以下の内容はhttps://mt-saka.hatenablog.com/entry/2025/08/18/180500より取得しました。


第37回国際情報オリンピック(IOI2025)ボリビア大会参加記

先にこちらの記事を読むことをおすすめします。情報オリンピックとは何なのか、今回大会の情報、日本代表選手の紹介などの内容があります。
mt-saka.hatenablog.com

7/27~8/3に開催れた第37回国際情報オリンピック(IOI2025)ボリビア大会に参加していました。これはこの大会の参加記です。

この記事は春季トレーニングで代表になってからの話、実際に羽田空港を出発してから羽田空港まで戻ってくるまでの話の二本立てです。実際の大会に参加している時の話や感想を見たい方は後半まで飛ばしてください。

日本代表に選出されてからIOIまで

日本代表になった以上は当然目標は金メダルでした。同時に、2022,2023年は4人全員金メダルの快挙だったので今年はそれを成し遂げたいという意欲も持っていました。ただこれは自分が金メダルを取らないと話が始まらないので、基本的に自分が金メダルを取ることに集中していました。

IOIの過去問を本番形式で演習するのに加えて、中国の有志の方が開催していたNOI(日本で言う情報オリンピック本選のようなもの)に向けてのトレーニングに日本代表も参加させてもらっていました。直前期にはQingyuさんが主宰するIOI Trainingにロシア,アメリカ,etc.. の国の代表と一緒に参加させてもらいました。団長のyutoさんをはじめとしたチューターの方々が翻訳やら問題へのコメント/ヒントを下さったりしました。

チューターの方々が予定を立てていたバチャ以外にも自分はここ10年のIOIを全て解き切る(少なくとも満点解法を理解する)ことを目標に計画を立てました。最終的には計画通りにすべてはいきませんでしたが、9年分(IOI2016~)の54問は目を通し、30問は満点を獲得し、50問は満点解法まで理解しました。5年分くらいは期末試験が終わった7月上旬から埋めていたのですが、5hを毎日やる生活習慣になっていました。また、全体的に知識を増やすということはあまりせず、自分の中でなんとなくしかわかってないかもというようなアルゴリズムやらをちゃんと自分の中で定着させることに重きを置きました。実際、IOIに出る範囲というのはsyllabusで定まっていてその知識に穴がなければ基本的に大丈夫です。

また、高山病予防のために心肺を鍛えておこうという思いでランニングを定期的にしていました。出発前2週間くらいは毎日3~4km走っていました。タイムが改善していくのを見て体力がついているという実感が得られてかなり楽しかったです。ボリビアのような高地で開催されるとか関係なくIOIは長距離/長時間の移動、様々なイレギュラーな事、英語で国際交流など疲労がたまる原因はいくらでもあります。ですので、体力をつけておくことは非常に有用であると思います。

IOIの過去問の感触/戦略

過去問を解いていった感触では問題を理解して解けそうと感じた小課題をちゃんと回収しきると金メダルボーダーの少し下くらい。それに+20点できると金メダル圏くらいみたいな感覚を持っていました。つまり、一日は普段通りの実力でももう一方の日で多少相性が良ければ金メダルを取れるだろう。逆に両日多少点数を取り切れなくてもギリギリ銀は耐えるくらいだろうという算段でした。
戦略は基本的に春季トレーニングから変わりません。

  • 序盤15分でパソコンの設定や全問題のファイルやらを準備してテンプレートを書く下準備の時間とする。
  • 下準備が終わってから問題文を初めて開封する。小課題の制約/配点などからおおざっぱに各問題を難易度評価をして(1分以内で終わらせる)簡単なものから目を通す。
  • 各問題を見て取れる部分点をとりあえず実装していき問題を開いてから1時間以内に別のまだ見ていない問題に移る。
  • 後半2時間くらいは取れそうな部分点とかかる実装時間+考察時間をソートして価値が高い順に30分くらいは考えていく
  • 少しでも行き詰ったり時間がかかりそうなバグ取りを始める前はとりあえずトイレに行く。

というような戦略でした。
ですが、バチャでは家でダラダラやってしまっていたのもあってか実装が間に合わないことが多々ありました。なので、春季トレーニングで持っていた1時間の目安を45分に変更してより早くすべての問題を見て、周回する戦略に変えました。IOIはJOI春季トレーニングの一般的なセットより簡単なことが多いのもあって、結果的にこの戦略はパフォーマンスがより安定し、ちょっとした上振れも得点に反映されやすいようなものになりました。めちゃくちゃ相性が良くでポテンシャルを5時間でフルで出し切れば超高得点が取れるようなセット、そもそも250点以上が20人以上いるような高得点勝負だとちょっと不利ではありそうだなと思ったりはしました。ですが、自分の普段通りの実力から少し背伸びすれば金メダルを取れると思うと割とよくできた作戦だと当時の自分は思っていました。

他にも細かい作戦としては OutputOnlyが出たら先に見る。CommunicationとBatchで難易度が近そうだと思ったらCommunicationから見る。など色々自分の中での取り決めがありました。事前にあらゆる状況におけるムーブを想定しておくことで悩んだりしないで済み、時間が捻出できるという考えです。どのよう難易度のどのような問題が出るかの組み合わせを色々イメトレしました。

QOJ.ac での自分の解いた問題数

お気に入りの問題たち

IOI2020 Day1-C Carnival Tickets
IOI2021 Day2-B Dungeons Game
IOI2022 Day1-B Prisoner Challenge
IOI2023 Day1-A Closing Time
IOI2024 Day1-B Message

実は...

6月上旬に左手の人差し指の付け根を骨折していました。その間もそこそこバチャをやっていたのですが、タイピングが思うようにできずかなりメンタルもやられていました。まあとにかくいつも通りやっていくしかないと切り替えて日々頑張ってはいましたが、6月末まではずっとこの不便な状態でした。

骨折したときのツイート

ギプスが外れたときの感動:



本編

Day 0(出発日)から時系列で書いていきます。

Day 0 7/26

羽田空港に朝9時に集合し壮行会がありました。スポンサーのNTTデータ様から日本代表のユニフォームであるポロシャツと法被を頂きました。法被が特にウケが良さそうだな~と思いました。写真撮影や団長からお言葉を頂いて壮行会は終了し、チェックインやら荷物を預けるなどして保安検査を通過してようやくボリビアへの長い旅が始まりました。

フライト1: 羽田空港ロサンゼルス国際空港

11時間のフライトの末、7/26 朝7時(UTC-7)にロサンゼルス国際空港に到着しました。


アメリカで有名なポテチのLaysを買い、食べました。(5$もしたが...)
スクレに到着する24時間程度前だったので代表団全員でダイアモックスを飲みました。

フライト2: ロサンゼルス国際空港→リマ・ホルヘ・チャベス国際空港

8.5時間のフライトの末、7/26夜11時(UTC-5)にリマ・ホルヘ・チャベス国際空港到着しました。


リマから様々なワクワク要素があると思ったのですが、思いのほかリマ国際空港がモダンで活気がある空港で安心感がありました。
ここでも再びダイアモックスを飲みました。
代表選手と団長団はタイミング良く開催されていた高校生数学コンテスト in Hamamatsuの予選に参加していました。疲れで頭が全然働かなかったけど結構楽しかった。

Day 1 7/27

リマでの乗り継ぎで日をまたぎました。長いDay 0が終わりDay 1になりました。

フライト3: リマ・ホルヘ・チャベス国際空港→ビル・ビル国際空港

2.5時間のフライトの末、7/27朝5時(UTC-4)にビル・ビル国際空港(サンタクルス)に到着しました。ついにボリビアです。この時点で日本を出国してから実に30時間以上です。
ヘロヘロでしたが、IOIのお出迎えがありようやくボリビアについたんだと実感が湧いてきて嬉しかったのを覚えています。


入国審査の列をIOIの案内人がスキップさせてくれて、日本のパスポートが強いおかげか審査は一瞬で割と早く入国できました。
また、リマから実はシンガポール代表とペルー代表と一緒だったようです。サンタクルスで遭遇しました。シンガポール代表団のerrorgornはシンガポール国立大学の学生のyutoさんとpenguinmanさんと知り合いのようで話しかけてきました。(今回の大会では団長たちは彼によく絡まれたようです。)
サンタクルスではみんなで朝食を食べました。SALADOSという単語の意味をサラダと勘違いして届いた商品に驚いたり。

フライト4: ビル・ビル国際空港→フアナ・アズルデュイ・デ・パディリャ国際空港

40分程度のフライトで7/27午前11時半(UTC-4)にフアナ・アズルデュイ・デ・パディリャ国際空港(スクレ)に到着しました。


スクレは国際便がないものの国際空港という名前を冠しています。着陸した場所の周辺は本当に何もない高地という感じで、すごい場所に来てしまったという感覚ともう飛行機がないという嬉しさでいっぱいでした。
飛行機を出て荷物受け取りの場所まで行くと空気が微妙に薄いと感じました。これは走ったりしたらダメだと直感が伝えてきます。

お昼ご飯の時間に宿に到着し、自分がスマホを一瞬紛失するというトラブルを起こしましたが、無事部屋にたどり着きました。ガイドさんは日本語をそれなりに話せる方でした。どうやら日本に留学したことがあるようです。Mitsubachiさんとかと話が盛り上がっていました。

団長たちが自身のホテルに向かった後、国際交流をしました。フィリピン、ボリビアアメリカ、カナダ、オーストラリア、スペインetc...
そしてついにイギリス代表のCyanmondと感動の再会!Cyanmondと合流した後は台湾とずっと雑談していました。
夜ご飯も近いしルームメイトのウクライナ代表も到着した様子だったので部屋に戻ったところ、他3人はさっきまで寝ていた様子。

部屋にはシャワートイレが2つあり、一つずつ各代表に割り振りました。我々の方は水しか出ませんでした。この時、しおむすびはウクライナ側は温水が出ると思っていたようですが、ウクライナのシャワーを試したときはコールドシャワーを浴びた後で体がバグってて実際はウクライナ側も水しか出ない様子でした。

夜ご飯はCyanmondと合流しイギリス代表と一緒に食べました。他3人は感動の再開なのにお疲れの様子で反応は何もなかったです。

夜は再びCyanmondと台湾代表とずっとカードゲームを遊んでいました。さすがに体の疲労を感じ始めたので早めに撤収。

Day 2 7/28

ラクティスと開会式の日です。
3:30に一度目が覚めましたが二度寝に成功しました。朝ご飯を食べてちょっと一息したら移動です。宿(Villa Bolivariana)から競技会場(Polideportivo de Garcilazo)は徒歩2分くらいなんですが、正門が宿と真反対の方向にあるせいで5分以上歩かされます。とても急で長い坂があり大変そうだなと思いながら歩いていたら、プラクティスに持っていくべきマスコットを忘れていることに気付きました。坂を下りきったところで気づいたので再び坂を上ることになり息切れしまくり。
無事スタジアムにたどり着き、実際の競技をする空間に入るにはチェックを受ける必要がありそこがボトルネックで外で大分待たされました。

Practice Contest

いざ中に入って自分の席につくと、まず机の狭さに驚きます。そして、相手選手とマウスが衝突してしまうことが容易に想像できるような配置でした。また、各種要望を伝える札が配られていました。トイレに行きたい、バナナが欲しい、水が欲しい、チョコが欲しい、紙が欲しい、競技環境のトラブル等。
いざプラクティスが始まって取り組んでいると、鳥の鳴き声が聞こえます。ふと上を見上げるとなんとびっくり、鳥がスタジアム内を飛んでいます。おそらく外と中が完全に遮断されていない空間なのでしょう。雨が降ったらどうするんだろうかと考えたりしながらパソコンの環境で色々実験します。

競技環境
トイレの札

Practiceの終盤ではGA Meetingから帰ってきた団長らが競技会場に流入してきます。最初は厳粛な雰囲気だったのが緩い感じに変わり、自分は他の席の日本代表やCyanmondに色々話にいきました。そして、団長らの話だとどうやらこの席は競技Day1,Day2も変わらない可能性が高そうとのことらしい。自分は後ろが通路になっていて開放的な席だったのでラッキーだなと思いました。(そして位置的に広報の写真に後ろ姿が移りやすかったようです。)

競技中の画像

キーボードがスペイン語配列だったらしく、US配列だと聞かされていてキーボードを持ち込んでいない代表が困惑していたようです。JIS配列のキーボードをちゃんと持ち込んでいるのでワクワクを、回避!

開会式

Practiceから帰ってきて宿でお昼ご飯を食べて一息ついていると開会式への移動の時間です。ふと窓の外を見てみると大量のバスが並んでいます。みなOvertaking(IOI 2023 Day2-B)だと口にしていました。やはりIOIの参加者は全員過去問のネタが通じます。

Overtaking(IOI 2023 Day2-B)

開会式は市街地でBibliotecaという場所でした。バスで降ろされたところから多少歩くと民族衣装を着て音楽を流しながら踊っている集団がいてそこで代表選手がみんな密集しており先に進まないなあと思っていたら入口の目の前だったらしいです。人が密集しており何が何だかわからなかった。

伝統衣装を着た人たちが踊っている

会場は屋外で各国の選手がまとめて座るという形式でした。開会式では伝統的な踊りがたくさん披露されてから国紹介に入りました。アルファベット順で呼ばれていたので日本(Japan)の直前はイタリア(Italy)だったはずがイタリアが飛ばされて呼ばれたので驚きましたがとりあえず盛り上げます。後半でイタリアがちゃんと呼ばれましたがどうして順番が入れ替わっていたのだろうか🤔日本の法被はウケがよくて現地の人にめちゃくちゃ写真を要求されました。そもそも写真を撮る文化があるっぽい?無事開会式は終了し、帰って夜ご飯を食べて疲れたのですぐ寝ました。

Day 3 7/29

Excursion 1の日である。
午前組と午後組で別れており我々は午後だったので午前は自由時間でした。のんびり朝食を食べていたらウクライナの選手が1人同じ卓に来てコカ茶があるよとニヤニヤ話をしてきました。ウクライナはどうやら午前組だったので彼は早々に去っていきました。午前はライブラリを復習したりみんなでnoshiさんのブログを読んで今から知っても損がなさそうなテクニックの話をしたり...

Excursionはトルコと一緒でした。バスでは自分がトルコ代表4人と会話する感じで、トルコの選考の話や学校が科学オリンピックを推奨しており授業のサボりを正式に許可しているという話を聞いて驚いたりしました。また、彼らはJOISC(春季トレーニング)(発音はじょいすく)のファンらしく、双子の話もしてきました。道案内2が好きな問題らしい。
最初の観光場所ではIOI人文字をした。

観光地1

そこから移動するときに団長らと合流しました。トルコの団長も一緒にいましたが、次の目的地に移動するバスに乗った後、出発前に降りて一服して帰ってしまいました。移動中は団長含めてトルコとJOI春季トレーニングの話をはじめとして色々話しました。スクレは憲法上の首都なだけあってボリビアの歴史の中で重要な場所を複数訪れました。中心街の広場はボリビア独立200周年で盛り上がっていて騒がしかったです。
観光地から移動する直前にテレビカメラに取材されました。放送されたかは知らないがちゃんとインタビューに答えました。

丘の上から市街地を眺めた

最後に団長らから色々お言葉を頂き、解散となった。ついに明日が本番だと思うとドキドキしてきた。

Day4 7/30

Contest Day 1
朝は代表みんなでインスタントフードで宴をしました。緊張感が漂う中、コンテスト会場へ手ぶらで向かう。外で20分くらい待たされましたが、厳しい身体検査を受けて自分の机へと向かいました。やはりpracticeの時と配置は変わらず、自分の席は端なので背後には広々とした空間があります。競技開始前にトイレに行きたかったが、もう札を上げるなというアナウンスがあり行けなかった。開始20分前くらいから競技会場は静かになり緊張していました。

競技1

午前10時、予定通り競技開始

12分くらいかけてすべてのテンプレートやらを実装し、全問題を眺める。Batch And Output Only がありびっくりするが見た感じOutput Onlyが30点分だけで少し安堵。
A問題は配点的に満点の前が67点だけなので簡単そう。2問目にはBatchAndOutputOnlyのBを見るのが良さそう。といった感じで見る問題の順番が決まった。

A問題 souvenir

A問題は一周目で67点までいければとりあえずよさそう。という思いで考える。N=2とPが定まっている小課題1,2は問題文を正しく理解できているかの小課題だ。とりあえず出して7点を得る(10:15:53)

小課題3,4を見るNが定数のほうがやりやすそうなのでN=3を考えると場合分けをいくつかするだけでいいと気づく。実装してさらに18点を得る(10:21:36)

よく考えたら小課題3もうまくやればPを全て特定して回数を抑えられる。直感的に正しい実装をし、投げるがWA。一瞬焦るがコードの最後で

rep(j,i-cnt[i]){
  //処理
  cnt[i]++;
}

をしているのでこれが悪さしてそう。何も考えず cnt[i]++; を消して再び提出すると小課題3も得られる。一旦39点。悪くないここから67点に乗せられるかだ。(10:29:41)

Pに関する性質が色々見えて実はNが70以下とかであることがわかるが元の制約でNが100以下。あまり意味がない。Pを上から特定していくことを考えていたが何もうまく行きそうにない。テキトーなコードを書けなくはないがそれで時間を食うのはもったいない。うんうん考えていたら競技開始から50分が経とうとしていた。全然つかみどころがなく、これ実は満点むずい系か?と思い、とりあえずBに移ることを決める。

B問題 triple

問題を読むとよくある感じのBatchで安心。こういうのではできればBatchの満点70点取りたい。

自明な O(N^2)が思い浮かぶので実装する。18点のつもりが34点も入ってびっくり。どうやら定数倍がいい実装をしてしまっていたらしい。ラッキー(10:59:54)

見た感じコードの大部分はは単純な考察でO(N)に落ちる。ただ、一つの場合だけどうやってもO(N^2)かかってしまい、こまった。Hが広義単調増加の場合はこのO(N^2)かかるケースを数えなくていいので実装しさらに11点獲得(11:10:35)

70点が近いと思いO(N^2)をどうにかすることを考えるがなかなか落ちそうにない。一旦6点を回収するO(NH)コードを書いて6点獲得。(11:29:01)

いくつかエスパーっぽいことして提出するが無意味。定数倍高速化したりもしたがACにならず。う~ん無理かあ

Output Onlyを見る。とりあえず1,1,2,1,1,2,...でN-1が実現できるので提出。これは5.29/30らしい。これもしかして得点獲りにくいOutput Onlyか?(11:37:50)

一旦頭を冷やして戻って来るためにC問題に行くことにする

C問題 worldmap

木の場合は簡単である。よくあるオイラーツアーをして並べる。二次元グリッドであることを活用していないがまあ小課題は取れるので一旦考えないことにする。15点を獲得(1:55:25)

次の完全グラフの方が自明な構築がある。さらに7点獲得。(1:57:29)

小課題4は1を間に挟み込んでうまくやる感じだろうと思うが実装がめんどそうなので次の小課題N<=15を考える。これのほうが全体の解法につながりそう。少し考えると、2*N*(N-1)/2が240以下なので辺をすべて尋ねるオイラーツアーを取ってまた列ごとに埋めてやればいいと気づく。dfsを実行しないコードを提出するバカをしたりしたが無事14点獲得(12:07:07)

この問題、意外と解けるのでは?と思いながら小課題4を考えるが、先ほどのオイラーツアーのコードがうまくいきそうだとわかる。市松模様っぽく埋めればオイラーツアー順で隣同士とあとはある頂点に隣接する頂点を詰められる箱をたくさんつくることができる。それを雑に実装し4Nを得る。一番得点を得られている問題になって、かなり気持ちがいい(12:23:13)

その後少し考えると余分な行がNくらいあってそれを消せば容易に3Nが達成できる。頭のキレが少し落ち始めていたので実装にかなり時間がかかり満を持して提出するとWA。あらら(12:46:51)

構築をよく見ると、市松模様パリティがうまくいってないので丁寧に紙で整理するとちょっとミスってることがわかる。そして無事86点を得る。これは本当にうれしかった(12:52:16)

少し満点を考えるが、今の方針だとどう頑張ってもだめそう。斜めにして行数を増やすことを考えたが、列の長さが短くて無理じゃねとなる。今思うとDFS木の性質を思い出せずもったいない!
3時間時点を過ぎたところで2周目に入ることにしA問題に再び戻る。ここまでそこそこ順調か?

A問題

とりあえず28点の小課題を考える。
P_{N-1}が特定できればうまく全部特定できそうであることがわかるがこのP_{N-1}を特定する方法がなかなか思い浮かばない。どうすればええんや?P0-1を初手で聞いてから得た情報をどううまく使えばいいんだろうか~
うんともすんともいかず30分くらい経つ。B問題はOutput Onlyなどで少量でも点数を得る余地があるので移ることにする。

B問題

とりあえずpracticeでもやった数列を前から追加していってスコアを増やす貪欲を書く。スコアが増えない場合もあるのでその場合はランダムにをするとN=20だと満点を得られる。(13:50:59)
N=500もギリギリ実行できそうなので実行させる。10分くらい実行を二回やった末N=500で3.91点を得る。(14:12:45)

この間もずっとO(N^2)の処理の部分を考えていた。二次元にプロットしてうんうん眺めていたが何も思い浮かばない。Output Only構築に活かせるかとか考えたが頭が固くてうまくいかない...少しずつ焦りを感じ始める。

A問題とB問題BatchとB問題Output Onlyを反復横跳びしはじめてそれぞれ15分くらい考えて進捗、無いな~をしていたら14:50でもう点数上がらね~と言う気持ちに

最後の3分くらいでB問題のOutput OnlyでN=500で得られている割といい解を連結させれば他の大きいNでも今よりいい点数を得られることに気付きました。1,2行書いて最後の最後に提出。見直して保険でもう一度提出。そしたら競技が終了し、空気が一気に緩んだ。
競技終盤だったのでジャッジに時間がかかっていたが、競技終了後すぐにリロードすると点数がちゃんと2点以上上がっており、これでメダル変わったらどうしようとか調子のいいことを考えていた。

競技終了後

全体的に点数を伸ばしきれなかったという感想を抱いたので金メダルボーダーは210点くらいかなという予測を立てていました。そうすると自分は40位悪くて50位といった気持ちです。

席を立っていいですよというアナウンス後に一番席が近いhiikunZに話しかけます。彼はどうやらA(souvenir)で満点を取ったらしい。え?頭が凍って冷や汗が一瞬にして出てくる感覚がした。これ240くらいが金ボーダーか?終わった終わった。とか思っていたら彼は合計210くらいらしいです。実は他2問で多少差をつけられてはいる/縮められているのかもしれないという淡い期待を持てました。すぐ後にhirayuuと遭遇し点数を聞くと230。あ~金ボーダー230以上だと絶望。shiomusubiがちょっとしてから合流し、彼は200くらい。自分との差はBのbatch満点かそうじゃないかだった。このbatchを取れないのはやっぱりだめだったんだと反省。
競技会場内で台湾代表のうち3人と遭遇し彼らは全員A(souvenir)で満点らしい。絶望。終わりだ。彼らは全員230くらいらしい。日本代表終わったかも...?という雰囲気になる。

競技会場の外に出て、団長と合流して一息ついて順位表を見せてもらう。嫌な予感が的中し日本代表全員が銀圏で衝撃が走る。Cyanmondとも合流し、彼は別のところでコケて180点くらい。自分は188.28点で70位。信じられなかった。よくみるとsouvenirの満点が50人近くもいる。なんでなんだ。理解できなかった。hiikunZは最初に話しかけたときに「souvenirはテキトーをすると通ります」といつもの調子で言ってきていたがそれが本当だったとは。日本代表では圧倒的最下位でもう金メダルの希望なんてあるのか?という諦め。ただただつらかった。唯一のよかったところは予想外にもOutput Onlyだった。

食事をしているうちに気持ちは落ち着いてきて順位表を見せてもらったらアメリカ勢、ロシア勢なども大分やらかしていて大荒れの様子だった。ぱっと見の印象ではヨーロッパ勢が躍進していた。souvenir解けるか解けないかという感じのセットだった。

絶望の中、宿に戻り夜ご飯。昨晩Cyanmondに国際交流に誘われたのに寝落ちして連絡を無視してしまったので今日こそはやろうと話したが、結局競技の話ばっかりで暗い話をしていました。そんな中、たまたまアメリカ+カナダ+ニュージーランド+オーストラリア+中国勢がカードゲームを始めようとしているところに遭遇したのでそこに入れてもらいました。Cyanmondはシャワーを浴びると言って消えていったが自分は最後までやりました。中国語のカードゲームだったのでことあるごとに中国語がわかる人に訳してもらったり盤面がクソゲーだったりしましたが楽しかったです。

カードゲームをやっている様子

寝る前になるころにはただただ悔しかったのでDay2はやってやるぞという気持ちに大分切り替わっていました。

Day5 7/31

Excursion 2の日です。
午前中に宿を出発し、La Glorieta Castleに行きました。お城を観光したあとは前の広場でアクティビティが行われました。あまり元気はなかったけれども結構走らされるアクティビティに参加しました。となりのグループで救急隊が出動しており大変そうだった。明日コンテストなのになぜ激しい運動をさせるのか...

お城

広場をはさんで隣は閉会式の会場でした。広場でサンドイッチを食べている間にCodeforcesのdiv 1が始まってしまったので、その場で日本代表で問題を見て解いたりしていました。

外から見た閉会式会場

明日が最終日だという緊張があったせいかあまり覚えていません。夜ごはんには一蘭カップラーメンを食べて自分を鼓舞しました。夜は色々考え事をしたりしていて寝た時間は多少遅かったが今までで初めて一回も深夜に起きることなく6:30頃まで寝ることができました。



Day6 8/1

Contest Day 2の日です。

インスタント味噌汁や缶詰などを朝食として食べて、日本代表は少し重い雰囲気で会場に向かいました。今日は宿の鍵を競技会場に持ち込んでOKらしい。それ以外は何も持たず、身体検査を通過し無事入ることができました。
席の場所はDay 1と変わらず。ただ、自分のおやつとして入れていたはずのGABAが紛失しておりそれは少し悲しかったです。

そうこうしているうちに開始10分前になり、緊張がピークに達していたので持ち込んでいたピュレグミを食べて落ち着いた。

競技2

午前10時、競技開始

10分くらいかけてすべてのテンプレートやらを実装し、全問題を眺める。Batch-Communication-Batchだ。問題をぱっと見た感じでBatchは普通のBatchでCommunicationも普通のCommunicationっぽい。まずは、ありがとう。Communicationを真ん中に置いて順当に前から解くことにする。

A問題 festival

問題文を読んでまずよぎったのは全順序。
これだと思いながらまずは問題文を正しく理解できていることを確認するために累積和をやるだけの小課題1を書いて5点獲得(10:16:20)

手元で計算すると商品 i,j の順 j,i の順で使うときの評価が今持っている金額にかかわらず可能であることがわかった。これでしかない。どの小課題が通るかよくわからないが一旦実装して点数を取るぞと実装すると小課題1,5で正しく、追加で27点を得る。確かに全部使えるならこの順序が最適だ (10:22:12)

また、T_i <=2も簡単で評価関数よりT_i=2のものを先につかうのがよい。また、金額は小さい方から順に使うのが最適なので前からいくつかT_i=2を使って残りをT_i=1で使う実装をした。これで小課題2,3の19点を獲得(10:29:48)

とりあえず小課題4の N<=70を考える。これはさっきの考察がそのまま使えて、各Tについては小さい方から何個か使う。使う商品の集合を決め打ったらさっきの評価基準でソートしてちゃんと全て買えるか判定すれば良さそう。この調子だとあと一個何か性質を見出せれば満点が可能の問題か?と思ったので実装を一旦置いて小課題6を考える。

常に単調減少の場合はPの値がある程度制限されることは言えるがそれ以上のことが何も見えなかった。競技開始40分くらいだったので一旦実装もせず他の問題に切り替えることにする。小課題4の考察を問題用紙にちゃんと書き残してB問題に移る

B問題 migrations

まず、問題を読むのに時間がかかった。小課題1の30点は絶対に欲しい雰囲気がする。よくわかんないCommunicationだ

とりあえず小課題1の片方の端点が0であるとき実は候補はN-2通りしかないのでこれでなんとか16点を得られることがわかる。Z<=4が正直わけわかんないので一旦実装して16点を得る。(10:54:51)

ここで Z<=4にできるかできないかが勝負の分かれ目だと感じ、少なくとも30点になる解法を得るまで粘ることにする。そうすると今年の春のFortune Telling 3が突然頭に降ってきた。そうだ、これ最後の数ターンで今までの情報を送りながら現在の情報の更新も入れていくやつだと気付いた。これなら余裕でZ<=4を達成して30点が取れそう。最後の14手で2進数で数字を送る(1または2) そして、その頂点が追加されて直径の端点になった場合は3を送る。完璧だなんならZ<=3である。これは先の小課題でも点が取れる手法かもしれないとウキウキしながら実装に取り掛かる。

考えている時間が長かったが実装はすぐ終わって無事小課題1で満点。(11:16:36)

そのまま残り70点分の小課題2も考える先ほどでZ<=3が達成できてたのでどうせZ<=4もできるだろうと思いZ<=4から考え始める。
u,vを順番に送ることを考える。uを送っている時にuの更新があったら知らせる、vを送っている時にuの更新があったら今送っているvの値の情報とともにそれを知らせる、vが更新されたらそれを知らせるの場合がある。送っているときは0を送るのも含めて5通りある。uを送るときは1通りはuの更新の通知に使うので、(5-1=)4進数でuを送信できる。7文字必要。vも似たように(5-1)/2=2進数で送ることができるとわかった。これで14文字。合計21文字で達成できることがわかった。スコアを計算してみたら49.11点を獲得できるっぽい。これは実装するしかないと実装に取り掛かる。

Day1も含めて一個の提出でここまで点数が上がる想定のものは初めてだったので実装する手は少し震えていた。15分くらい実装しできあがって提出すると0点でかなり焦るが、Communicationの問題なので一回問題文を読み直して変な仕様がないか、何か勘違いしていないか確認する。そうするとよく考えると当たり前だが同一ケースでプログラムは別々に2回実行される。その事実は実装時抜けていたので確認すると初期化がミスっている箇所があった。それを直し祈りながら提出すると無事79.11点が返って来る。思わずガッツポーズが出た。(11:52:14)

Fortune Telling 3ありがとう!流石に時間を使い過ぎたので3問目に移ることにする。

C問題 obstacles

問題文を読んでよくあるクエリ問題に見えたときは運が良いと思った。83点分は(L,R)=(0,M-1)なので一回それで考える。37点分の部分点はかなり自明に見えた。一旦O(NM)を実装し、小課題1,3の23点を得る。(12:07:02)

小課題2もかなり自明なので実装しさらに14点を得る。(12:09:51)

このくらい37点が簡単ならこの問題が今日のセットの一番の簡単枠かもしれないと満点を取ることを視野に入れながら一旦小課題4のQが小さい条件で考える。
ここで一つ予想を立てた。
以下の操作を繰り返し行って収束するマスが等しいこととマスが連結であることは同値であるというものだ。
操作: 同じ列で移動できるマスのうちできるだけTが高い行に移動する。その後、同じ行で移動できるマスのうちできるだけHが低い列に移動する。

なんとなく手元でいじってみるとこれが正しそうなみた目がする。セグ木をDay2のこの時間になって初めて実装し、セグ木上の二分探索をさぼったが無事小課題4のO(QNlogN) の21点を得る。(12:38:20)

さらにここで実は訪れ得るマスの個数はO(Nlog(N))とかで抑えられるのではないかというエスパーをしてそれを実装することにした。これで25点得られたらアツい。
多少の焦りもありバグらせてから直すまで何回も提出してしまったが、操作を2回以上繰り返していないという致命的なバグが見つかり、無事追加で25点を得る。ここで本日2回目のガッツポーズが思わず出た。(12:50:39)

この時点で51-79.11-83である。開始3時間前でこれは大分調子がいい。

B問題

そういえば0を返していいときに0を返していない箇所がいくつかあることをふと思い出したのでそこで0を返して点数がワンチャン上がるかもという淡い期待を持って投げる。運がいいことに2.17点上がった。(12:55:44)

2文字くらい改善してるっぽい。18文字以下でできる気が全くしないので、もうA問題とC問題に全ツッパで行くことにする。(これは結果を見ると正しい選択だった)

A問題

放置していた実装をすることにした。四重ループとかを書いてちょっとバグらせたが無事小課題4を通して15点獲得(13:06:09)
この時点で66-81.28-83で合計230.28点もうだいぶ気持ちよくなっていた。一番点数を取る余地があるのはA問題なので引き続き考えていくことにする。
嘘っぽいDPを生やしてそれを実装してみるが32点(小課題1,5)しか得られない。
絶対何か見落としていて、N<=70の時点でその考察を通る必要があったのではなど疑ったりしたが紙の上で色々するだけだった。

今思えば、考察がさらに必要なことは明確だったので本当はここで解の構造を調べるためにランダムテストをするべきだったと思う。
気付いたら30分くらい経っており、C問題の満点を一切考察してないのはもったいないので考えることにする。


C問題

少し考えてみるが、83点の時点でよくわからないエスパー考察を経ており、ここからどうにかできそうな予感がしない。TやHのCartesian Treeのなんらかに言い換えられたりしそうと思ったが、制約をよく見たらT,Hは相異なるわけではないのでやりにくい。
領域の分断のされ方を色々描いてみたりしたが正直何も見えなかった。L,Rについての制約があっても綺麗にクエリあたりlogとかで解けるような性質が見える気がしない。自分の83点の解法はL,Rに制約があると58点解法となんら変わりない状態である。わからん!A問題考える

A問題

最適化なのでよくわからない嘘が刺さる可能性にかけていくつか嘘dpや嘘貪欲を実装して提出したりした。気づいたら競技終了まであと20分。結局何も進捗は得られていなかった。

B問題

もうA,Cを考えるのに飽きたので少しだけ考える。他のテキトーな最適化で運よく18以下になったりしないかなという期待で色々書いて終了5分前から4回くらい連投した。一部の競技結果が返ってくる前に競技は終了した。競技終了後に全部別に得点が上がっていないことを確認した。

競技終了後

今日は出し切った感覚はありました。特にobstacleでよくわからないまま83点まで伸びたのはかなりアドバンテージだと思った。やったか?と心の中で思いはしたが別に金の自信があったわけではなかった。競技中からずっと頭の中で金メダルがチラついてはいた。

席を立っていいですよというアナウンス後にすぐhiikunZに駆け付け点数を聞きます。彼は170くらいで自分と比べたら大分低かった。その次にhirayuuに遭遇。180点らしい。二日合計でもhirayuuに勝利したが、festivalで82点とっており流石です。本人曰く嘘解法らしいけど。そして最後にしおむすびに点数を聞く彼は250点らしい。惨敗。点数の取り方も自分がちゃんと負けていました。
だけど、日本が金メダル二枚以上なら俺は金メダルであると思うと流石にドキドキしてきました。しおむすびの金は確定だろうが自分は本当にボーダー近辺かもしれない。

団長団と会場外で合流し、少し開けたところでみんなで順位を確認します。しおむすびは22位、hirayuuは39位、hiikunZは56位、自分は33位だった。28位まではあと20点だったらしい。ここまでDay2で盛り返したのに金に届かなかった無力感を覚えました。Cの満点が取れてもAの小課題6が取れても届かない点数でした。今日の自分ではどうしようもなかった気がしてきた。悔しい気持ちもあったがとにかくsouvenirが恨めしかった。souvenirのせいにしないと受け入れられなかった。

昼食を食べ、今日もスポンサーブースでダラダラし、最後に競技会場の近くにあるとてつもなくデカい滑り台を滑って爽快感を味わって宿に戻りました。
今日は市街地に行って団長たちとごはんを食べられるので楽しみで仕方がなかったです。ついにおいしいご飯だ!
ほどなくして団長に競技会場で合流するように言われ向かったところ、イギリス、アメリカ、韓国、カナダ、オーストラリア、ニュージーランド代表と一緒にご飯を食べることになっていました。どうやらスポンサーのHRTの奢りらしい。最高!バスに乗るのかと思いきやみんなで歩き始め、ついていったが交通量が多い道路を何回も渡ったりして車にひかれそうになりました。怖かったけど30分くらいいろんな人と雑談するとレストランにたどり着きました。ボリビア料理だと思っていたところ、イタリア料理だったのでちょっとがっかりしましたがおいしかったです。数日ぶりのインスタントではない美味しいご飯。ありがとう。

テーブルは分散して色々な人と座っていたので気付かなかったのですが、日本代表の他の3人はお疲れで早めに帰って行ったらしいです。自分は最後までディナーを楽しんで同卓のカナダ代表と仲良くなりました。

帰りはバスが用意されていてみんなでゆったりと宿に戻りました。宿に戻ったら部屋は真っ暗で他3人とウクライナ代表は寝ていました。シャワーを浴びたかったけれどもコールドシャワーは嫌だったしイギリス代表と大分仲良くなったので彼らの部屋で浴びさせてもらえないかお願いしに行きました。ジャパニーズ土下座を披露しシャワーを浴びさせてもらうことになりました。あったかいシャワーはほぼ一週間ぶりで流石に感動しました。

Day7 8/2

表彰式の日です。

午前中は自由時間で競技会場のスポンサーブースやらで遊べたりスポンサートークがある緩いイベントでした。Cyanmondと一緒にのんびり競技会場に向かい、雑談しながら無料配布のポップコーンやジュースをもらって食べていました。OpenAIのスポンサートークがあるらしく流石にOpenAIは気になるとなり、二人で聞きに行きました。聞いている間、少しだけDiscordを開いたらIOI2028,2029の開催地がそれぞれ日本、ブルガリアであることを知りました。びっくりしたので隣にいたCyanmondにすぐそのメッセージを見せて少し騒いでいました。程なくしてTwitter上でも海外の人がツイートしておりtatyamさんが即座に反応していました。IOI2028 Japanが衝撃的過ぎてOpen AIの話はそこから半分くらい覚えてないです。

自分は本当にDiscord上でのメッセージを見るまで日本が立候補することさえも知らなかったので何が何だか理解できなかったです。10年に1回開催はかなりの高頻度らしく、Codeforcesなどを見た感じIOI2028 Japanは楽しみな人が多いようです。

OpenAIのトークの後はスタジアム外にあるyogiboもどきに座り込んでCyanmondとあれやこれや話していました。そしたら昨日仲良くなったカナダ代表の人がやってきてゲーム遊ばないと誘われたのでその場で昨日一緒にご飯を食べたオーストラリア代表、初対面のインド代表と一緒に人狼ゲームもどきを遊びました。それなりの時間遊んでいたらスタジアムの撤収の時間らしく、追い出されました。中では一部解体作業がはじまっていて喪失感を覚えました。

表彰式

夕方頃になり表彰式の時間になりました。バスに乗ってExcursion2のお城の隣にある表彰式会場に移動しました。表彰式では順位順に席の位置が決められており、銀メダルの最前列だったときは少し悲しかったです。逆ボーダーだったカザフスタンの選手がいません。どうやら彼らはもう帰路についてしまったらしいです。
表彰式では銅メダルから順に順位順に10人位の単位で前に呼び出されており、人数のめぐりあわせで銀メダルの最後のグループで自分含めて4人だけで前に出ました。ロシアのbashkortへの歓声がすごかったです。

銀メダル


表彰式後はデカい会場でディナーでした。色々な国の人に話しかけられては一緒に写真を撮りました。銅メダルを持ったキューバ代表の人が金メダルと銀メダルを貸してくれないかと聞いてきたので貸したら三色のメダルをかけて自慢げな顔で記念写真を撮っていて面白かったです。終盤はガイドの方たちを中心に騒がしくダンスをしていました。自分は疲れ切っていたのでダンスはせずに宿へのバスに乗って帰りました。
JOIから各国の選手に配るためにもらっていたボールペンや自分が持ってきた日本のおやつを消費するために共有スペースとかに居座って通りがかる人全員に声をかけて渡しました。Cyanmondも一緒にいてずっと雑談しながらやっていました。

Day8 8/3

出発日です。我々は午後の便だったので午前はゆっくりパッキングする時間がありました。ウクライナ代表は早めの時間に出発らしく朝起きてすぐに別れを告げました。

スクレ空港で見かけた旗がDay1 worldmap の満点解法の構築にそっくりだって話をしおむすびとしてニヤニヤしていたら団長らに激写されインスタグラムに投稿されていました。

worldmap(一番左の旗)
フライト5: フアナ・アズルデュイ・デ・パディリャ国際空港→ビル・ビル国際空港

40分程度のフライトで8/3午後4時頃(UTC-4)にサンタクルスに到着しました。到着して遅めのお昼ご飯にSubwayを食べました。Subwayはどこでも美味しいなあ。
トランジットが6時間くらいあったので5hのICPC バーチャルコンテストをやることになりました。yutoさんとぺんぎんさんはICPC WFが控えているのでそれの練習も一応兼ねていたらしいです。団長団vs代表の勝負になり、shiomusubiとhirayuuとチームを組みました。OIをしたばかりだったので遅延セグ木の実装で一切ライブラリを参照しませんでした。そうしたら案の定バグらせた... 途中パソコンの電源が切れてパソコンで実装できなくなったので結果的には負けましたが、完数はタイで本当はもう一問解法がわかっている問題がありました。



Day 9 8/4

サンタクルスで飛行機に搭乗した直後くらいに日を越しました。

フライト6: ビル・ビル国際空港→マイアミ国際空港

8時間程のフライトで8/4午前8時30分頃(UTC-4)にマイアミに到着しました。実は飛行機は給油のためにパナマシティに着陸していましたが、便を通してほぼずっと寝ていたのでよく覚えていないです。
空港内ではお昼ご飯にキューバ料理のレストランで大きい肉を食べました。hirayuuはスタバで何か親へのお土産を買っていました。

デカい肉とフライドポテトと米
フライト7: マイアミ国際空港→ロサンゼルス国際空港

5時間ほどのフライトで8/4午後4時30分頃(UTC-7)にロサンゼルスに到着しました。ロサンゼルスではトランジットの時間に余裕があったのでyutoさん、みつばちさん、ぺんぎんさん、hiikunZと共に空港の外に行きました。Uberに乗って市街地に行く案がありましたがタクシー料金が高すぎたので歩いてIn-N-Out Burgersに向かうことになりました。20分以上歩いてたどり着いた先で食べたバーガーは格別に美味しかったです。空港が真横なので着陸してくる飛行機を近くで見ることもできました。ちなみに隣にセブンイレブンもあった。

In-N-Out
着陸する飛行機

Day10 8/5

深夜1時発の便だったので空港で日をまたぎました。少し遅延もありましたが無事飛行機に搭乗できました。いよいよ最後の便です。

Day11 8/6

フライト8: ロサンゼルス国際空港羽田空港

11時間程度のフライトの末ようやく羽田空港に到着しました。
着陸したらもう8/6の朝5時です。時差のせいで1日が一気に消えました。

入国審査を済ませて無事預けていた荷物を回収し、長い旅が終わりました。
みつばちさんがいつからかずっとお寿司が食べたいと言っていたので解散後に代表みんなで連れて行ってもらいました。早朝だったので営業中の店が空港内の高い寿司屋くらいしかなかったのでそこに行きました。ありがとうございます。

その後、羽田空港からリムジンバスに乗って無事帰宅しました。

最後に

まずは、日本代表を応援してくださった方々に感謝申し上げます。自分は銀メダル、日本代表としても金メダル1枚と少し不甲斐ない結果で終わり悔しい気持ちでいっぱいです。ですが、IOI2025では様々な出会いに恵まれ、とてもいい思い出になりました。競技プログラミングを始めてからの5年間を振り返ると様々な記憶が蘇ってきます。自分が始めた頃から既にAtCoder黄色だったしおむすびと出会い衝撃を受けたこと、高1のJOI春合宿Day 1で大失敗をして悔し涙を流したこと、ABCで初めてWriterをして緊張したこと、パ研合宿でみんなで深夜まであれやこれや話しながら楽しく作業したこと、そしてなにより日々問題を解き続けたこと。
競技プログラミングは目標に向かって努力することを教えてくれ、かけがえのない友人達との出会いをくれました。


今後はJOIのチューターになって情報オリンピックに取り組む中高生を少しでも手伝えたらなと思っています。また、今大会で得た教訓/学びは今後の代表にも引き継いでいくつもりです。
悔しい思いをして終わってしまったので大学入学後も競技プログラミングは続けます。目標はもちろんICPC WFに出場してメダルを獲得することです。未来への決意を新たにし、この参加記を締めさせていただきます。

長い駄文を読んでいただきありがとうございました。




以上の内容はhttps://mt-saka.hatenablog.com/entry/2025/08/18/180500より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14