見出し画像

ICPC国内予選2024参加記

にころ

はじめに

こんにちはにころ（nikoro256）です！！！
先日、ICPC 国内予選という大会に参加してきました。

ICPC国内予選とは？

International Collegiate Programming Contest (国際大学対抗プログラミングコンテスト、ICPC)という競技プログラミングの大会の予選です。

ICPCは大学生限定の競技プログラミングの大会としては最大のものであり、ここで結果を残すことを目標にしている大学生競技プログラマーも多いと思います。

チームメンバー

※()内はAtCoderのIDです。

・にころ (nikoro256)
僕です。AtCoderのレートは青でチーム内では一番上です。素早く実装することが苦手で、動的計画法が得意です。
・Cecil (trkwm)
友人です。AtCoderのレートは緑でチーム内では３番目ですが、図を綺麗に整理したり人に考察を伝えたりするのが上手いです。
・Suzux (Suzux)
友人です。AtCoderのレートは緑でチーム内では２番目です。素早く実装するのが上手です。

前日談

みんなインターンの選考や課題等で忙しく、昨年ほど練習の時間は取れなかったのですが２回練習をすることができました。

１回目の練習

昨年の練習で解いていなかった2021年のICPCを解きました。
結果は惨敗。昨年参加した時と同じ２完でした。
(~2023の予選突破のボーダーは3完早解きもしくは4完のため全然基準に届いていません。)

ICPC2021のバーチャル参加

原因は自分がCで方針を詰め切れず実装をしてしまい、沼にはまってしまったことでした。（Dも解けませんでした）
今年も予選突破出来ずに終わってしまうのでは？
と不安になる結果に終わってしまいました。

２回目の練習

バイトが被っていたため、不参加だった模擬国内予選を行いました。
今年のICPCと模擬国内予選は簡単な問題が１問増えているためボーダーは４問早解きか５問と予想されます。

結果はABDEの４完。早解きなら予選突破の可能性がある結果となりました。
（しかもCは自分が事前に解いてしまっていたため、手を付けないという縛りでのこの結果でした。）

リハーサル

本番では問題のテストケースをダウンロードし、プログラムから答えをテキストファイルとして出力し、提出しなければなりません。
本番と同じ入出力形式の練習が出来るリハーサルに参加しました。

入出力形式でややチームメイトの二人が詰まっていたので不安があったのですが、ファイル入出力部分のサンプルプログラムを準備しておくことで対応しました。

本番

遂に本番がやってきました。16時に監督の先生の研究室に集合だったのですが僕とSuzuxは遅刻してきました（汗
弊学（上智大学）は今年は１チームのみの参加となりました。

16:30開始なので用意したものをチームメイトに説明したり、机のセッティングをしたりして準備をしていました。

Cecilがチョコを用意してくれていました。

↑　今回の問題です。

A問題

監督の先生がコピーをしてくださっている間に、全員でA問題を読み始めました。貪欲でシュミレーションするだけの問題のように見えました。当初の予定通りSuzuxが実装を担当してくれていて4分で実装を終わらせてくれました。

B問題

A問題が終えてもコピーをしてくださっている最中だったため、全員でB問題を見ました。
長距離走で二人の進んだ距離の推移を見て、片方が追い抜く回数・追い抜かれる回数の和を求める問題でした。最初は二人が並んでいるので、追い抜き判定が無い事に注意しつつ、１ターンずつ追い抜き判定があるかどうか見ていけば実装することが出来ます。
Cecilが実装してくれました。

C問題

問題を見た途端 Cecilが「見たことある！」と言っていました。どうやらAtCoderに既出の問題だったようです。

実装は僕が担当でした。
問題を見た時、幅優先探索の解法と、数式で答えを表せそう、という二つのアイデアが思いつきました。本番では後者の方が沼ると判断し、前者を選択しました。
（これはコンテスト後に分かったのですが、数式が簡単な形で落とし込めるため後者で行った方がかなり早く解けていたかもしれません）

幅優先探索の解法は、６角形がしきつめられた図形上で幅優先探索をするだけなのですが、グラフの構築で手間取ってしまいました。
28分も実装にかかってしまいました。（一番の反省点です）

D問題

C問題を解き終わった時点でSuzuxとCecilがDの解法を思いつき終わった空気になっていました。ここまでDがすぐに思いつけた事はなかったので驚きました。
二人に考察を説明してもらうと、AtCoderでも良くあるなもりグラフの閉路検知で、シュミレーションを省略する問題になっている事に気づきました。

実装が少し重い問題でした。実装はSuzuxがやってくれることになり、僕とCecilはEに回ることになりました。

E問題

昨年のCで苦しめられた構築問題の再来で、宿敵に会ったような気分になりました。どの方向から見ても同じ色の配置になるように、正方形のタイルを配置する問題でした。与えられるリストの左端と右端が同じケースは簡単に構築できることにすぐ気づいたため、そうでないケースを二人で考察していました。

具体的なケースより、より抽象的なケースでどうなるかを考えるため、一番左端がうまく構築できる条件を考えてみた所、それが実は必要十分なのではないかと思いつきました。実際その条件で抽象化して図を書いてみたところ、確実に構築できそうであることに気づきました。

ホワイトボードに書いた図



ここで自分とCecilは問題を誤読していて全ての色を使用しないといけないと思っていたため、如何にして無駄な色を真ん中に詰めるかという議論に発展しましたが、しばらくして誤読に気づいたためその議論は必要が無い事に気づきました。

そこまで考えて丁度良いタイミングでSuzuxのDの実装が終わっており、提出した所、見事DのACを取ることが出来ました。

残り時間が１時間ほどであったため自分がEの実装を急いで始めました。

左端と右端が同じケースの実装はすぐに終わったのですが、そうでないケースの実装はかなり苦労しました。特に４方向について、「端のindexをどこにもっていくか」を考えなくてはならずindexのミスで苦労しました。

気づいたら残り20分ほどになっていてかなり焦りがありました。（特に自分はARCなどでギリギリで実装しきれず正答できない時が何度もあったため、それが頭に思い浮かんでしまいました。）
しかし隣でCecilが試すべきテストケースを手書きで書いていてくれたり、答えが合っているか横で確かめてくれたりしてくれ、なんとかデバッグを終わらすことが出来ました。

残り10分で提出した瞬間、問題に正解した事が分かった時は全員で喜び合いました。（順位表的にEを正解できなければ予選敗退、Eを正解出来ればまず突破できるだろうという場面でした。）

ICPCを終えて

最終結果

全体53位で見事に予選突破する事が出来ました！
結果的に練習の時以上の成果が出せました。
方針をしっかり固めて実装が出来たこと、チームメンバーそれぞれが自分の役割をきちんと果たせた事、デバッグをチームメンバーと協力し上手く出来た事が勝因だと思っています。

最後に、応援してくださった弊学の先輩方、コーチ・監督を引き受けてくださった先生、国内予選の運営の方々、本当にありがとうございました。

予選の次であるYokohama Regionalも頑張ります！


いいなと思ったら応援しよう！