はじめに
こんにちは、ひらくと申します。大学に入ってから競技プログラミングを始め、日々精進しております。jackでも競プロがじわじわ流行り始めていて、うれしい限りです。
今回のアドベントカレンダーでは、先日行われた「ICPC Asia Yokohama Regional 2023」に参加してきたので、その参加記を書こうと思います。
ICPCとは
ICPC（International Collegiate Programming Contest）は、国際的な大学対抗のプログラミングコンテストで、毎年世界中から数万人の学生が参加しています。同じ大学の学生3人とコーチ1人でチームを組み、国内予選を勝ち抜いたチームがアジア地区予選に出場でき、さらにそこで勝つと世界大会に出場できるという感じです。
私たちのチームは幸運にも国内予選を通過できたので、アジア地区予選に出場することができました。
チーム紹介
NUCODER_Aというチームで出場しました。（NUCODERは名大の競プロサークルです）
メンバーは僕（B3）とmono（B3）（明日彼の記事が出ます）とNUCODERの先輩（B4）の方でした。コーチもNUCODERのM2の先輩にお願いしました。
day1（11/25）
この日はオリエンテーション、リハーサル、チーム紹介がありました。
アジア予選なので、スタッフからのアナウンスや会話は全て英語で、びびりました。
リハーサルでは、PCのセッティングや解答の提出を一通り試しました。問題分も全て英語なので、そもそも理解するところから一苦労です。
リハーサルの問題は全部解きたかったのですが、最後の問題で parallel (平行) を 交わる と勘違いして、最後まで気づかず解けませんでした。（サンプルを見れば一発で気づけたのに…）
普段の日本語のコンテストですらよく誤読をするので、英語ならなおさら慎重にならないといけませんね。
チーム紹介では、各々スライドを1枚作成し、それを表示しながら英語で30秒ほどのスピーチを行いました。先に登壇した名大のもう1つのチームから少し煽られたので、アドリブで煽り返したら、微妙な空気になったのを感じたので、来年は真面目にやろうと心に誓いました。
リハーサル後は名大のもう1つのチームと一緒にご飯を食べに行きました。海沿いのテラス席でイタリアンという優雅なものでしたが、実際は寒すぎて震えながらピザを食べました。味はとてもおいしかったです。
その後は、ホテルでABCのA~E問題を英語で解いて、明日に備えて早めに寝ました。
day2（11/26）
本番前
朝は7時に起きて、8時半には会場入りしました。
いっぱい重ね着していたせいで、名札と学生証をどのポケットに入れたか分からなくなり焦りましたが、何とか会場にたどり着きました。
コンテストまでの30分で軽く作戦会議をしたり、用意されていたお菓子を食べてました。
練習とかをちゃんとやっていたわけではないので、かなりぶっつけ本番感がありました。
本番
結果から言うと、ABFの3完47位でした。
自分が担当して解けた問題（A, F）について、何をやったかを書こうと思います。
A問題はマス目上に Y, O, K, H, A, M のどれか1つが書かれており、通ったマスの文字を並べたときに ”YOKOHAMA” になるたどり方が何通りあるかという問題です。（一度通ったマスに戻ってもOKです。）
上の図の例だと、赤線のようなたどり方が全部で8通りあります。
自分は深さ優先探索（DFS）で解きました。具体的には「Y」が書かれているマスから始めて、隣接するマスで次の文字に対応するものがあればそれに移動していくという感じです。
ただDFSはあまり得意じゃないので、案の定バグらせました。
解説や他の方の参加記を見ると、動的計画法（DP）で解いたという方が多かったので、DPを選択するべきだったなあと思いました。複数の解法がある場合は、自分の得意な実装を選べるようにしたいですね。
F問題は マスのチェス盤の行または列の色を反転させるクエリが与えられ、クエリごとに同じ色でつながった領域がいくつあるかを答える問題です。
例えば3×3の場合を考えます。最初は白と黒が交互に塗られていて、領域の個数は9個です。1つ目のクエリで2行目の色を反転すると、2つ目の図のように縦に白黒白と並んだ形になり、領域は3個になります。それ以降のクエリも同様に処理していくと領域の個数は、2個、6個と変化していきます。
この問題は という制約があるので、チェス盤の各マスの色を配列等で持つことはできません。
そこで、各行では1つ上の行、各列では1つ左の列と反転した回数の偶奇が一致しているなら1、そうでないなら0を持つことにします。最初はどこも反転していないので、すべて1です。
各クエリでこの値は、行なら反転した行とその1つ下の行、列なら反転した列とその1つ右の列の01を反転させることで更新できます。
そして、領域の個数は行の合計と列の合計の積で求めることができます。
これ以外の問題は、D問題は数字が1桁じゃないといけないという条件を見逃したり、E問題は計算量が落とせなかったりと、3時間半くらい椅子を暖めるだけになってしまいました。。。
そんなこんなでコンテストは終了。５時間は長いと思っていましたが、あっという間でした。
コンテスト終了後は、作問者からの簡単な解説と順位発表がありました。
順位発表では残り１時間の提出で各チームがACしたかどうかが Yes/No で発表されていきました。司会者がYesと言うたびに順位が変動し、会場からは拍手が起こっていて、とても盛り上がっていました。最後に１位のチームが全問正解していたことが分かった瞬間は、その日一番の盛り上がりでした。
その後の懇親会では、名大のチームと話したり、企業のブースを見たりしていました。生chokudaiさんが見れたのは感動でした。
帰りの新幹線では、ICPCの反省会をしたり、前日のABCの問題を話し合って考えたりしていました。コンテストが終わっても、競プロ熱が全然冷めず、すごい大会に参加できたんだなと改めて感じました。
感想
正直、今回のICPCは、初めての参加というのもあり、勝手がわからないことが多く、悔いが残る部分が多かったです。
ただ、出場できただけでもとても貴重な経験になりました。今回のICPCでかなり競プロのモチベが高まったので、来年にはもっと強くなって、より良い結果が出せるように日々精進していきます！
NUCODERの宣伝
NUCODERは名古屋大学の競技プログラミングサークルです。現在の主な活動はAtCoderのコンテスト終わりの感想戦と定期バーチャルコンテストです。競プロに興味がある方は是非discordにご参加下さい！！！！
参考
おすすめ記事
