↓AC提出
Submission #8506338 - AtCoder Grand Contest 015
AC
int main()
{
cout <<setprecision(10);
string s; cin >> s;
ll ans = 0;
ll n = s.size();
rep(i,s.size()){
if(s[i]=='U'){
ans += n - (i+1);
ans += 2 * i ;
}else{
ans += 2 * (n - i - 1);
ans += i ;
}
}
cout << ans << endl;
}解法
・0インデックスなら、s[i]がU のとき、それより下に行くのは
0,1,....,i-1 のi個がある、これらは2回押さなきゃたどり着けない。
それ以外のn - 1 - i 個の階（今より上の階）に対しては 1回押せばいけるので このような立式になる。
s[i]がDならその逆。
int main()
{
cout <<setprecision(10);
int n ; cin >> n;
vector<string> S(n);
rep(i,n) cin >>S[i];
int num[26];
rep(i,26) num[i] = 50 ;
rep(i,n){
for(int c = 'a' ; c <= 'z' ; c++){
int count = 0;
for(int j = 0 ; j <= S[i].size() ; j ++){
if(S[i][j]==c){
count ++;
}
}
chmin(num[c-'a'],count);
}
}
int ans = 0;
rep(i,26){
char c = 'a'+i;
rep(j,num[i]){
cout <<c;
}
}
cout << endl;
}解法
aの使える個数は、S1~Snのそれぞれに入っているaの数をsa1,sa2,...sanとすると、 それの最小値
って感じなことをやっていく
sa1~sanの最小値はnum[0]に格納されている
で
あとは
a~zについて、aをnum[0]回,bをnum[1]回…出力させれば解ける
ACコード
Submission #8499609 - AtCoder Beginner Contest 131
int main()
{
cout <<setprecision(10);
ll n; cin >> n;
vector<pair<int,int>> task(n);
rep(i,n) {
ll a,b;
cin >> a >> b;
task[i] = make_pair(b,a);//task 締め切り、かかる時間
}
SORT(task);
ll time = 0 ;
rep(i,n){
ll a,b ;
tie(b,a) = task[i];
time += a;
if(time > b){
cout <<"No"<<endl;
return 0 ;
}
}
cout <<"Yes" <<endl;
}解法
締め切りが近づいているものは早く終わらせよう
例えば、
タスク１締め切りが 5分、かかる時間が1分
たすく２締め切りが 5 分 かかる時間が2分
みたいなとき（たとえがおそらく適切でない）
タスク1、2の順でやっても、タスク2,1の順番でやっても、間に合うときは間に合うし、間に合わないときは間に合わないんですよね。
締め切りが5分のもののかかる時間の総計が結局のところ5分で終わらなきゃいけない。
みたいな感じ。
証明 ↓
Task 1 A1,B1,
Task 2 A2,B2
(B1 <= B2)
Bが小さい順にタスクをしたほうがいいことを示す
1 2 の順でやるときには
A1 <= B1 && A1+A2 <= B2を満たせればいい これを条件①
2 1の順でやるときは
A2 <= B2 && A2 + A1 <= B1 を満たせればいい これを条件②
締め切りが近い順にやればいいってことを示すには、
条件①のほうが緩いことが示せればいい
条件②を満たしていて条件①を満たせてないのがなければいい
条件①のA1 <= B1 を満たさないとき、
条件②の A2 + A1 <= B1 は当然満たせない
次
条件①の A1 + A2 <= B2が満たされていないとき
条件②の A2 + A1 <= B1 は、 B1がB2より小さいので当然満たされない
よって ①が無理なら②も満たしていない
これで証明終わり
らしい
C - Go Home
ACコード
https://atcoder.jp/contests/abc056/submissions/8498356
int main()
{
cout <<setprecision(10);
ll x ; cin >> x;
ll ans = 0 ;
ll sum = 0;
for(ll i = 0 ; i < x ; i++){
sum += i;
if(sum >= x){
ans = i ;
cout << ans << endl;
return 0;
}
}
ans = x;
cout << ans << endl;
}解法
①sum に1 ,2,...と足していって、 xを超えたときを考える、
最後に足した値をnとすると、1個前に足した値はn-1、
nを足す前のsumは x-1 以下なので、
nを足した後のsum は x + n より小さい。
よって 1 ~ (n-1) までのどれか(k)を sum から引く（この操作は、時刻 k - 1からkにかけての操作を 「飛ばない」にすることである）ことでちょうどXに飛ぶことが出来る。
解法② （解説の解答）
①の場合より計算量を落とす方法
①のノリで、ピョンピョンカンガルーさんがどんどん跳ねたとき、sum = 1 + 2+ ...+n (nを足したらxを超える）
この時X <= 1/2 * n *(n+1)
式変形をして
n ^ 2 + n -2X = 0
となるのは二次方程式の解の公式のノリで
n = -1/2 + root(1+8X)/2
このときのnが答えになる（多分）
ちなみに書いたコードは↓
int main()
{
cout <<setprecision(10);
ll x ; cin >> x;
ll n = (-1 + sqrt(1+8*x)) / 2;
cout << n << endl;
}
atcoder.jp
問題
提出コード(大事なとこだけ）
int main()
{
cout <<setprecision(10);
ll N ; cin >> N;
vector<ll> a(N);
rep(i,N) cin >> a[i];
//ソートは出来ない。
ll S = 0;
rep(i,N){
S += a[i];
}
//一番好ましいのは、 S / 2 にすること
ll prefer = S / 2 ;
ll sunuke = 0;
ll ans = INF;
rep(i,N-1){
sunuke += a[i];
if(sunuke < S / 2){
chmin(ans,abs(sunuke - (S -sunuke)));
}else{
chmin(ans,abs(sunuke - (S - sunuke)));
//breakがあるとダメ
}
}
cout << ans << endl;
}
||
解法
・一番良いのは、どちらかの得点を S / 2 にすること （Sは整数列の総和） (この時もう片方の得点もS / 2 になる
・整数列には、負の数も与えられているので、sunuke （すぬけの得点を表す変数）がS / 2 を
初めて超えた後、またS / 2 ( prefer)に近づくこともある。
だから、一度prefer を超えたらそっから先は見ないなんてことはしなくていい。っていうかしちゃだめ。さらにいうとbreakしたからと言って最悪ケースの計算量は変わらないからするな。
-> break ; があるとダメな理由
rep(i,N-1){
の中のif条件分岐は必要ない
解説の解答
・総和をXとして、 i枚目までの総和をxi ,とする
(1 <= i <= n-1)について
| xi - (X -xi) | = |X -2xi | の最小値を取ればいい
↓提出コード
Submission #8496532 - AtCoder Grand Contest 011
解法
到達時刻でソートして、到達時刻が早い人からどんどんバスに乗せていく。
このとき、以下の条件を満たす必要がある。
・ バスに乗れる人数は C 人まで。
・人は、k分より多くバスを待つことが出来ない。
↓ WAコード
rep(i,n){
rider ++;
if(i==0||newbus){
active_start = time[i];
newbus = false;
}
active = time[i] - active_start ;
if(rider == c ){//k分を超えてしまったらダメ 1戻す必要がある
bus ++ ;
newbus = true;
rider = 0;
}else if( active > k){
bus ++ ;
//今いるところからもう一度やらないといけない
active_start = time[i];
rider = 1;
}
}
||
これのACコードと違うところは、
if(rider == c)
else if(active > k)が逆になっているところ。
このコードだと、
例えc人目の人を乗せたとき、最初バスに乗った人（待ち時間が一番長い人）の待ち時間がkを超えてしまっても、乗客がc人になった段階でbusが一台追加されてしまう。
クソ
AtCoderレート下がった
オーマイが…
今日の知見
atcoder.jp
整数列 a1 ,a2 ,a3 .... an
について、この中から好きなだけ選んで和を取る（0個、全部も可能）
この時、整数列に奇数が一つでもあれば、和が奇数になるものと偶数になるものは同じ数だけある。
ちなみに和はそれぞれについいて取る/取らない の2通りなので、
2^n できて、半分ずつってことは奇数、偶数が2^(n-1)ってことになる。
詳しくは解説の動画で言ってるけど
要するに、一つの奇数に着目してみたとき、そのほかの数の部分は奇数か偶数になる。その時、着目した一つの奇数を足すか足さないかで奇数、偶数を操作できる！！
だから半分ずつ奇数と偶数になるよって話
バケモン化よ
解説天才すぎ…
はあああああああああ
緑なりたい。
