緑diff埋め

あらすじ

水色になりました。

コンテストに出ていれば青は維持できると自惚れていたのですが、そうでないことが分かったので精進をすることにしました。

結果

ちょうどAtCoder Probremsの表示が変更された時期にやっていたのでちょっと惜しい感

感想

全体として、ずっと考えてもどういうアルゴリズムかわからんというのはなくて安心しました。 代わりに、「大体分かった->あとは実装するだけか」の実装パートの雑さ、遅さが(今まで薄々感じていたものの)明らかになった感があります。

得たもの

・何らかの満足感
・デバッグの粘り
WAが出ても流石に緑diffで落とすわけにいかんと躍起になっていたのですが、そもそも元々のすぐに放り投げちゃうスタンスが問題という説もあります。
・典型アルゴリズムへの慣れ(主に試験管問題から)
グリッド周りの処理を整備したのと、累積和をin-placeでやるようになりました。グリッドの問題が多すぎる

微妙だった点

・貪欲の証明
正直、コンテスト中ではないかつ緑diffだと高を括っており方針を思いついた時点で雑に投げていました。

水色に落ちた原因がまさにこの能力の無さだったのに...と若干の反省が残ります。

atcoder.jp 競技プログラミングのやらかしトラウマその2となりました。ちなみにその1はDouble Factorial

前から順に見ていけば良いのに反例(実は反例ではない)を思いついてしまい、謎のDPを始めた上にバグらせるという最悪の立ち回りでした。

終わりに

問題を埋めていくにつれ「まだポテンシャルあるから」という言い訳の余地がなくなっていくという不安もありますが... そんなこと言っている場合ではないので、まあやっていきます。
次は水diffです。