Australia

ウォンバットのブログ

ICPC2020 国内予選 参加記

ぴーよ (holeguma) さん、まさよし (masayoshi64) さんと組んでチームPWMtreeで出ました。5完20位でした。

回想

僕は高専から大学に編入しました。高専ではICPCには出ていません。理由としては国内予選に通る自信がなかったこと、参加する文化がなかったこと (岐阜高専からICPC参加したチームって今までにあるんでしょうか？)、忙しかったことなどが挙げられます。

大学に入って、ICPCに出てみたいとはぼんやり思いつつも、界隈に親しい人がほとんどおらず、数少ない友人を誘ってチームを結成するバイタリティもなかったので、まあ今年は出ずに終わるんだろうなと思っていました。そんな僕をぴーよさんが拾ってくれました。

チーム練

*UPCの類にいくつか出ました。過去のセットを使ってバチャをやりたいですね、という話はしていましたが、やり方がよくわからずズルズルと来て結局本番1週間前に1回やっただけでした。

本番3日前

というわけで構文解析担当になってみました。構文解析の概念を学び、何問か通しました。

本番

始まった！ と思って問題を見ようとしたら開けなくて草を生やしていました。

しばらくしたら復旧したので、予め決めていたとおりBを見ました。問題文がなかなか頭に入ってこずに苦労しましたが、普通に実装して通りました。
先にAを通したぴーよさんがDが構文解析だと教えてくれました。一点読み成功！ しかもDという丁度解けそうな位置。

意気揚々と取り掛かりますがなかなか解けません。構文解析自体は本質ではないようでした。このときCも詰まっていて、まさよしさんとぴーよさんが色々やっていました。

悩んでいるとこれがよぎってDの解法が生えました。結局全探索を回すことにしたらしいCと同時くらいに通りました。

Dが通った時点で既にぴーよさんまさよしさんがFの考察を終わらせたらしく 、ぴーよさんが実装をしていました。僕とまさよしさんでEの考察をしました。
しかしこれが全然解けません。グリッドグラフの独立集合を数えればいいんですが、斜めに区切ってDPをすると状態数が1.618^30くらいになるし遷移も厳しそうです。他にもいろいろ試しますが、悉くダメ。

さらにFがcase2で落ちたという報告がなされ、肩を落としました。それでもまさよしさんとEの考察を続け、いやこれ縦で区切れば状態数2^15で抑えられるやんけということがわかって草を生やしました。高速ゼータ変換を使えば遷移できるということもすぐにわかりました。僕が実装を始め、まさよしさんにはFのカバーに入ってもらいました。この時点であまり時間が残っていなかったのでかなり焦っていました。

Eの実装を進めようとするのですが、マジで頭が回りません。細かいところがめんどくさいタイプの実装だと思うのですが、1行書く度に次に何を書けばいいのかわからずまごついているような有様でした。

そうこうしているうちに、Fで解答ファイルを取り違えていたことが発覚したようで、投げ直したら通ったようです。あとはEを通せば！ 焦れば焦るほど手は進みません。こうしてコンテストが終了しました。

今順位表を見直して気づいたのですが、Fが通ってからまだ20分残っていたらしいですね。本当に僕は何をしていたんでしょうか？ しかもこの時苦し紛れに書いた高速ゼータ変換のコードですが、余裕で間違っていました。(ライブラリに、入れましょう)

感想

20位は健闘した方だと思うのですが、やはり悔しいです。自分は残り時間が少ないとべらぼうに弱くなる、ということが再確認できました……。

とはいえ、ちゃんと全力を出して燃え尽きた感はありますし、本当に楽しかったです。来年もこのチームでやろうという話になっているので、是非リベンジを果たしたいです。

チームメイトのお2人、コーチをやってくださったすぎやんさん、ありがとうございました！