ICPC2023国内予選にkyaさんとnattonatoさんと３人でチームtriC_Hinoから参加し3完58位でした。まだ確定してはないですが地区予選に進めそうなので嬉しいですアジア地区予選確定しました！やったあ！準備したこととか模擬国内、国内本番の話を書きます。
準備したこと
基本的には週１でチームで集まって過去問を本番と同じ環境で解く練習をしました。今年のルールは３人で１台しかパソコンが使えないので誰が実装するかその間どうするかとかを考えました。
個人としては構文解析の対策を重点的にやりました。構文解析の対策をしている人が誰もいなかったのでアジアのボーダーになってくるC問題やD問題で構文解析が出た時に対応できることを目標に勉強しました。
使ったサイト
はまやんさんの問題まとめのほうは半分くらいしか解けなかったので今後またチャレンジしようと思います。とりあえずBNF(Backus-Naur 記法)から構文木を構築し可換群なら２分木にしたりとかはだいたいできるようになりました。ただ、構文解析の問題は構文木にしてから探索したりする部分も大変だったりして、木にした後ができない問題もままあり今後の課題かなと思ってます。
また、構文解析の問題はマクロ定義とか除いてもコードが300行くらいになってしまう問題も少なくなくやってるうちに実装力がついた気はします。
・構文解析の問題例
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=ja
まあ本番はボーダーラインの問題にはでなかったのでちょっと残念というか、出てもできるか怪しいので出なくて良かったというか...
模擬国内
模擬国内は3完50位でした。B問題を担当するも途中で浮動小数点つかってバグらせ変わってもらったり、D問題をDPで押し切りたかったものの定数倍を落とす工夫が思いつかず実行が数時間かかってしまい解ききれず個人的には残念でした。
できなかったD問題を後輩が畳み込みを使って解く解法で通してて、解説してもらいすげーとなったんですが、いかんせんフーリエ変換周りがあんまり分かってないのですげーとしか分からなかったので勉強しておきたいです。
国内本番
本番当日は始まる３時間前くらいに会場の研究室に行ってライブラリを印刷してもらったりPCの環境の準備をしました。マウスとキーボードはkyaさんがゲーミングな光るやつを持ってきてくれたのでずっと光っててよかったです。
監督員としてお願いしていた先生が「定刻に向かいます」との話だったのですが、本当に本番が始まる16時半ぴったしに来たのはとても焦りました。とはいえ大会中、3時間もいなきゃいけないのに監督員を引き受けてくださって感謝しかないです。
本番が始まったらnattonatoさんにAを通してもらいその間に自分がBを読んでると、Cがパズル問題で誰がやっても変わらなそうということとBが適当に全探索すれば通りそうということが分かりBを実装の速いkyaさんに任せてCを考えることにしました。
C問題はnattonatoさんが行だけで完結する操作を行ごとに行いそれを列に対してもおこなえば良さそうという方針を示してくれたので行で完結する操作を考えました。すると奇数番目と偶数番目のグループに分けて奇数番目を前に偶数番目を後ろに持っていけば条件を満たすと気づきそれを実装して通しました。実はこの解法が解説解とドンピシャで一致していたこともあり実装も大したことなくCをかなり早く通せました。
残りの時間はD問題を考えていて、チーム内で
・2^nの和を考えると必要な問題の数は最大7個
・6個でできるかが分かればいい
というところまで分かっていて、計算量が100C6 * 100くらいから落ちず悩んでいたのですが、なんと３人共配点の合計が満点に等しいという条件を見逃していることに終了15分前に気づき、現実的な時間で解ける方法が思いつくも流石に間に合わず３完で終了になりました。
反省点としては最初に問題が両面で印刷されてしまい、ちょっとやりづらいけどいいかと思ってそのままやっていたのですが、余裕のあるタイミングで全員分片面で問題を印刷し直しておけばもしかしたらもう少し早く気付けたかなと思いました。
結果的には誰が実装するかという作戦と運が噛み合い３完早解きができたのでまあよかったかなと思ってます。アジア地区予選に向けてまた頑張りたいです。
(首都大学東京じゃなくて東京都立大学なのでそれもいつか直って欲しいですね。個人的には首都大学東京のほうがかっこいい気がするのでこのままでもいいのですが)
