AtCoder Beginner Contest 196 反省
つらいね ぐにゃぐにゃになります
結果を鑑みて
1000 15:25
やらかした......という気持ち。青下位パフォ、全体785位、レート-29となった。最近やらかしたABC級4完はCaddiコンで、まあもう4完なんてしないだろ と思ってたらこんなことになってしまった。その時も今回もE: 数学, F: ライブラリ+高度典型といったラインナップだったので、こういうのが苦手なんだなーとはっきりした。
余談だが、CaddiコンのWriterと今回のWriterを見比べてみると......
A - Difference Max
見てすぐ解法はわかったのでその通りにやった。
B - Round Down
Xの上限が10^100とか書いてあってぎょっとしたが、これはよく考えると文字列で受け取って小数点で分割すればいいことにすぐ気付くことができた。いつぞやのABCで出た誤差ゲーでも浮動少数点数をまず文字列で受けるというテクが出たことがあって、そこで破滅したので記憶に残っていた。
C - Doubled
問題文が簡潔なので問題読む前に制約が目に入った。問題文を読むと制約の意味がすぐに理解できた。てきとうに全探索するだけなのですぐに書いて出した。
ところでサンプル2の1333ってなんだろう。
この時点で初めて順位表を見た。そこそこだったので焦らず進むことができた。
D - Hanjo
少し悩まされた。まず、問題文と制約から盤面の全列挙が可能なことに気付いた。これをbitDPで組もうとするのは少し大変で、精神のリソースを消耗することが予想された。そんなわけで少し逡巡して、dfs木の深さが高々8程度に抑えられることから、盤面と１畳の畳を引数に持った再帰的な解法を試みた。
サンプル2で答えが大きくなりすぎて少しびっくりした。重複をうまく除去できていないからこの方法じゃダメなんだ、と思ってコードを消そうとしたが、どういうわけか踏みとどまって順列で割ることを思いつくことができた。ふと思い出した蟻本のボリアの数え上げ定理の記憶が助けてくれた。ありがとう蟻本。
この時点で順位表をみるとかなりいい感じだったのでエンドルフィンの分泌を感じながら次の問題へ進むことができたのだが......
E - Filters
問題を読むと、操作についての前計算を行い、クエリに対して小さい計算量で解答する問題のように見えた。
次のように解法の予想を立てた。
1. maxやminをif文に置き換えて数直線上のイベントソートのようにやる
2. なんかがんばると遅延セグ木に載る
3. 実はmaxもminもまとまっていい感じになる
コンテスト中は特にパッと思いついた2. が光明のように感じられて、大半の時間をmaxの合成写像を考えることに費やした。
1. もそれなりだが、加算操作のせいで前計算が二乗計算量になってしまい、うまくいかなかった。
1. も2. もうまくいかず、すっかり焦ってFを見に行ってあれこれ考えたりした。こういう時、どうやって思考をクリアに戻すのが正しいのだろうか。
最後10分ほどで3. をやけくそになって考えた。実はこれが最も答えに近かったのだが、結局コンテスト中に提出することすらできなかった。
できあがる関数の形に注目する問題はABCでも度々出題されているが、だいたいの場合はそれが単調性と結びついて二分探索やら三分探索につながる問題だが、自分は今までそのような問題に対して「単調性がありそうか」を調べ、その結果として関数の形に気付くことが多かった。maxやminの合成関数の概形が正しく想像できなかったのも無理もなかったかもしれない。ただ、サンプルは明らかに単調だったので嘘でもにぶたんとかしておきたかった......
F - Substring 2
この問題を見たのはEに詰まっていたときで、パッと見てdpや前処理、差分などに思いを馳せた。感覚的には解けなくもなさそうだった。solve probability 30~50%程度の感覚だった。
Binary Trieとの相性が良さそうに見え、それを使った考察に時間を使い、ダメだと思ってEに帰る、といったことを繰り返した。
大局的に見たような定式化ができればこれは解けたかもしれないが、流石にEが通っていないとその余裕はなかったろうと思う。
解説を見て悔しい思いをした。配列同士のなんやかんやを多項式乗算に帰着する問題はyukicoderで一回解いていたのだ。とはいえEが通っていたとしても組み切れていたかはわからないが。
総括
Dまでのムーブは大体よかった。バランスよくいろいろな方面に思考とエスパーを巡らすことができ、それが功を奏した。
Eで1時間強も椅子を温めることになったのはかなり厳しい気持ちになるが、時間配分やレートロスの最小化を考えた際に適切な判断ができていなかったのは問題だと思う。Fはやらずに順位表の動向だけ適宜見てEに取り組むべきだったかもしれない。
一方で、思考に詰まったときにこれを回復する術の習得が必要なことがわかった。試しに、ビハインドな上に思考の詰まった状況になってしまったら外を走ってこようと思う。
また、数学寄りの問題への習熟度の低さが露呈したので（というよりも考察のボトルネックが数学になっている）これもこどふぉなどで頑張って研鑽していきたい。
ちなみに最近すまーとうぉっちを買ったので、コンテスト中身につけていた。
ストレス値はコンテスト中ずっと低い状態で、心拍数がコンテスト開始時102 bpm、徐々に下がって22:00には76 bpm、最後10分は追い込みで103 bpmとなっていた。
80~90 bpm付近の頃は（問題が簡単なのもあるだろうが）エスパーが冴えていた。サンプル数が少ないのでよくわからないが、心拍数はある程度高い方が思考には向いているのだろうか。100 bpmあると流石に思考と脈のリズムが噛み合っていないような感じがした。
ちなみに、平静時は60 bpm程度なので、心拍数の爆上がりする競プロを毎日10時間やる生活などをしているといずれはしぬとおもう。
