2019 ICPC Asia Taipei-Hsinchu Regional
ICPCの感覚を味わうために1人でバチャをしていた
始まる前は寂しいなと思ったが、自分が解かなきゃいけないものを全部1人で考察するのも悪くない
コンテストの流れ
まず問題文がpdfでびっくりする。
前からAを読むとおそらくやるだけだが、重実装なのが目に見えていたのでパス
順位表を見るとCがACされ始めていたので、Cを読む。
3重ループやるだけなので解く→WA
あほなので3重ループを書き直す→ C AC(0:07)
順位表を見るとDが結構通され始めてるのでDを解く
ABC-Aのような自明な問題なので通す→ D AC(0:13)
Kが通され始めてたのでKを解く
隣接同士しかできないと勘違いし、区間DPにしては制約が大きいと嘆く。
よく見るとただ
priority_queue
をすればいいと分かる→K AC(0:22)Hが通され始めてるのでHを解く
まではすぐで、が大きいので嫌だなぁとなる
よく考えるとの因数分解はの約数のペアの積を考えればよくてこれの数は少ない→H AC(0:36)
Jが結構通ってるので見る
nとmを逆に考えていて全く違う問題を解いていた(は???)
bit全探索やるだけ→TLE
文字列で愚直にやると間に合わないらしいと分かったので、bitsetを使う→J AC(0:57)
ここらで順位表でろくに解かれてる問題が無くなる。
AとEがまだ解かれていて、Aがやりたくなさ過ぎたのでEをやる。
90分近く考えた末にぐっと睨むと最初を-1にすればあとは最後までみれば構築できる→E AC(2:34)
もうまともに解かれてるのがAしかないので嫌だがAをやる。
制約がかなり小さい。全探索でなんとか間に合わせれる気がする。
dfsで見ていくのが自然だが、この局面を見たと判断するのが普通のdfsより難しい
というのも例えば8step目である局面が不可能でも4step目だと可能みたいなことが起こるかもと考えた
setに{局面, 手数}という状態を持たせてこれで全探索
配列がコピーになってたり、ちょっとだけ余裕持たせてた局面をぎりぎりにするとなんとか→A AC(3:46)
寝て起きて気づいたが、set[手数]で局面を管理したほうが探索回数がかなり減る
最短手数が決まる局面についてはメモ化再帰っぽくやるのもありだと思うんだけど、結局メモチェックがTLのネックそうなので速くなるか微妙でやってない(まぁ間に合えば何でもいいので)
まとめ
そんな悪くないんじゃないかな?
1人でも5hバチャはあっという間でした。