4完。まだ緑コーダーなのだから満足してもいい成績だとは思うのですが、Eはなんとかしたかったと思う自分がいる。
罪深いぜ令和ABC・・・。
各問題
A - Airplane
かかった時間に移動の順序は関係ないので、要するにP+Q, P+R, Q+Rの3パターンのうち最小のものを取ればいいです。
B - Balance
累積和を取ると、i番目までとi+1番目からで分けたときS1とS2はそれぞれsum[i]とsum[N] - sum[i]になるので、それらの差の絶対値を端から順に取っていって最小となるものが答えです。
Bで累積和！？と思ったけど、愚直に計算しても間に合うのね。
C - Typical Stairs
i段目に上がる方法は「i-1段目に上がる方法」＋「i-2段目に上がる方法」で求められるので、それをDPで回していくだけです。 壊れている段については上がる方法がないので無条件に0になることに注意です。
CでDP！？と思いましたが、漸化式が単純（ていうかフィボナッチみたいなもの）だからあり、なのか？それにしてもMODもありますしねぇ・・・。
で、単純な漸化式とか言いながら、私はすぐに思いつけず、先にDをやりました。on_
D - Lamp
まず、縦と横で累積和チック？に見渡せる範囲を保存していきます。
例えば#...#.#..という並びに対しては{0, 3, 3, 3, 0, 1, 0, 2, 2}みたいな感じで。
それから、あるマスに対して縦と横の見渡せる範囲を足して、重なり合う範囲がひとマスあるので1を引けば見渡せる範囲がわかるので、すべてのマスに対してそれを求めていって最も大きいものが答えです。
editorialでは縦横の二通りではなく四方向で見える範囲の保存をするような解説がされてましたけど、そっちのほうがまっすぐ捜査するだけで済むので実装がシンプルでバグらせにくいかもしれません。
E - Sum Equals Xor
考察の結果、editorialで言われているところの、「どちらの数についても 1 であるような桁」が存在しない、まではわかりました。
で？
どうすんの？
というところでタイムアップでした。Lを超えないようにという条件がつくので今の私には無理ゲー。
F - Takahashi's Basics in Education and Learning
ちらっと見て、そっ閉じ。
まとめ
やっぱり数学力とDPが今の最大のボトルネックなんですよねー。後者はDPの問題を解きまくれば慣れていくでしょうけど、前者はさすがにつらい・・・。
水パフォは維持できているけど、もうひと伸びがないと水色コーダーにはなかなかたどり着けないですね。
