はじめに
ICPC（国際大学対抗プログラミングコンテスト）という大会の2023年度国内予選に参加しました。私たちのチーム「AMATSUKAZE」は国内10位の好成績を収め、11月に行われるアジア地区大会への出場権を手にしました。やった〜！
チーム結成から国内予選前日まで
ICPC2023 には AMATSUKAZE というチーム名で noya2, shobon,ebi の3人で参加しました。
ebi さんは修士1年で早生まれではないため、今年が最後のICPCです。shobonさんは学士3年、私noya2は学士2年ですが、3人ともアジア地区大会への出場経験はありません。
~3/24 noya2 と shobon が yukicoder で共同コンを開催
2023年に入るまでは shobon さんとはお互いのことをよく知らなかったのですが、1月に私から shobon さんに共同コンテストの開催を持ちかけ、結局 3/10,3/24 に yukicoder380,yukicoder382 の開催に至りました。その過程で shobon さんとはかなり仲良くなりました（とはいえ discord 上でのコミュニケーションがほとんどでしたが）。
4/13~4/14 ebi さんからの熱烈プロポーズ
ebi さんとはTTPC2022の開催時に多少仲良くなってそれっきりだったのですが、CPCTF 開催にあたって競技プログラミングの問題(PPC分野)の作問作業をしていくうちに再び ebi さんと話したりﾝｺｿﾊﾟのことで助けてもらったりしてまた仲良くなりました。
進級して ICPC のことも考え出すようになっていたころ、ebiさんにICPCのチームを組まないか、と誘われました。夜ご飯にも誘われてしまって、熱烈なプロポーズを受けちゃいました。そのころ自分は tonosama の tatyam さんが抜けた枠に入りたいとか思っていましたが、tonosama の一員である ポテロングさんに相談したところ、別の強い人と組んだということでした。でもこんな嬉しいメッセージをもらって、自分たちも熱烈精進しちゃうぞ〜！という気持ちになりました。
いったん保留しておいた ebi さんからのお誘いを受け入れ、チームを組むことにしました。3人目としては精力的に競プロに取り組んでいる shobon さんが適任だろうと思い、お誘いすることにしました。shobon さんに快諾していただき、チームが結成しました。
チーム名決め
チーム結成後まもなくして、チーム名決め会議を3人で行いました。かっこいい感じのチーム名を考えたいですが、なかなか思いつかなかったので chatGPT くんに聞きました。
ebi さんが 天津風 を激推ししたので、これになりました。聞けば全部大文字がかっこいいとのことなので、チーム名は AMATSUKAZE に決定です。
4/17~ チーム練習
週2のペースで国内予選と模擬国内予選のバーチャルコンテスト（バチャ）を走りました。結局、国内予選本番までに合わせて 21 回のバチャを走りました。バチャを走るうちにチーム全体としてのムーブの練習はもちろん、必要なライブラリの肌感も分かってきたし、お互いの得意分野も見えてきました。個人的には幾何が大好きになり、そこそこ普通の幾何は手に届くどころか楽に倒せるくらいになりました（なったと思っているだけかも）。また、HUPCのほぼICPCルールの回はチームで参加するなど、チーム全体での精進はかなりの量をこなしたと思っています。
個人としても、AtCoder,CodeForces の Rated は全員出るのはもちろん、ebi さんは構文解析の問題を重点的に練習したり、shobon さんはフローや形式的冪級数の問題を重点的に練習したり、バチャで解き切らなかったもので自分の得意分野だったものは upsolve しておくなど、そこそこ十分な対策ができたと思います。
ライブラリ
チーム全体で GitHub でライブラリを管理しました。コンテストで要求されるたびに追加していきました。また、要求されなかったものの出る可能性のありそうなものや出たときに空書きしたくないものを、思いつく限り追加していました。
キーボード
練習が始まる前は ebi さんと shobon さんはキーボードはJIS配列を使っていましたが、この先を見据え、チームとしては US配列のキーボードを使おうということになりました。自分は UC配列ユーザですが、チームで使うキーボードの矢印キーの位置が遠すぎて、なかなか慣れませんでした。
6/24 模擬国内予選
模擬国内予選は国内予選の2週間ほど前に行われました。大学の演習室にあるPCから参加する予定でしたが、PCがキーボードをうまく認識してくれず、JIS配列としか解釈されませんでした。この時は仕方がなく別の方法を探していたところ、日本語入力ではなくポーランド語入力として使えばUS配列として使用するのとほぼ同じ動作をすることがわかり、これで一時凌ぎということにしました。なにをやってるんでしょうか。
コンテストの方は、体感ではかなり失敗寄りでした。C問題で無駄に誤答してしまい、他の問題の実装にも手間取ってしまいました。自分のパフォーマンスがそこそこ悪く、あまり手応えは良くなかったのですが、結果としては 12位（ゲストチームを除く予選出場チームのみの順位で8位）の成績を残すことができました。ここから模擬国内予選には参加していないチームを加えて、本番はどうなるやら、という感じです。
7/7 国内予選当日
前日は早寝(24:00)しました。早起きとはいかなかったですが、十分な睡眠をとることができました。開始 3 時間前に会場入りし、リハーサルを行いました。印刷機やエディタが動くことの確認や、キーボードを変更を行ったのですが、なぜかキーボードがUS配列として解釈されたので、ちょっと得した気分です。
本番の初動は模擬国内予選のときとあわせて3時間くらい練習しました。code touch diff cat などのコマンドは多く打ちました。
alias g++=...などとしてエイリアスを貼る。touch temp.cpp->tempにテンプレートを書く ->cat temp.cpp > a.cppなどとして問題ごとに提出ファイルを作成する。g++ a.cpp->./a.out < A > Aans->code Aansとしてまともな値が出力されているかを確認 -> 提出する。- WAが出たあと改善したコードを提出する時は
diffコマンドを使って出力する値に差が出ていることを確認する。
また、印刷デバッグの練習もしました。自分の学籍番号を用いて刷ることのできる枚数は年間200枚までと決まっていましたが、あまり気にせず使ってしまいました。まぁええか。
そうこうしているうちに本番が始まりました。
初動
担当: ebi
ebi さんがディレクトリを作る・vscode を開いてテンプレートを書く・エイリアスを貼るなど、問題を解くのに必要そうな設定をしました。
A問題 AC
担当: shobon
ebi さんの初動の際に画面の右半分でA問題を見ていましたが、「自明です」とのことでした。初動終了後すぐに実装し、すぐに通りました。
B問題 AC
担当: noya2
画面右半分でB問題を見ました。はやく問題文の印刷終わってくれ〜。あみだくじのシミュレーションは swap で簡単に実装できるので、本当に全探索するコードを書きました。意外に難しかったですが、そこそこすぐ実装が終わり、バグもほぼなく、すぐに通りました。
C問題 やばすぎ！
担当: shobon/ebi
紙の問題文が届きました。普通に難しいそうです。初動を終えた ebi さんとA問題を通したshobonさんが自分がB問題を実装している間に考察をしていましたが、なかなか詰められないようです。自分はそれ以降の問題に目を通したかったのでスルーしてD問題に行きました。2人は嘘を生成しては指摘し合い、実装も大バグり、阿鼻叫喚、という感じでした。自分も首を突っ込もうかと考えたのですが、みんなで沼にハマるのは良くないと思って最後まで2人に任せることにしました。assert を真面目にやれば防げたはずですが、安易に提出してしまい 1ペナルティをくらってしまいました。「20分でアサーションが書けるなら書いたほうがいいです」ともっと主張すればよかった...反省です。
D問題 なんか解ける
担当: noya2
30分ほどうなりながら考えていたのですが、何も出てきません。そもそもまともに解ける気がしません。半分全列挙とか、そういう賢い全探索系を考えていたのですが、はじめは並列考察してくれていたebiさんもC問題につきっきりで、自分にかかっているなというプレッシャーもあったので、なかなか良い方法を思いつきませんでした。そこでふと愚直の計算量を解析してみると、余裕で間に合うことがわかります。良い計算量を実現するにはそこそこ枝刈りを真面目にやる必要があるのですが、丁寧に実装することでぬるっと通りました。2人はまだC問題と格闘していましたが、4完が見えてきて少し心の余裕が出てきたようです。開始1時間後くらいのことでした。
C問題 なんとかAC
アサーションを書くことはジャッジを書くことと同じなので、ebi さんがアサーションを書くことになりました。これのおかげで解法のバグと実装のバグをついに解消し、提出、ACしました。なんとか2人の努力が報われてよかったです。ようやくチーム全体で調子を取り戻してきました。
この時点で、ホスト校枠での通過はほぼ確実でした。それでみんな落ち着くことができたと思います。しかし、上には同じ東工大チームの acidrain と Bocchi The Tech がおり、このチームたちを抜かしていかなければという焦りもありました。
E問題 解けそうで解けない
担当: shobon/ebi
自分も問題は見て多少考察をしたのですが、愚直な 3 乗のDPしか思いつかず2人に投げてしまいました。どうやら、えいえいやると になるようです。定数倍がかなり重いがぶん回せば通る、くらいの感じだったと聞いています。しかし、DPの遷移がふわふわしていて、まだまだ詰まりきっていないようです。F問題もおおよその考察は浮かんでいたのですが、嘘の可能性も多くあり、正しいと分かっているものを実装したほうがいい、という判断でE問題のラフな実装をしておいてもらうことにしました。
F問題 丁寧に考察 AC
担当: noya2/shobon
どう見ても幾何だったので、自分が担当しました。まず、サンプルの2は不可能なのにサンプルの1,3は可能であることが非自明です。これの考察をします。凸包に接している辺の存在がキーであると、直感がそう言っています。そこで与えられた図形の凸包をとり、それの有限回の重ね合わせである凸包ができたと仮定すると、辺の傾きの順番はもとの図形のそれと一致することがわかります。そこから、凸包から凹んだ部分を埋めようとすると凸包の角から直接凹んでいる箇所があってはならないこと、そういう箇所がなければ適当に貼り合わせればその凹みを埋められそうであることがわかります。ここまでくればあとは実装です。凸包ライブラリを当然持っているので、shobonさんにタイピングゲームをしてもらいます。
shobonさんは補完を使わずにすべて直打ちするので、写経がめちゃくちゃ速いです。実は、長めのライブラリが必要になった時は shobon さんに写経をお願いしています。
また、後から思えば博打でしたが、速度勝負だと踏んで整数幾何で使用するベクトル構造体を書かず complex<ll> で代用しました。std::complex は浮動小数点数型以外での使用は非推奨のはずですが、事前に T の範囲で済む演算しかしない場合は complex<T> が期待通りに動きそうということは確認していたため、うまくいくだろうとは思っていました。実際、この問題ではうまくいきました。
意外にも凸包の角ではないが凸包に含まれる点、みたいなものを処理するのが難しく、慣れない処理を書いたので、かなり時間がかかってしまいました。その間、「E問題のDPの遷移は詰められましたか？」とか聞いた覚えがありますが、まだまだダメっぽいということでした。ぬるぬる印刷デバッグをし、トイレに立っているときに大バグに気づき、E問題のラフな実装を書いていた shobon さんを突き飛ばし（てはいない）、急いで修正しました。その後いくらか粘ってサンプルを合わせ、1ファイル目を出すと、なんとAC！解法が正しいことを確信して2ファイル目もACしました。終了30分前くらいのことです。
E問題 バグだらけだが動きそうなコードができる
shobon さんがえいえい実装をして、計算量が怪しいがなんとか動くコードができました。が、一向にサンプルが合わないようです。その後、自分はやめたほうがいいとは思いながら、添字ガチャをすることになりました。自分は解法について何も聞いてないので、ほぼお祈り状態でした。口もあまり挟まないようにコードを眺めていました。なんとかサンプルがあったものの、計算量がおしまいになってしまっていたようで、1ファイル目の1ケース目の実行の時点であまりにも実行が遅く、時間内の終了はほぼ絶望的でした。この時点で残り20分ほどでした。
E問題 感動のフィナーレ
奇跡が起こります。 ebi さんが計算量を落とす方法をひらめきます。すぐに shobon さんから席を奪い、実装をし始めました。自分はもう何がなんだかわかりませんが、ebi さんに賭けるしかない状況、祈りを捧げるばかりです。まもなくして実装が終わり、再び1ファイル目の実行を開始します。するとなんと！そこそこ（ほんとうにそこそこ）実行が進むではありませんか！体感で5分ほど実行し、1ファイル目の出力が終了しました。提出するとなんとAC！（自分は驚きましたが、後から聞くと素直なDPをしたので実行時間だけが問題でACするとは思っていたそうです。）その後すぐに2ファイル目の実行をぶん回し、終了およそ5分前に実行が終了、提出しACしました。このときばかりはチーム全員で大声をあげてしまいました。すぐに静かにします。最高に気持ちよかったです。
終了まで
終了直前、我々 AMATSUKAZE の順位は 10 位でした。東工大内では tonosama に次ぐ 2 位です。10 位以上は無条件で国内予選突破なので、この順位をキープできることを祈っていました。結局、下位のチームからの追い上げから免れ、10 位で終了することができました。ラッキーです。
終了後
東工大からはおそらく 4 チームが国内予選を突破したようで、嬉しさ満点でした。自分は熨斗袋さんにサインをもらいにいきました（ファンなので）。アイコンを描いてもらいました。感動です。すこしみんなで感想戦をした後、会場を後にしました。その後、順位表を観戦しながら応援してもらっていた友人と合流して夜ご飯を食べに行きました。今後の traPアルゴリズム班としての活動の進め方についての議論も盛り上がり、楽しい夕食でした。
振り返り
チームが結成したときから、練習に大量の時間を避くことを念頭においていました。大学生ともなれば忙しい人も多くいると思いますが、そんな中でもチーム3人が全員コンスタントに練習に参加できるというのはとても有利に働いたと思います。これはひとえにみんなの競プロに対するモチベーションが（異様に）高かったおかげだと思っています。20回以上もバチャで練習を重ねた、というのも大きな自信になりました。また、バチャ終了後には毎回夜ご飯を食べに行き、解説を見たり復習や解法共有をしたりと、多くのコミュニケーションをとってチームの仲を深めることができました。そのおかげか、チームが総崩れにならずにすべてのバチャおよび本番でそこそこの成績を出せました。
さいごに
応援してくれた方、ありがとうございます！
アジア地区大会に向けてさらに頑張ります！
今後とも応援よろしくお願いします！
