ICPC2019 国内予選 参加記
チームdefine_mod_31536000で参加して、全体40位、学内1位でした。個人的に任意を差し置いてでもアジアに行きたかったので、チームメイトに感謝しています。cirno3153とbanboooo044とclaw88で出ました。
プラン
実装がボトルネックになるチームですが、4完すればいいので1問ずつ確実にやる。ペナルティは気にしない。
コンテスト
会場のチームにまとめて問題文を印刷してもらうはずだったのですが、印刷がうまくいっていないようでみんなでAを読んで通す。mが縦なのに注意。
「複数のセルが同じ文字を含むことはない．」の意味がわからなかったので、banboooo044にBFS書いてくれというオーダーを出した。添字ミスなどが怖いし、あまり慣れてなさそうだったので口出ししながら書いてもらってAC。
cirno3153がDを考察していたので、Cを書く。3進数をやった後にどうするかがわからなかったので、3人で相談。mapとかsetとかいろいろ使ってAC。実行時間1分ぐらい。
cirno3153が、dp[i,j]：i番目のものをj回ループしたときの最小回数 だと言ってきた。それには同意できるが、jの最大値(=J)を何にすればよいかがわからなかったので、とりあえずJ=3にしてO(NJ2)を書くとサンプルが通るがWA。cirno3153がどんなに多くてもJ=Nと言ってきたので信じて実行するとAC。実行時間2分ぐらい。
claw88にはEをやる体力が残っていない。終わり。
感想
Dに関しては運が良かった面がある。初めからJ=Nと理解しているとO(N3)を書くのに躊躇したかもしれない。
4完にすべて関与したが、チームでC,Dを通したところがとても良い。
