Codeforces Round #206 (Div. 2)

Codeforcesに初参加したので感想を書きます。最初の2問しかできませんでした。

A

難易度の基準がわからなかったので、定義を見てかなりビビった。でも、他の人達が即答しているのを見て、見掛け倒し問題なのだとわかった。

B

簡単な場合分け。
最高でもc4を払えば十分。busに払う額をmax_bus、trolleyに払う額をmax_trolleyとして、max_bus+max_trolleyとc4の少ない方を払う。
max_busは、最高でもc3。これと一枚ずつ払う場合と比較すればよい。
max_trolleyも同様。

C

ぱっと見では、左から取った回数、右から取った回数で2次元DP(最後に取った方によって2枚用意)をすれば良いと思うが、1<=N<=10^5なので、それだと間に合わなくなる。
なぜか、配列を再利用して空間計算量を削減すれば大丈夫だと思い、そのまま実装してしまった。
結局、N=10^5のテストケースをもらってHacked。
正解を見たら、全然DPじゃなかった。

まず、左から取った総数Lを決める。すると、右から取った総数R=N-Lが決まる。
L<Rのとき、R回のうちR-L回は、必ず右から連続して取ることになる。
ここで、取る順番によって結果が変わるのに、それを考慮していないことが気になるが、最小コストさえ求めればよいことに注目。
つまり、左から連続して取る場合や、左から取り始める場合は考えなくて良い。
最善手は、右から取り始め、左右交互に取っていく方法であり、この時のコストは簡単に求まる。
あとは、Lを0からNまで動かして最小値を求めればよい。

左から取った総数Lを決めるとかなりのことが決定される(左のL個は全て左から、右のN-L個は全て右から取ることになるし、連続で取る回数も分かる)のだが、そこが意識できていなかった。
最善手を考えることによって探索空間を削減するのは良くあるパターン。

あと、10^5を10000と間違えるというミスもしていた。今後は気をつけよう。

D

誰も解いていなかったのでパス。

E

1<=n<=3*10^5、1<=a<=10^5なので、brute forceではもちろん間に合わない。
求めるgcdをa[0]~a[n-1]の最小値から初め、少しずつgcdの値を小さくして試していく。
a[0]~a[n-1]を昇順にソートして、小さい順番に試し、制約を満たさない場合はgcdを1減らすという方法でやってみた。
ここで、残り時間が少なかったので、「a[n]まで既に制約を満たしている場合は、gcdを1減らしてもa[n]までは制約を満たしている」という謎の仮定を置いた。
他の人の解答を見ても、このように考えた人が多かったようだ。
結局TLEになってしまったわけだが、多くのテストケースを通っているので、もしかするとこの仮定は正しかったのだろうか?

ポイントは、gcdを効率よく減らしていくことにあったようだ。
あるa[i]に対して、a[i]%gcd>kだったとする。(つまり制約を満たさない)
ここでa[i]の中にはa[i]/gcd個のgcdが入っている。
ここからgcdを減らしていくわけだが、どこまで減らせるだろうか?
仮にgcdを1減らすとする。gcdが十分大きい場合、a[i]%(gcd-1)=a[i]%gcd+a[i]/gcdであり、a[i]%(gcd-1)>k、つまり制約を満たさないことは瞬時に分かる。
検討に値するのは、a[i]に入るgcdの個数が増えるときである。
結局、gcdはa[i]/(a[i]/gcd+1)まで一手で減らすことができる。
f:id:nupioca:20131014133836p:plain