ABC124

Cまで、調子良くは解けていたが実装に少し手間取ってしまった。Dが難しく少し頭痛を伴うくらいの熱を感じた。終了後36.9。Dの考察に手間取るのは(問題が難しいので)仕方ないが、全体的に「このくらいの実装すいすいできないの?」って感じだ。

A - Buttons

大きいほうを押せばいいのだが、A==Bにコーナーケースのにおい。大きいほうを2回押したらダメ。ただ、処理を2回書くのは嫌だし、この程度でわざわざループを書くのも嫌。swapでAのほうが大きいとして、a + max(a - 1, b)という方針にした。これは1分切りたかったなあ。今回は問題の読み込みも時間かからなかった。

B - Great Ocean View

問題文が読みづらい。「かつ」の意図が見えない(後から考えると英語だと思えばよかったのか)。サンプルも交えつつ問題を読む。これは全探索できる。しかし、面倒なので配列や二重ループは避けたい。高さの最大値を保持していれば行けそうだ。m = max(m, h);の形のコードスニペットはこの前登録して慣れてきた。

C - Coloring Colorfully

「初めの色」というので混乱した。タイルが2次元のように感じる。塗り替えていくので初期値という意味だった。塗り方は2通りしかないので簡単。瞬殺だったが、'0'を引くかとか2通りをループにするかとか文字列に対してrange-based forを使うかとか迷いに迷って時間を食ってしまった。見通しがよくない。

D - Handstand

C問題とD問題で、なぜNの入力での与えられ性に違いがあるのか気になった。まっすぐ逆立ちしたら直立と言える可能性があるのではと気になった。「1を連続で最大いくつ並ばせることができるか」と言えばいいのに逆立ちを経由するのしんどいと思った。

反転するのは0が連続する区間だけでいいような気がする(1は反転させない)。実際、区間が完全に含まれていれば(回数を増やさずに)小さい2つの区間に分割できるし、一部が重なっているときも、偶数枚の指示が重なっているとこは消せる。やや雑だが、これが成立するとして話を進める。じゃあ連続する0の個数を数えて多い順にK個取ればいい?いや、1を増やしたいだけならそうだけど、この問題は「連続で」だ。ここで、問題が思ったより難しいことに気づく。

もう20分切りは諦めている。じっくり考える。同じ数字が連続する個数を数えるのはそうだが、1も数える。情報はそれだけでいい(べつに情報減ってないだろ)。K回で連結にできるのは、1で始まって1で終わるK*2+1個ぶん。しゃくとり。これで既に解けている。あとは現実的な実装方法だ。端が面倒そう。0個の1を挿入するのはすぐ思いつくが、本当にそうしていいか、簡単に実装できるかを考える。行けそうなので実装する。こういう個数を数えるやつってループが終わったあとに最後の区間を追加しないといけないけどループだけできれいに書けないもんかねえと考えてたとこだった。それはやはりわからないけど、実装はまあできた。0で終わっていたら0個の1を追加する。答えがNになるケースの扱いに迷ったが、分岐して別処理に落ち着いた(こういうとこで時間食う)。しゃくとりで、ループをどこから始めるか(頭とお尻どっちか(どっちでもいいだけに))かなり混乱した。