エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202） 反省
久しぶりにまた書いている。ゴールデンウィークから先週末くらいまでひどいスランプに陥っていて半月で150近くレートを溶かしてしまった。
結果を鑑みて
1500 43:21
Eで時間をかけすぎてしまったようだ。とはいえ2100ほどのパフォーマンスなのでレートは上がる。スランプは脱せていると良いが。
A - Three Dice
21から引けば良い。やるだけ。
B - 180°
反転するとどう見えるのか書いてあるので、その通りにやる。うっかり変換のし忘れがないかちょっとヒヤヒヤしていた。
C - Made Up
読んでもよくわからない感じだったが、C_jに注目してみるとテーブルにまとめてしまえばいいような気がした。この解法で正解なのだが、いかんせん問題文がよくわからなくて雰囲気で実装した。サンプルは合っていたので出した。
ここで順位表を見る。300位くらいなのでそこまで早いわけではなかったが置いてけぼりにされているわけでもないので特に心持ちの変化はなかった。ただ、自分としては結構すいすいといたつもりではあった。
D - aab aba baa
まず階乗進数に思いを馳せたが、文字は2種類なのでもう少し簡単だろうと思った。
AもBも小さいので全列挙できるかな？と思ったけど60C30を考えて真顔に。
組み合わせが計算できるなら、その値を参考に貪欲に構築できるなと思った。試しに60!までテーブルに保持したが時間はかからなかったのでこの方針で解き始めた。辞書順K番目の文字列を出力する問題でバグらせなかったことはないので、落ちたらやだなあと思いながら出したら通ってびっくりした。
E - Count Descendants
最初すぐには解法が浮かばなかった。木DPで集計してクエリに答えるタイプだろうと推測した。集計できる感じではないので、ダブリングでも使うのかなと思って考えていたがこれもよくわからなかった。
部分木クエリに読み替えて深さの小さい頂点から木に出現させていく（？）手法を取ればクエリソートしてオイラーツアーを区間木に載せることでとりあえず解けそうなことには気付いた。実装が重いので想定解ではないだろうと思ってこの実装に踏み切るのに逡巡したが、仕方ないのでこの方針をとった。
40分あたりでACしたが、この時点で2150くらいの推定パフォーマンスだったので方針を間違えて時間をかけすぎてしまったのだと解釈した。実は今回の実装は想定解通りで、単に自分が悩みすぎていただけだったのだ......
F - Integer Convex Hull
普通に諦めていたが、一応解こうとしてみた。
3点選んでその内部に入る点を見つけるのはO(N^4)で可能。三角形の面積の関係を使った。
辺を共有する三角形同士を連結することで凸包を作る方針で行った。辺を共有する三角形同士を無向グラフ上で連結させると、グラフは木になるように思えた。
そういうわけで木DPしていたが、値の伝播が難しく、「無理だなあ」と思っていたらコンテストが終わった。
総括
Dくらいまでいいペースで解けていた。ライブラリをちゃんと整備して木→オイラーツアー列をパッとできるようにしておけばもう少し速く自信を持ってEを解けたのではないかと思う。全体的にあまり焦りは感じなかった。
スランプは概ね抜けたのではと思ってはいるが懸念もある。Eを解いている時に頭にもやがかかるような感覚に陥った。今回は大して支障はなかったが、俯瞰することを見失って大冷えするときは大抵こういう感覚を味わうので（ここ２〜３週間はずっとこうだった）まだ油断はできない。
