ICPC模擬国内予選2019 参加記
ICPC模擬国内予選2019にチームEldoradoで参加しました。
ABCD4完で順位は参加資格有17位でした。
コンテスト中の動き
Aをmhrbさん、Bをニクローさん、Cを僕が読む。
Aをmhrbさんが一瞬で通す。Bの考察が完了しているそうなのでニクローさんが実装に移る。
僕はCを読み終わるが方針は立たず… なのでO(1)かなあと思いつつ、mhrbさんにCの概要を伝える。すると、偶奇で場合分けでいけそうと返答が来る。聞くと割と正当性がありそうなのでCをお任せする。
Dを読む。ほぼ編集距離を求める問題だけど最後のローテーションの処理が分からない... とりあえず蟻本で編集距離のDP実装を探すが載っていなかったので思い出す。
このあたりでニクローさんがBを通す。mhrbさんがCの実装するがWA。(0,0)の周囲8マスに目的地があるときの処理が抜けていたそうなので、修正してもらうとAC。注意力問題だった。
Dで先にxをk回ローテーションしてから編集距離求めればいいのでは？と思いつく。なんとなくよさそうなのでとりあえず入力と編集距離DPを書く。が、文字を消してからローテーションするとコストが減るという反例が見つかる。ふりだしに戻る。
ここからしばらく苦しい時間が続く。僕はDの考察。mhrbさん、ニクローさんがE以降を読む。E以降でもぱっと解けそうなのは無いらしく厳しくなった。
yのほうをローテションしておけばいいのではと思いつく。とりあえずこれを書いてみると多少の修正(添え字ミス、AとEの入れ替えなど)を経てそれらしい解が出るようになる。しかしサンプル3が合わない。手元でやってみると、結局途中で文字を消してローテーションの回数が減るパターンが考慮できておらずだめだった。
なにもわからないので菓子パンをほおばる。すると、ローテーション範囲にある文字を消すときはR一回分浮くのでは？？と解法が降ってくる。すごくいけそうな気持ちになったのでコードを修正するとサンプルが合う！キタ！
お祈りしながら提出すると無事AC！ちょっと声を出してしまった。
この後はHが見た目解けそうとのことだったので全員で考察する。愚直DPは流石に計算量がやばそう… 効率的な解法が浮かばないが取り合えず愚直DPを書いてもらう。テストケースを実行するも残念ながらコンテスト中に処理は終了しませんでした...
感想
Cまではまあ良い感じだった気がします。Dは解法ガチャでなんとかあたりが出た感じなので本番これだと怖いなあと思いました。
新入生チームがB,Cあたりまで解いたらしく強いなあという気持ちになった。
