AtCoder Beginner Contest 203 反省

今のところそこまで調子は悪くない。忙しくなる前に黄色に戻れるといいが。今回は開始1時間前から緑水青の3問を解いていた。開始5分程度での体感時間は実際の2倍程度だった。良い時は5倍くらいになることはあるが、比較的良い集中ができていたと思う。

2100(1) 84:46

93位となった。遅めの全完という感じだが、パフォーマンス2400だった。全体的に考察よりも実装が足を引っ張った印象だった。

if文で列挙した。xorでできると言われてびっくりした。確かにそうだ。

全列挙して実際にintとみなして総和を取る方法と数学をする方法がある。いつもであれば全列挙を選ぶが、今回は数学する方を真っ先に選んだためO(1)で解くことになった。この問題にはコーナーケースらしいものは感じられなかったので、サンプルを合わせるとすぐに提出することができた。

流し読みすると最短経路問題かなあという気分になるが、よくみるとシミュレーションするだけっぽいので普通に組んで提出。実装の問題だが、わずかにミスしやすいポイントを作ってしまった。提出前に気付いたので良かったが、できるだけ場合分けの多い実装は避けるよう日頃から心がけるべきだろう。

この辺りで順位表を見ると、200位未満であった。悪くないスピードなので焦らず進むことができた。

難儀した。3分くらい考え、トイレに行ったら解法がわかった。解法を二分探索と決め打たないとなかなか気付けない問題だった。Median of Medians を解いていれば典型と言えるかもしれないが、その上で二次元累積和を要求するのは400点にしては難しすぎではないかと思う。

判定関数で「何を判定させれば良いか」正確には不等号の向きなどで詰まって時間を使った。サンプルがいくらやっても合わず、焦って順位表を確認したりもした。この行動は結果的には良かった（みんなも事故っていたので安心できた）が、基本的には焦燥を加速させるだけなので好ましくない。

実のところサンプルの合わない本当の原因は二次元累積和の添字ミスだった。累積和配列になぜか単調性がないことに気付いて直すことができたが、この問題には30分近く費やしてしまった。

二次元累積和はスニペットにして良いかもしれない。

ソートしてごちゃごちゃやるとかデータ構造とか色々解法のとっかかりはあったが、最初にインラインdpの方針を取ることにした。これはおそらく、問題を見てすぐにたどり着ける点は多くてM+1程度しかないということに気付けたため。

Counterでdpを書き、dpの更新はキューにためておいて一括更新する形をとった。詰まったのは、Xが縦、Yが横だったこと。チェスのマスの読み方は(縦, 横)なのかもしれないが、それなら(Y, X)にしてほしい。これのせいで2~5分は溶けている。条件はよく確認しよう。

そんなこんなで20分ほどかけてAC。順位は100位ちょっとだったので余裕を持って先に進むことができた。

まず、解けそうなオーラを感じ取った。時々、コンテスト中に問題文から解けそうな雰囲気を感じとることがある。そういう時、大概解ける。とはいえ今回解けたのはたまたま気付きが連鎖しただけだったが。

まず、ソートして高い草から除いておくべきではないかという気になった。よく考えると低い草を除くのも寄与が大きい場合がありそうだった。状況に応じて真ん中も...... と考えると、貪欲の線は薄い。

二分探索で高橋くんの操作回数をまず決定することを考えた。「後から保障する」アイデアでうまくいく気がした。判定関数を考えていると、二分探索する必要性がわからなくなった。

次にdpを考えた。一次元で済まそうとしたが無理だったのでN*Kのdpを書いていた時、そういえば高橋くんの操作回数は少なく済みそうだということに気付いた。思い出しただけかもしれないが。そこで思い切って持つ状態と、求めたい値の立場を逆転させて解くことができた。

dpの遷移を決める際の二分探索パートで上界の設定をミスってて1ペナした。すぐ気付いて再提出した。大して順位は変わっていない。

冷静に問題を解くことができていたと思う。ただ、今回は偶然に愛された部分が多く、立ち回り、実装上の注意など課題が残る。

とりあえずまあ1900には戻れたようでよかった。

perarduaadastra