トップ > ICPC 2021 国内予選参加記

ICPC 2021 国内予選参加記

 

KyopRo-jinで出場していました。5完20位、学内3位なので、今年は通過出来ていそうです。良かった。

 

まずCを見る。
30分くらい考えたが回転操作の扱いが何も分からない。根が動かなければ木DP（というかDFS）で終わりなんだが...
気が付くとAが通っているのでACが出ているDを見てもらうことにする。B書き終わったので提出してくれと言われる。残り二人とも大きいデータを入力できる環境が無いらしい。ちょっと手こずりながらもBもAC。ここまで25分くらい。

気合を入れなおす。回転操作の後に入れ替え操作をする手順は、入れ替え操作を先にやったことにしても良いので、入れ替え操作=>回転操作の順だけ考えれば良いと考える。
この結論自体は役に立たないけど、入れ替え操作を先にやったことにしても良いので任意の頂点を根にできることに気が付く。

これは全方位木DPなので頑張って再帰関数を書きまくると通る。ここまでで75分くらい。

https://atcoder.jp/contests/chokudai_S001/submissions/27049817 （履歴から復元したので微妙に不完全かもしれない）

 


この段階でBも通っていてDを二人がかりで考察しているが、嘘貪欲でWAを出しただけで進展が無いらしい。問題の説明を受けるも僕も分からない。Dは他のチームが解けている問題なので焦る。

分からないって言ったらEは実装が面倒だけど解けてそうなので書いてと言われる。残り二人には引き続きDを見てもらう。
Eはタクシーを使う数で場合分けすると良いらしい。なるほど。
サンプルにタクシー沢山使わないといけないケースが無いの悪意がないか？って言いながら書き終わる。提出しようと思ったら出力にINFが残っていることに提出前に気が付く。ここまで120分くらい。

このあたりでDが通って、順位表も見て3人でデバッグ。
タクシー使用回数が0でゴールに行けるはずなのに使用回数50回以内で到達できないことになっていて、使用回数50回以内でのダイクストラの部分を見るがバグっているように見えない。
サンプルを抽出しようとしたものの、入力テキストが大きいので苦戦。デバッグ出力を入れたとき、ついでにワーニングを思考停止で潰したらその直す操作で未定義動作踏んでしまい悪戦苦闘。

なんとかサンプルを抽出すると、「タクシー使用回数が0でゴールに行けるはず」の方が間違っていることが判明。

直して提出したらWA。
タクシー沢山使わないといけないケースの方の計算で、(1<<taxi)のつもりでpow(1,taxi)を書いていた(提出の434行目)。サンプル強くしてくれ～～
直してAC。ここまで160分。

本番ではすんなり解いたつもりだったけど、振り返ると時間かけすぎかもしれない。関係ない未定義動作踏むくだりとpowのWAのくだりは完全に要らなかった。
https://atcoder.jp/contests/chokudai_S001/submissions/27039170


この段階で5完20位、学内3位でギリギリ通過圏。ABDのペナが他と比べて大きくEも時間かかっているので、学内4位がもう一問解いてきたらペナ差でギリギリ負け、学内4位になって落ちそうという話をしていた。
残りはもう解けないだろうと祈祷フェーズのつもりでFを考えていたら、意外と考察が進んでしまった。解ききれはしなかっただろうけどちょっと悔しい。