ABC125

そんな感じはしなかったけど終了後37.0(今は下がってる)。始まる前は、ABCなのに緊張するなあウンコしたくなるなあと思っていた(ウンコが直前に来るのが困る(結局はしてない))。もうちょっとスピード出したかったというのはあって悔しいが、ノンペナ全完はいいものだ。

A - Biscuit Generator

Aにしてはかなり難しそう。どうせ小さい数だろうし、全探索でゴリ押すことも考えたが、きっちり考察して書いた。まず、最後にBを掛ければいいことがわかる。次に、TがAのときを考えると、ちょうどビスケットができたところだ。つまり、T/A(あまりは切り捨て)で生産回数がわかる。

B - Resale

これはやるだけ。VとCが同時に得られないのが面倒だ(考察が済んでいるので面倒だとわかる)。Vだけ配列に入れておいてmax(V_i-C_i, 0)を足していく。

C - GCD on Blackboard

少し考えてわからなかったので、D問題と並列でやることにした。C問題でこの悩み方は既視感がある。頭が固いのだ。Dが簡単そうだったので、DをACしてから戻ってきた。

まず状況をしっかり認識する。0に書き換えることができないのは確認していたが、0に書き換えるとしてよい(自分以外の最大公約数と同じ数に書き換えれば0にしたのと同じになる)。gcdをとっていくとどんどん因数が減っていくのでネックになってる1つを除けばいい(0とgcdをとっても変わらないので除くのと同じ)(ただ、この考え方だと、残った因数たちの積の最大化が難しいと思った)。全体を半分に分けることを考える。それぞれの最大公約数の大きいほうが上限になる。ただ、何も起こらない(解けない)。そもそも、半分に分けて解けるなら、1個とN-1個に分けても解けそうなものだ。それで考えよう。A_1を書き換えるかどうかで場合分けする。書き換える場合は簡単(A_1を0にするだけ)。書き換えない場合、これ問題のサイズが1小さくなってるね!

A_2からA_NのN-1個の中から1個を書き換えるのだから、Nが1小さい問題に帰着できた。これは累積和的に左右からi個の整数の最大公約数を持っておけば問題が解ける。要するに切断の場所をN通り試せばいい(順番は関係ない問題なのに不思議な感じ)。解けた。この時点で開始17分くらいだった(文章にすると長いがけっこうスムーズに解けてる)。20分切りも見える。しかし、実装が大変だった。境界がちょっと注意を必要とする程度でそんなに難しいわけではないが、なぜかこれは書き慣れてない。実行時間の最適化ができない。しなくていいのだが、自分の場合それができないということは、処理内容に慣れてないということだ。実行時間ではなく、見慣れぬ景色が問題なのだ。コードも汚くなる。何をすればいいかはわかっているのに(後から考えてもわかっていたのに)、ものすごくしんどい思いをして実装を進めている。やはり累積和と同じでN+1要素のvectorを使うのが考えやすい。最初のi個の最大公約数を保持(最初の要素は0)。反対側は、最後の要素が0になるように。+1の必然性がよくわからないまま、正しさだけは保証する思考(保証といいつつこれは(見るからにそうだと思うが)よく漏れる)で提出。

あ、答えが0のとき10^9を出力するの忘れた!と今思ったけど、制約を見直すとN>=2だった。サンプル3がN=1だと思い込んでいた。やっぱり親切だ。

D - Flipping Signs

これは見るからに簡単そう。-1倍できるのは偶数個っぽいと思い考えると、実際そうだ(一回に2個を反転させる)。そして偶数個であれば好きな場所にできそう。端から決めていって、自由にできないのは最後の1個だけ。その最後はパリティチェックみたいになってるから偶数個であれば合うはず。これは配列を用意する必要がない。唯一負の数のまま残るものをmaxとっておいて全体の合計から2倍を引けばいい。0の扱いは少し迷ったが、負の数としてカウントするのがよさそう。0があれば自由になる(-1倍してもしなくてもいいので)。

雑に書いてサンプルで様子を見るのだが、サンプル2が通らない。合計は(紙で計算して)36。そこから3の2倍を引いて30に見えるがなぜそう出力していない?引くんじゃなくて負の数を絶対値とったぶん補正するんだから足すんだよ(中学生か!)。それでも合わない。あー、単に絶対値最小のものをあぶれさせるんだよ(気づいてなかったのか!?(コンテスト中の理解はこんなもんで、全くわかってないわけでもない))。カウントするのは0含めてもどっちでもいいが、とにかく全体の合計と絶対値の最小を求めて、カウントが奇数なら今度こそ2倍を引く。やはりサンプルが超親切だった。