AtCoder Beginner Contest 224 反省

ちゃんとABCにでた記念。

結果を鑑みて

2000(4) 117:38

316位。ABCの練習して青落ちしても大丈夫なようにするぞ〜と思った矢先、轢き殺されてしまった......。パフォーマンスたぶん1900台なので微冷え。

A - Tires

うしろ２文字が"er"かどうか判定する。うしろ３文字が"ist"かどうか判定しようとすると２文字だったときにREするところまで予知した。

B - Mongeness

monge性の定義そのものっぽい。言われた通りにやる。添字を間違えやすいのでブラウザとにらめっこしながらコードを書いた。

C - Triangle?

正の面積とかいうから符号付き面積を想像した。それは関係なかったし、N≦300だったので単純に3つ取って直線上になければいいなと考えた。

これを通した時点で６０位くらいだったはず。そこまでスピードは衰えていないなと思いながらDへ進んだ。

D - 8 Puzzle on Graph 

なんか制約ちっちゃいな、bit全探索→WFとかできそうだな〜（できません）とか思ったりしていた。9!が結構小さい値なので、この順列を探索することにした。最初、バカすぎて再帰でDFS書いたりした。BFSに書き直してなんとかAC。

かなりぐちゃぐちゃになって時間がかかり、この問題になんと２０分かけた。重実装の易問でぐちゃぐちゃになるのは勿体ない。こういうのの練習しといたほうがよさそう。JOIとかかな。

E - Integers on Grid

0の部分は無視できることがわかり、二乗だったら解けるな〜というのが第一印象。

重要なこととして、同じ行（列）のある値へ遷移しようとしたとき、同じ行（列）のその値と自身の中間にある値を経由した方が良い。ということは、遷移先としては同じ行・列の自分よりほんの少しだけ大きいやつへ遷移させるようにすれば良い。行、列ごとに要素を集めておいてにぶたんで遷移先もできて、あとはトポソしてlongest pathを解けばよし！とした。

1ケースのみのWAが返ってきて、コーナーか？？？とか思った。どれだけ考えてもコーナーが思いつかず、頭を１８０度くらいひねってさらに虚無提出をもう一回した挙句、このままではまずいと思ってFへ行った。

Fを解いて、さらに虚無提出（ばか！！！）をしてぐっとコードを睨んでいて気付いた。

遷移先は行と列で高々２個だと思っていたが、同じ値の数字がいくつもあったらそうはならない！このとき単純に同じ値のすべてに辺を引いたら最悪O(N^2)の空間計算量となる。そこで超頂点を管理してうまいこと辺数を削減する。

時間がなくて元のコードを拡張してCounterで超頂点のぶんのdp配列を実装したのでさらに1回TLEして、定数倍高速化したら1900msとかで通った。きびしいよ〜

F - Problem where +s Separate Digits

なんかよくわからない名前しているが、主客転倒でうまく解けることを直観した。

2^-i * 10^iとかを累積して（なんか数学でここスキップできないか？とは少し思ったがスルーした）やろうとした。

なんか値が合わず、ここで5~10分くらい使っていたのだと思う。+が末尾に置けないこととかを考慮して、累積和をちょっといじらなくてはならなかった。気付いてからは早かったが、気付くまでにちょっとかかってしまった。DやEでてこずってやや焦っていたかもしれない。

とにかく解いてEに戻った。

G - Roll or Increment

あんまりみてない。 

H - Security Camera 2

みてない。

総括

まあ、しばらくABCちゃんとやってなかったわりにはまずまず。ARCに取り組まなくてはならない身としてはカスだった。

DやEでの筋の悪い実装が目立った。Dは少し勇足になって解法の全体像がやや見えていなかったこと、Eでグラフに対する想像が薄くて二部完全グラフになるようなパターンを最悪ケースとして想定できなかったことなど。そもそも陽にDAGにしようとするのが筋悪だったのだろうか？しっかり復習と修練を積んで次は暖まれるようになろう！

立ち回り自体はまあまあか。Eで詰まってからFを見に行くのが遅かった。こういうところも再度意識していきたい。