AtCoder Beginner Contest 205 反省
今回はコンテスト前まで体調が終わっていて、ウォームアップの問題を解いていなかった。前回の分は書いていないが、黄パフォだった。内容について軽く触れると、ABCDFの5完で、順位表から得た情報でDとFを通して何とか冷えずに済んだ感じだった。ほぼまぐれ。
結果を鑑みて
1600(1) 85:54
239位となった。EとFは何となく解けるオーラがあったので両方同時に考えていた結果、Fだけ通してしかも時間がかかったという結果になった。とはいえ立ち回りはマシになってきていると思う。
A - kcal
writerにサーバルがいるので誤差問題かと勘繰ってしまった。関係なかった。
B - Permutation Check
len(set(a))を見るだけで良いことがすぐにわかるが、2重ループを許す制約なので少し不安になった。通りはした。
この時点で順位表を見た。100~200位くらいだったと思う。
C - POW
どちらもC乗なのでAとBだけ見ればいいだろと思ったが、よく見るとA, Bが負の数も許容されている。Cが奇数かどうかで場合分けをした。一応、A=0のときとかがコーナーになっていないだろうかとチェックしていた。まあ指数関数なので問題ない。
この時点でも100~200位くらいだったと思う。いいペースで解けていた。
D - Kth Excluded
答えの二分探索を考えてあげると、その値が何番目になるのかはさらに二分探索でわかる。最近解いたARCの問題で、ある数についてのある計算値から数が昇順何番目になるかが推測できるという問題があった。これを思い出したおかげで解法がわかった。
出してからジャッジの進みがやけに遅いことに気付いたが、TL3secだったので通った。このとき、実行時間制限が3secだったことを把握していなかった。今回は通ったが、場合によっては定数倍高速化が必要になった可能性もあるので気をつけよう。
この時点で50位くらいだった。安心して次に進めた。
E - White and Black Balls
インラインDPっぽいなあと思いつつも遷移がよくわからず、よく考えないままFを見に行ったらめちゃくちゃ二部マッチングっぽいので投げてみたが何だか通らず、EとFは同時進行で考えていた。
残り30分くらいになってやっとカタラン数との明確な関係性に気付けたが、対称位置のアイデアを思いつかず、解けなかった。単純な幾何で対称位置をとるのはよくやる操作だが数え上げでやることになるとは......
F - Grid and Tokens
見てすぐ最大二部マッチングだと思ってmaxflowを投げたが通らず、残り20分までうんうん唸りながらEとFを同時進行していた。
通らなかった理由は行へのコマの割り当てと列へのコマの割り当てを別々にやっていたから。この場合、行への割り当てで用いなかったはずのコマを列に割り当てたりすることができてしまう。解決案としてこの2回のフローを重ねていっぺんにやる構造を考えていた。最終的に残り20分くらいで行とコマと列のサンドイッチみたいにすればいいことに気付けた。サンプルのおかげでコマの頂点は倍にしなければならないことにも気付けた。（このくらいは自分で気付こう！）
総括
Dまで解いてE捨ててFに行ったムーブは悪くなかったが、通らなかった時にどちらも捨てきれずにどっちつかずな進行をしたのはよくなかった。今回はEもFも解けそうな問題に見えたことがこのどっちつかずムーブの原因でもあるが、効率の良くないムーブなので考えものである。精神が安定しているときはこのムーブを取っても良いが、今回の後半のようにやや焦りを感じながら2つ以上の問題を考えるのは若干無駄なので自分の状態に応じてさっさと切るかどうするか決めたほうが良いのかもしれない。
