MtSakaのブログ

競技プログラミングをします

第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に出場してメダルを獲得することです。未来への決意を新たにし、この参加記を締めさせていただきます。

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

第37回国際情報オリンピック(IOI2025)ボリビア大会 Day -1

参加記

目次

はじめに

どうも、MtSakaです。7/27から8/3にかけて開催される第37回国際情報オリンピック（IOI2025）ボリビア大会に日本代表として参加します。日本代表団は明日7/26に出国します。前日なので今大会の情報や日本代表選手について書きます。観戦する人がより楽しめるようにと書いたので実際の競技の問題や対策についてはあまり深く触れません。

IOI2025公式サイト:
ioi2025.bo

情報オリンピックとは

情報オリンピックとは数学オリンピックや物理オリンピック、化学オリンピックなどと並ぶ科学オリンピックの一つです。高校生以下を対象とした競技プログラミングの大会です。情報オリンピックはFull Feedback形式で、プログラムを提出すると自動採点されて点数がすぐに返ってきます。そのためリアルタイムで競技者は自分の点数を知っています。

国際情報オリンピックは情報オリンピックの世界大会です。各国の選抜を経て選ばれた4人以下の代表が参加します。競技は2日にかけて行われそれぞれ5時間で100点満点の問題を3問解きます。2日間の競技の合計点で順位が算出され、上位1/12には金メダル、次の2/12には銀メダル、その次の3/12には銅メダルが与えられます。人数で言うと30,60,90人ずつくらいです。

日本代表になるには

日本では日本情報オリンピック(JOI)に参加することでこの代表の選考にエントリー出来ます。代表になる資格があるのは高校２年生以下です(翌年度8月の代表の選考なので高３は情報オリンピックに参加することだけはできます)。9月頃から3回開催される1次予選、12月にある2次予選を突破し2月にある本選で優秀賞を取ると代表候補になることができます。30人程度いる代表候補は毎年3月に開催される春季トレーニングにて4日間毎日5時間の競技に参加します。この春季トレーニングの結果で上位4人だった人が日本代表に選ばれます。(注: 今年からJOIの各選抜段階の名称が変更されるようです)

www.ioi-jp.org


私は3回春季トレーニングに参加しており2年前は8位、昨年も8位で今年は3位となり日本代表に選出されました。以下は過去の自分のJOI参加記です。(このブログに他にもあります)

mt-saka.hatenablog.com
mt-saka.hatenablog.com

IOI以外に日本から参加できる国際大会にアジア太平洋情報オリンピック(APIO)があります。毎年5月頃に開催され、春季トレーニングの参加者に参加資格があります。30人ほど参加して上位6人がAPIOの日本代表になります。IOIの代表にとっては前哨戦のような位置づけです。

代表紹介

今年の日本代表(+α)を紹介します。意気込みも聞きました。

JPN1 shiomusubi496

X: @shiomusubi496 AtCoder: shiomusubi496
高３。昨年も日本代表で金メダルを獲得している。春季トレーニングでは圧倒的1位で代表になった。CodeforcesではLegendary Grandmaster(LGM)でIOI参加者のLGM5人の1人です。ちなみに他4人は全員中国代表。マジでめちゃくちゃ強い。日本代表のエースと言っても過言ではない。全分野において強い。優勝候補。
意気込み「目指すは優勝」

JPN2 halc

X: @halc_kyopro AtCoder: hirayuu_At
高１。彗星のごとく現れて昨年日本代表になった。昨年はあと順位1つのところで金メダルを逃して銀メダルだった。元代表の威厳を見せつけ春季トレーニングでは2位。最適化とかが得意。
意気込み 「また逆ボーダーなったら泣いちゃう」

JPN3 MtSaka

X: @mt_saka AtCoder: MtSaka
この記事の筆者。高３。中学1年生の頃からIOIに参加することを夢見て競技プログラミングに取り組んできた。春季トレーニング3位。APIO2025では銀メダル。データ構造がちょっと得意かも？
意気込み「日本代表になったからには目標はもちろん金メダル」

JPN4 hiikunZ

X: @hiikun_Z AtCoder: hiikunZ
高３。競技プログラミング以外でもCTFで色々な国際大会に出場しておりパソコン力が高い。春季トレーニングでは怒涛の追い上げで4位になった。代表で一番ヒューリスティック/マラソンと言われる分野が得意。
意気込み「金メダルほしい～ マラソン問題が出てきてくれたら嬉しいです」

GBR4 Cyanmond

X: @Cyanmond_mapr AtCoder: Cyanmond
高３。現在イギリスに留学中のためイギリス代表での出場。JOI2023/2024では銀賞を獲得している。ずっとJOIに参加していたので実質日本代表かもしれない。
意気込み「日本代表全員に勝ちます。」

注目選手など

各国の代表は以下のCodeforcesのブログにてまとめられています。
codeforces.com

以下個人的な注目選手です。

  • USA Rain Jiang (rainboy) 今年でIOIへの参加は5回目で5位を3回取っている。Codeforcesでは参加するすべてのコンテストで一番最後の難しい問題から逆順で解いていくことで有名。
  • China Hengxi Liu (liuhengxi) 毎年全員強い中国代表の中でも群を抜いて強いんじゃないかと思っています。Universal Cup Finalsに1人チームで進出していたりする。
  • China Chen Xinyang (JoesSR) IOI参加者で最もCodeforcesレートが高い
  • China Sizhe Fan (umbrella-leaf) 5人のLGMの一人。
  • China Liu Haifeng (crazy_sea) 5人のLGMの一人。現在レートがちょっと落ちているがHighestレートではJoesSRに次いで高い
  • USA Brian Xue (hyforces) 去年のIOIでは3位だった。1位、2位だった人は今年いないので...?
  • Romania Mihai-Valeriu Voicu (ntherner) 去年は6位だった。

こちらからIOI順位予想ができます！(QOJのアカウントが必要です)
https://qoj.ac/voting_game/vote?competition=ioi2025

IOI面白(ワクワク)情報

  • IOIではマスコットの持ち込みが可能です。私は以下のマスコットを持ち込む予定です。
猫のマスコット
  • 開催地のスクレの標高は2790m
  • 移動は行きも帰りも乗り継ぎ3回。トランジットも含めると片道30~40時間。 羽田(日本)→ロサンゼルス(アメリカ)→リマ(ペルー)→サンタクルス(ボリビア)→スクレ(ボリビア)→サンタクルス(ボリビア)→マイアミ(アメリカ)→ロサンゼルス(アメリカ)→羽田(日本)
  • 選手の宿泊部屋は8人部屋で2段ベッドが4つある。公式HPに載っている部屋の画像は以下の通り。
部屋の例
  • ボリビアは冬なので夜は気温が4℃まで下がるが、宿の部屋には暖房がない。

さいごに

Instagramにて委員会が速報します。是非フォローしてください。
https://www.instagram.com/ioi_egoi_jp/

競技1日目は日本時間7/30 23:00から7/31 4:00まで、競技2日目は日本時間8/1 23:00から8/2 4:00までです。
当日はおそらくLive Scoreboardが公開されると思います。深夜ですが、是非日本代表の応援をよろしくお願いいたします！

JOI2024/2025 春季トレーニング参加記

参加記

今年もやってきました、春季トレーニング(通称:春合宿)。 日記形式で毎日書こうと思います。(ので、ブログをこの五日間鍵にしていました)

Day 0 (3/20)

表彰式でした。chokudaiさんがマイクを軸に左右に体を動かすという話を聞いてからスピーチを聴いていると、実際そうだなと話し方に目が行ってしまった....

交流会は楽しみました。交流してくれた人ありがとう。

practiceはまあVM配布されたからVM上で練習してきたので大丈夫。ただ、家のPCより重く感じた(ノーパソなので当然スペック悪め)。過去2回解ききれなかったpracticeで初全完。まあ今年はonline practicecもあって問題は知っていたのでね。

今年のテンプレート

モリモリにしました。cerrのデバッグがめんどいので関数を作った。いつも使う感じのやつらを全部入れた。正直ちょっと多い

#include <bits/stdc++.h>
#define overload4(a, b, c, d, ...) d
#define rep1(n) for (ll _ = 0; _ < (ll)(n); ++_)
#define rep2(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define rep3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (ll i = (ll)(b) - 1; i >= (ll)(a); --i)
#define rrep(...) overload4(__VA_ARGS__, rrep2, rrep1)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vi = vector<int>;
using ull = unsigned long long;
using vvl = vector<vl>;
using ld = long double;
using pl = pair<ll, ll>;
using vp = vector<pl>;
template <typename T, typename U>
inline constexpr bool chmax(T& a, const U& b) { return (a < b ? a = b, true : false); }
template <typename T, typename U>
inline constexpr bool chmin(T& a, const U& b) { return (a > b ? a = b, true : false); }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (it != v.begin()) os << ' ';
        os << *it;
    }
    return os;
}
template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    for (auto& e : v) is >> e;
    return is;
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename U>
istream& operator>>(istream& is, pair<T, U>& p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
void print(const T& v) { cout << v << '\n'; }
template <typename Head, typename... Tail>
void print(const Head& head, const Tail&... tail) {
    cout << head << ' ';
    print(tail...);
}
template <typename T>
void dbg(const T& v) {
#ifndef EVAL
    cerr << v << endl;
#endif
}
template <typename Head, typename... Tail>
void dbg(const Head& head, const Tail&... tail) {
#ifndef EVAL
    cerr << head << ' ';
    dbg(tail...);
#endif
}
static constexpr ll inf = numeric_limits<ll>::max() / 2;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

無思考で書けるってレベルのデータ構造等は以下の通り

  • Segment Tree
  • Lazy Segment Tree
  • Binary Indexed Tree
  • Heavy Light Decomposition
  • DSU(Union Find)
  • Bitwise and,or convolution
  • ダブリング LCA

まあ書けそう

  • O(N)空間LCA
  • 64分木 Set
  • Sparse Table
  • Wavelet Matrix
  • 永続配列
  • Undo可能Union Find
  • SCC
  • Rolling Hash

ギリギリ

  • CHT
  • Static Top Tree
  • Dinic(フロー)

これを書いていて今年はいよいよ最後なのかと思うとしみじみとした気持ちになります。

おおまかな戦略

昨年の反省を生かしてルーティーンみたいなものを作って冷静でいられるようにしました。

  • 最初の10分は環境設定とテンプレートやらスクリプトやらだけに使う。実際にそのくらいかかる。終わってから問題が入っている封筒を開く。
  • 最初に解く問題はBatchの中で制約/小課題の設定や問題の分量から総合的に判断して一番簡単そうな問題を選んで解く
  • どうせ時間はあるのだから、分かった小課題はすぐ実装する(多少は次の小課題を考えたりはするが、わからなそうだったらすぐ撤退する)
  • 20~30分くらい進捗がなくなったら次の問題を開封する
  • Communicationは2問目として見る。自明な部分点がよく配置されているから。
  • トイレは気分の切り替えのために行くのを惜しまない
  • 2時間30分時点ではすべての問題を開封する。

(以降、問題のネタバレがあります。)

Day 1 (3/21)

おはようございます。良い睡眠ではなかったけど十分な睡眠は取れました。頑張ろう 行きで吉祥寺でhiikunZと遭遇してそこからNTT駒場まで一緒に行った

競技(覚えてる範囲で書く)

A

まず読んで、嘘貪欲が生えてそれを実装して小課題1が通らないな～を30分くらいして、他の小課題を見たら小課題4でTLEしてることに気付く。

制約を見ると、Aに含まれるiの個数も大事であることに気付いて、1,2,3,....と追加していったときにiで被覆できるかできないかという問題になることに気付いて、ちょっと考えると区間スケジューリング問題に帰着できる。2年前も区間スケジューリング問題がそういえばあったな。テキトーに O(NM^ 2 \log M) を書いて19点。嘘貪欲の方も二次元セグ木を使うと高速化できるが、とりあえず後回しにしようと思う(45分くらい)

B

コミュニケーションは意外と正の得点は得られるから見た。問題読んで確認がてら3点を取る。得点計算を見るとなんか点数のつけ方キモくない？となる。

ちょっと考えると2文字ごとに00と11だった場合に送れば450を基準に差分が取れることがわかる。これで16点。どう考えても優位になる点数を取るのにL=40とかを達成しないといけなくて、ちょっと考えるけど無理そうと思い撤退した。(75分くらい)

A

9点の小課題2や19点ある小課題3も解きたいと思って考えるけどどうやっても O(NM^{2} \log M) かかるが？とか言ってた　100分も経ってたのでさすがにCを見ることにする

C

グリッドで一瞬嫌な気持ちになるが、問題を読むと意外に素直な設定で、50点まではストレートにいける。50点を取って、ちょっと考えてみるとダブリングが降ってきて、クエリで並列二分探索すればうまく行くことに気付く 100点の実装は40分くらいかかった。180分くらい

A

ここらへんでUcupにdynamicな区間スケジューリング問題があったことを思い出す。これ

ただ、upsolveしてなくてlink cut treeであることしか覚えてなかったので何も役には立たなかった。

とりあえずBはやりたくないしわかってる二次元セグ木解(小課題4)を書く O(M \log^{2} M) とかでTLの余裕はそんななかった。実装に時間かかった上、うんうん考えてたら残り30分くらいで空間/時間 O(MN \log M) の解が思いついて実装してみるが、MLEした。ギリギリまで粘るも伸びず

31-16-100 計147 で 2位でした。上が173で下が143と団子の先頭みたいな感じで順位にしては余裕がない立ち位置。つらい。

Day 2 (3/22)

おはようございます。快眠。頑張るぞ～

競技

今日は提出画面の写真を撮ってきたので、色々書ける

A

自明な指数として O(4^{N}) がある。 次に O(NT^{3}) の多項式があるが、多項式はできれば N に偏らせたい気持ちになる。

別の指数として $O(N2^{N})$ が小課題にあったので、とりあえず $O(NT^{3})$ だけ実装する。

うんうん考えていると、対角線上の二つの救急車は患者を取るか取らないかは X+Y (あるいは X-Y) について単調なので、片方の対角線で取る患者を決め打って取れるだけ取るを実装すると $O(N2^{N})$ になり、無事35点。

Y座標が全部同じやつは今度は単純に Y軸に平行な組の救急車同士で考えると部分和問題もどきになる。それを通して 50点。ここで60分経って、$N \leq 45$ を通したいので、考えるが無理なので70分時点で撤退。

C

またCommunicationだけど、自分のプログラムがやり取りする系ではなく、木系なので高得点は狙えるかもと思う。

とりあえず直線とスターグラフが自明だったからテキトーな二分探索をする20点 (100分)

とりあえず木でうまくやれば 2N になるので、それも実装してさらに15点 (120分)

さらに5点は取れそうだったが実装がめんどうだったので、先の小課題を考えていた。わからずAに戻る(135分)

A

有意な進捗はほぼないが、ななめ二つを固定したいみたいな考えはこのときあった。結局諦めてBをとりあえず見ることにする(145分)

B

問題を読むと、実は単純な設定であることに気付く。(二回目のiの出現,一回目のjの出現)となっているような組のswapで高々1種しか増えず、結局01列の転倒数が本質。愚直で確認しようと思い、実装すると45点入る(160分)

転倒数の前計算部分でBITをテキトーに使えばまず自明な改善ができて、66点になる。(170分)

クエリ計算の部分ではLi Chao Treeが必要とか一瞬思うが、実はx座標だと思っていたものが傾きで、傾きが定数なのでテキトーにやればいいことが判明する。問題文のXって変数やっかいすぎ！テキトーに実装して無事100点 (180分)

一気に30分くらいで100点取れてさすがにほっとする

A

さっきのななめ二つ固定を考えるが4次元セグ木とかになり、明らかにおかしい。結局よくわからず一旦わかっているめんどいCの部分点に行くことにする

C

2Nだったのを $N+4\log_{2} N$ とかに改善する。最後の二分探索を結構さぼったので怖かったけど無事通る +5点 (計40点) 200分

A,C

70分くらいずっと行き来して考えてたが全然わからん。Cはどうせ重心分解/HLD系統なのでさすがに通せる見込みはなさそうと判断して途中からはAに比重を重くして考えていた。

A

終了十分前にトイレに言っていたら天からAの81点(最後の小課題以外)の解法が降ってきて、4つに区切って4つとも部分和もどきをするとうまく行くことがわかる。熱烈実装をするが、間に合うはずもなく....

競技終了後にForestedさんにAの思いついていた解法を話したらそこから満点はすぐだよと言われた。昼飯中は頭が働かなかったのでよくわからなかったが、解説聞いたらもう10分くらい考えたら思いつくようなシンプルな改善だった。もうちょっと早く思いついていたら....と思うがまあ仕方がない。 hirayuuがA,Bの満点を開始150分でしたらしく、圧倒された。

今日はA,Cを考えている時は特にイライラしてしまい、マスコットに当たっていました。他にも振り回していた気がする。

day2 は 50-100-40 計190 で単体2位、二日間総合2位です。トップが入れ替わったが、相変わらず激しい代表争い集団の先頭になんとかいるって感じで苦しい。昨日からしおむすびと4点差だし。逆にトップとの差は開いて、結構しんどい。明日も頑張るぞ！

Day 3 (3/23)

5:45に一回起きたけど二度寝に成功。おはようございます。やるぞ～

朝、会場でOutput-Onlyは出ないだろ～（笑）とかしおむすびとほざいてた(フラグ)

競技

最初の十分の環境構築をしていると、唐突に競技システム上にアナウンスがあるので確認してくださいというアナウンスがありテンプレートの実装中だったが見てしまい、なんと今日Output-Onlyがあることが判明した。とんでもない。助けてくれ

B

一番素直そうな見た目していたので考えることにする。11点は簡単なDPなので実装して一回TLEするがpragmaとかテキトーにつけて通る(24分)

$ N \leq 5000$ を考えていたが、テキトーに考えた貪欲はなにもうまくいかずうんともすんともいかない。

小課題が多いので後の方を見ると文字種が少なくなる部分問題の小課題がある。これは簡単な貪欲が回るので実装してさらに8点を得る (52分)

Z=0も考えるがわからんのでもう一つのBatchであるAに行くことにする

A

とりあえず愚直なシミュレーションが $O(QN \log {L} \log {N})$ になるので、書いてワンチャン59点ないかな～とか思いながら24点をとりあえず取る。(69分)

35点は取れたらデカいので色々定数倍高速化を試みる priority_queueやsetを使うような解法しか思い浮かばず、色々苦戦して気づいたらほぼ1時間経ってたので仕方なく重い腰を上げてOutput-Onlyを見ることにする。ついでに、乱数とかの書き方を頭の中で思い出させる。

C

問題文がとにかく長い！読解を頑張るととりあえずN=4は手で解をすぐ書けることに気付く。とりあえずL=3で9点(127分)

提出する時にL=2になったので1分後に出して16点になる(128分)

N=32を考えると、とりあえずbitごとの情報をまとめて～とかしたくなり、考えると $\frac{N}{2}+ log_{2} {N} -1 $ が思いつくので実装する。5bitなのを忘れててペナを積んだが無事通る(139分)

急にBinary Indexed Treeの気持ちになり、頑張るとL=9が達成できそうなことがわかるので、実装する。バグらせたりしたが一発で73点になる。うれしい。(160分)

よくよく考えると、BITの子の方が無駄なクエリを投げているので、そこで情報をできる限り得ようとするとL=8が達成できるのでうまく実装する。ちょっと遠回りして時間かかったが無事通る。76点(174分)

最後にN=48を考えるが、N=32でやっていたのと同じ感じで、BITみたく和を計算していくパートをやってそのあとにN=32のときから一手だけ多くかければまたN=32の時の状態に戻ることが分かったのでコードの定数とその1手を書き加えて無事満点！(181分)

A

35点が取れる可能性が割とあって、取れたらデカいので粘着することにする。とにかく色々な $O(QN \log {L} \log {N})$ 解法を考えて、全部実装するという気持ちでやる。紆余曲折し、bitsetで高速化が効く解法が思いついて、実装すると35点の小課題を正解できた！最高！ (270分)

この35点がとにかくしんどかった。

B

テキトーな貪欲を書いては捨てるを30分くらい繰り返して終わった。まあ今日の最難かな？とは競技中感じていた。

結果的に 59-19-100 で計178点 Day3単体2位で全体1位になりました。hirayuuがOutput-Onlyで大きくコケていたので、1位になってしまった。5位との差は69点で4位との差は67点。明日は何もやることが無くなるまで粘着を絶対にしないことを肝に銘じて取り組まねば....

Day 4 (3/24)

いい睡眠をとって無事起きました。おはようございます。やったるぞ

競技

今日は色々あってあまり覚えてないですが、なんとなくの動きは覚えてる。

C

初手で読むと15点はとりあえずわかるので通す(30分くらい)

なんとなく小さい方から右から取って行く貪欲が思いついたのでそれも実装してみると30点(54分)

この貪欲をいい感じにやるとどうやら満点解になるようだがどう考えても高速化できないだろ！とか言ってわからなかったのでCommunicationのAに行くことにする。

A

初手で $N \leq 1000$ は自明なので通す(10点)

次に直線と二分木をそれぞれ考えるとそれぞれいい感じの二分探索が回るので通せて、これで50点になる。$(R \leq 70)$ しか取れていないが、どう考えてもこれより早くならなくてこまったな～をずっとしていた。

ただ、これらの実装でかなりバグらせて焦っていた。

+27点の解法はHLDしてheavy-pathを頂点とするとうまくいくことはわかっていたが、競技開始120分経っていたのでBを見ることにした。

B

読んだ感じマージテクとかを頑張る実家な感じがする。頑張って落とそうとするがなかなか二乗とかから落とせなくてこのあたりでかなり苦しくて、代表落ちを覚悟し始めた。

わからないのでとりあえず自明部分点を回収すると12点が得られる。

$T_i=2$ がない場合をとりあえず考えることにしてしばらく考えていたが、なんかそれらしき解法が思い浮かんだので実装してみるとなんかTLEする解法しか生えてないしで流石に焦り始める。色々実装してなんとか $T_i=3$ が5個以下の小課題は取れた。

C

この頃(210分くらい)からどの問題も満点は諦めて取れる部分点を取り切ることにしようと思い始めた。他の人がそれなりに失敗している可能性を信じ、自分がなんとかこの三日間で得た貯金を消費しきるギリギリまで部分点が取れればそれでいいんだという気持ちです。

とりあえず $A_i \leq 2$ の場合を一旦考えていい感じに関数合成で表せそうなことに気付き、実装するがWAが返ってくる実際ランダムテストを回してみると落ちることがわかる。流石にどうしようもない気持ちになり途方に暮れていた。(解説を聞いた感じ実際に関数合成みたいになってセグ木に乗るらしいが、競技中生やしていた関数合成は明らかに嘘であった)

B

時間が無くなり残り 15分とかになって、なぜか自明なの実装していなかった $D \leq 20$ を実装するが焦りもあり合わない。シグナル11(メモリ制限違反の可能性があります)のREで落ちているらしいが、メモリは全然使っていなくて本当に焦った。結局通らず終わってしまった。この13点で代表落ちしたら実装しなかった自分を一生恨むだろうな～とか思った。

点数は50-27-30 で107点でDay 4 単体は8位だった。

競技終了後は代表落ちたと思い絶望していました。競技会場を出て最初に点数を聴いたのがしおむすび,hirayuu,hiikunZで、自分がかなりの点差で彼らに負けていたため彼らがこの点数なら4,5,6位の点数もかなり良いだろうと思えて更なる絶望を味わいました。

結果的には、4,5,6位が失敗していて差が広がらずに済んだため3位フィニッシュでした。147-190-178-107 の合計622点でした。

ポエム

去年はDay 1で大コケして部分点を取ろうとしなかったムーブを反省し、Day 2から取れる点数全部取る戦略をして残り三日でいい感じの成績を残すことがでていました。なので、全体でみれば無駄は多いかもしれないがこのムーブが正しいと信じてやってきました。

ここ1年は5hに完璧に慣れて勝負強さを身に着けるためにUniversal Cupに積極的に出ていたり、忙しかったりする時期でも日々競プロのことを考えながら生活してきました。この努力は報われて、やっと雪辱を果たすことができた。

応援してくれていた友人やUCをいつも一緒に走ってくれるriano_さん、そして中一の頃からよきライバルであってくれた多くの同期には感謝してもしきれないです。

ただやはり、Day 4は悔いが残る結果だったのでこの気持ちをばねにIOIに向けて頑張ります。

IOIでも応援よろしくお願いします。

JOI2024/2025本選参加記

参加記

2025年1月26日,2月2日に開催されたJOI2024/2025 本選に参加しました。結果は100-100-100-46-25 合計371点で総合5,6位くらい(真偽不明)でした。

二次予選

今年はISUCONに参加していたため、二次予選に参加しませんでした。シード権を使用して本選進出です。前回大会の春季トレーニング参加記はこちら:

mt-saka.hatenablog.com

本選Day1

  • 講義が非常に面白くて普通に論文を読んでしまった。
  • 双子に代わって他チューターらがチューター企画をやっていた。今年はGartic Phoneみたいな感じで、お絵描きで競プロの問題文を伝えてコンテストフェーズで絵から問題を解くというような競技だった。CMSを使うのは新規性があって面白かった。各チーム2グループに分かれたが、自分のグループは問題を解くパートがあまりうまくいかず、悔しかった。なにはともあれ、楽しく交流できたので良かった。来年以降もチューター企画が開催されるのだろうか🤔

本選Day2

競技当日

時系列でコンテストでのムーブを思い出します。

13:00 競技開始 practiceの時コンパイルコマンドがなんだったか確認し忘れたのでここで確認してデバッグライブラリをこれに合わせる

13:06 A_1,B_1 だけ無視して累積maxを取って尺取り法をしろと書いてあるのでやる A AC 100点 6:24

13:11 (必要な強さ,増加する強さ)の組がモノイドになって、マージも簡単にできるのでセグ木でできる B AC 100点 11:34

13:11~13:45 Cを読み、 N,M \leq 8000 と P \leq 100 は見た瞬間わかる。 f(l)= ( l 以上の会社を使える時、 r 以下の会社のみですべての頂点を行けるような最小の r) を各 l について求められればあとは(座標圧縮した上で) r-l とかを持つセグ木を使ってやればいい。 f を求めるパートがどうしても \mathrm{O}( (N+M) \min (M,P)) かかってしまってそこから進展せず30分くらい経ってしまったのでとりあえず実装することにする

14:00 実装して出してみたが0点でちょっと焦る C 0点

14:16 直ったと思って出すが7点 どうやら クエリを答える部分で X=0 の場合しかできてないようだ。そこを重点的に見てバグを探した C 7点

14:22 場合分けが足りておらず実装しなおす C 48点

14:28 48点を提出した直後、このグラフがDAGであることを思い出し、すべての頂点についてその頂点に入る辺がありさえすればかならず頂点 1から到達できることに気付いて f を求めるパートだけ書き換える。10行くらいの書き換えで済んだ。かなりのアハ体験だった C 100点 88:19

14:46 Dを読んですぐに各長さは高々一つなのでbitで集合を持てばいいことがわかって 46点は取れそうだしもしかしたら72点も行けそうだし実装は楽そうだったので実装する。D 46点 101:08

この時くらいに春は大丈夫そうだなと一安心する。あとはメダル目指してがんばるだけや！

72点取れたらかなりデカそうなのでbitset高速化や定数倍改善をしようと色々試す。しかし、結局何も46点から改善せず 72点取るまであと2ケースくらいにはなったがさすがに厳しかった

ここまでで15:15くらい

一旦Eを読んで取れる点数を取ろうということでDからEにシフトする

Eを読むと愚直で12点取れそうだとわかったとりあえずこれと直線の木だけで50点取れるのでこれはデカいと思い考える。程無くして13点の小課題3はAとBの境目に注目してどんどんそこに到達してくるみたいな感じで考えるとうまくいった。これが実はそのまま小課題4に応用できるものだったが頭が動いておらず...

15:57 そのまま30分くらいEで小課題4すら解けなかったので 小課題1,2を実装することにする E 12点 177:34

16:12 小課題4も解けないか模索したが駄目そうだったので小課題3だけ実装する E (累計) 25点 192:04

このあとはEの小課題4のテキトーな嘘(2ケースしか落ちなかった)やDの定数倍改善/テキトーな嘘を投げたが結局うんともすんとも行かず競技終了

終了後みんなの点数開示ですぐさま3人くらいに負けてることがわかりメダルなし！

Dのhirayuuの嘘は考えなくもなかったので悔しいなあと思った。実際翌日(2/3)起きて実装してみたら100点取れました。マジかよ。

Eはこの記事を書く直前に本質を頭で理解できました。かなしいね。解説の図がHarvestみがあってHarvestだなあとか言っていたが本当にHarvestだなあ。

正直悔いが残る結果でした。Cで少しモタついたのと、D,Eでろくに点数で取れなかったのはかなり悔しい。Eは本質にほぼ近かったんだけどいい感じに整理できずノリで50点獲得まで行けなかった。(Dが頭でちらついて思考が整理できなかったと思う) 自分の特徴として複数の問題を同時に考えるのは苦手なんだろうか

今年はIOI日本代表になる最後のチャンスなのでボリビアへの切符を獲得するために残り40日程度頑張ろうと思います。

JOI2023/2024 春季トレーニング 参加記

参加記

JOI2023/2024春季トレーニングに参加しました。結果から言いますと四日間総合8位で代表にはなれませんでした。

本選

正直結果が良くなかった。そのせいで参加記とかを書く気が起きていなかったので書いていないしもうあんま覚えてないので言うことがない。なんとか通過はした。

春合宿まで

難易度11を中心に解いていてあとは意図的に残していた2020/21春を四日間バチャをした。結構良かった。
春前の感触としては上位6とかにいて代表争いをしているだろうというイメージでいた。そういう場合のイメージトレーニングみたいなことをしていた気もする。

Day0

practiceでN=1000のワーシャルフロイドやるだけがずっとTLEして解決せずに終わりちょっと心配だった。(が、結局本番で定数倍で死ぬことはなかったのでまあヨシ)

ここから問題のネタバレがあります




Day1

結果から言うと9-0-12 計21点 同率24位(実質下から二番目)だった。
この日は絶望の一言。まだあまり思い出したくないのでちょっと忘れたころに詳細を書くつもりです。とにかく後半2時間の記憶が全くというほどない。
家に帰って雛鶴 あいみたいに大泣きした。

結果的に、心を入れ替えてDay2以降取り組むマインドに切り替えることができた。

Day2

boardgame

小課題1~4は丁寧に状態を考えて解くことができた(この時すでに自分の中ではO(N2/K)に落ちていた)
あとはK<=100さえ解けば平方分割で解ける！と思い考察するとプレイヤー2~Kのコストは傾き1,2の半直線であることには気づくがうまく言語化ができず後半の疲労感の中考察していたのもあり、迷走してしまいちゃんと詰められなかった。(反省)
結局小課題1~4だけの36点

tricolor

全くと言っていいほど考察が出なかった。こういうパズルは一生苦手だと思う。5点しか回収できなかった。頑張ったら15点はいけたなあと思ったが40,50点を取っている人が理解できない...

vegetables5

この日問題を見て一番解けそうだと感じた問題だったので一番最初に取り組んでいた。
小課題1~3を回収した後は難しい考察をあまりせずに20分~30分で O(Nlog(N)log(A)) の満点想定を思いついた。
とにかく添え字を合わせるのが不快だが、添え字を合わせる以前にTLEが出て絶望した。結果的に他の問題を回収した後に最後に再び取り組んで、軽い O(Nlog(N)log(A))でもなんとか通せる小課題4だけ取れた。この後最後の5分とかで添え字を合わせた解が出来上がり、提出するがTLEしてかなりつらくなった。
解析で単調性を利用してlower_boundのlogを尺取りすることで落としたら満点が取れた。10分くらいしかかかってないので他の問題に割いていた時間をこれに割けば...と思ったがもう遅い。

36-5-67 計108点 Day2単体3位と割と良い結果となった。

Day3

collection

最初に見た問題で、初手の考察で O(N^{3}M)の区間DPに簡単に落ち、Nの次元を一つ落とせば一気に38点入るため頑張って区間dpの改善を考えた。考察をしたが大胆予想をするしかないと考え大胆予想をして実装するがWAで撤退した。結果的に最初の一時間をこれに浪費してしまった。

joitour

問題を真面目に考え始めた時点で時間が微妙に残っており、満点特攻するなら特攻するくらいの時間しか残っていなかった。HLDを使って根へたどっていって情報を更新すればいいことには気づいていたが、情報量が多すぎて頭の中でそれを管理する方法がうまく思い浮かばなかったため結局部分点をちまちま回収することにした。
部分点自体はそれほど難しくなく、丁寧に実装して52点を取れた。ただ、中途半端に時間が余った。

tower

この日の三問で一番解きやすそうに見えた。段数/時間のグラフを考えて非連続になる点を考えるという方針でやると区間を管理するテクだけで割と簡潔に書けた。ただこの考察にいきつくまで紆余曲折しており、実装も結構バグらせて時間がかかった。
何度も提出してなんかいつの間にか満点が取れた。ついに初の満点である。

11-52-100 計163点 Day3単体2位でDay2,3だけの成績だと1位だった。総合も8位まで舞い戻った。これでDay1で底辺にまで落ちた自信がちょっとだけ取り戻せた気がする。ボーダーとは80点以上差があったので厳しいなあと思ったがワンチャンを狙える位置ではあった。

Day4

escape2

ようやく実家が出てくれたという感覚になった。絶対に満点を取るという強い意志でダブリングを実装し、平方分割をして満点が取れた。ただ実装に無駄に時間がかかった。ちゃんと鍛えていたはずだが三日間の疲れが予想以上にあったのだろう。

island

面白いパズルで今までのどの日のcommunicationと比べても取りやすいだろうと思った。ただ、全然うまく線形回のクエリに落とせなかった。
結局クエリ数は(次数の最大値)*Nくらいしか実装できず50点。
人々の満点解法がきれいすぎてびっくりした。こういうのは解ききりたかった。

tabletennis

解の上界の評価をしてその結果をもとに3すくみの個数を頑張って山登りとかすれば解が割と高速に求まるんじゃないかと読んで実装したが評価からうまく行かず失敗してしまった。
最後20分くらいはなんとかN<=20を埋め込むでもして23点だけでも自明部分点以上を回収しようと思い、頑張ってコードを回したがそもそも間に合わなかった。

100-50-9 計159点 単体8位(多分) 総合8位(合計451)

結果的には昨年度と同じ順位まで追い上げることができた。すべてはDay1が悪いが、そこからの修正力には自信を持ちたい。
来年は代表になります。頑張ります。

【色変記事】AtCoder橙になりました

色変記事

2023/2/18のARC172で橙になりました。ずっと目標だったので本当に嬉しいです！

自己紹介

・私立中高一貫男子校の高1
・中学入るまではscratch触ったことある程度
・中1の12月から競プロをやり始めた

黄色になるまで

↓これ mt-saka.hatenablog.com

橙になるまでやったこと

・AtCoder上で1500問ぐらい解いた
・JOIの勉強
春合宿の勉強でかなり鍛えられた
・5hコンテストにたまに出る
頭を動かし続ける体力が得られた気がする
・Good NotesをiPadに入れてiPadで考察するようになった
図とかが描きやすくて考察が捗る

諸々

これから

本当はもっと深夜にやってるコンテストに出たりしたい。高校卒業するまでは我慢するしかないけど。
あとAtCoderのWriterもやってみたいです
もちろん目標は赤になることなのでこれからも頑張っていきたい！

ISUCON13に参加して再起動チェックでfailしました

参加記 ISUCON

はじめに

ISUCON13にチーム「ナニモワカラナイ」で出て再起動後のデータチェックで不整合があったためfailとなりました。
最後のベンチのスコアは83,615でした

チーム紹介

MtSaka: インフラナニモワカラナイ、Goを多少できるつもり これを書いている人
NaHCO3: 直前一週間の練習会でSQLを極めたN+1解消担当(重曹と呼ばれている)
hiikunZ: DBスペシャリストでインフラ含む全てを理解する人
自己紹介スライド供養

練習

ISUCON11 final,ISUCON9 予選の二つを走りました。
ISUCON11 finalはあまり振わなかった
ISUCON9 予選はかなり力を出しきれてもうボトルネックがアプリが使ってる外部APIだけみたいな状況になるまで突き詰めることができた。本番のスコアと比較したところ1位を優に超えるスコアを取れていました。ビックリ

本番当日

9:30

全員起床成功していた。
みんなでdiscordのボイスチャットに集まりYouTube togetherでライブ配信を見ながら今年の問題を楽しみに待っていた

10:00(開始直後)

重曹がインスタンスを立ち上げ、hiikunZとMtSakaがマニュアルを読む

10:10

インスタンスが立ち上がった後Git管理などのすでにまとめてある初動をhiikunZがする。重曹とMtSakaでアプリのマニュアルを読みアプリの概要や仕様を確認する。

10:20

何もツールなどを入れてない状態でベンチ
スコアは3,896

11:15

hiikunZが初動を終わらせ、自分がpprofを入れてベンチを回す
スコアは3,462
明らかにstats_handler.goの全てが重いことがわかったのでSQLの改善を重曹に投げる
hiikunZはDNS関連の改善やサーバー構成いじりに走り、自分はtagsのオンメモリ化をすることにした。

12:50

hiikunZがDNSの改善と3台構成へのシフトと自分のtagsのオンメモリ化が終わる
スコアは3,806

13:00

重曹がuser_scoreおよびlivestreams_scoreの二つの新しいテーブルを作成し、それを用いてuserのstatisticsの高速化をした
と思ったらバグっていて、それをなおす作業が始まった

14:20

バグが直り、やっとベンチを走らせることに成功した。
スコアは4,028
そんなに上がらなくてちょっと落ち込んだ

14:45

重曹がusersの非正規化を行い、DarkModeを入れた
と思ったら再びバグって一旦revertすることに

14:50

自分はlivestream_tagsがinsert以外行われないことに気づいたのでそれをオンメモリ化した
と思ったらバグってrevert...

15:40

livestreamのstatisticsのN+1の解消を重曹とhiikunZがした
少しバグって時間がかかったがスコアが少し良くなった。
スコアは4,171

16:00

この時間になってようやく調子が乗ってきて怒涛の改善が入るようになった。
まずは重曹はiconのhashをusersのテーブルに組み込んだ
スコアは7,036
ブレイクスルーを感じた。

16:05

このブレイクスルーの時にmoderateとlivestreamsのsearchが重いことに気づきとりあえずmoderateで自明な改善を自分が入れたらmoderateはかなり改善したのでスコアは落ちたがそのままで行くことにした。
スコアは6,720

16:30

その後hiikunZがlivestream_tagsのオンメモリ化に成功して重曹がlivestreamsのsearchのSQL改善に成功する
少しバグったりしたが、うまくいき第二のブレイクスルーを経験する。
スコアは12,925

17:00

iconsが重いことに気づき、hiikunZが/iconsをDBで持たずにファイル保存する方式をとる。
自分はiconsの更新が2秒毎で良いことに気づいてfillLivecommentResponseを2秒毎にキャッシュ保存することにした。
スコアは21,478

17:30

fillReactionResponseも同様に二秒毎で良いことに気づきそれをキャッシュ保存した
スコアは48,684
これでいったん重かった部分が全部解消される。

17:32

livesreamのsearchのSQLのチューニングを重曹がしておりそれをする
スコアが伸び悩み少し不思議だった
スコアは49,277

17:45

実は貼られているはずだったINDEXが貼られていなくてそれに自分が気づきhiikunZがINDEXを貼る
重曹のSQLチューニングがブッ刺さり、スコアが大幅に改善
スコアは81,286

17:55

pprofを自分が消し、hiikunZがslow-logなどを消して最終ベンチを走らせる
スコアは83,615

17:59

hiikunZがいきなりこれはfailします！とか言い出して怖くなった。
マニュアルを見てみると 負荷走行実行時にアプリケーションに書き込まれたデータが、サーバー再起動後に取得できない場合 と書いてあり、実装を見直すとtagsとlivestream_tagsのキャッシュが再起動後も動くような仕様ではないことに気づいて絶望した。

お祈りをしたが結局failであった。スコアで言えばtop30でかなり奮闘していたのでとても悔しい。

総括

良かった点

終盤の怒涛の改善とそれに伴うスコアの上昇はとても良い経験で実際いい感じに改善が回っていた。今までに味わったことのない改善速度でビビった。

悪かった点

インフラをまともにできるのがhiikunZしかおらず序盤でかなり負担がかかり、まともに改善を回せるまで時間がかかってしまった。来年以降は最後の一時間くらいの状況になるまでの時間を早くしたい。終盤でパラメーター調整をする時間がなかったりして少しもったいなかった。
また、まだ改善があるという状況だったのでやはりもっと序盤でスピーディーに諸々ができるようにしたい。

来年に向けて

自分はGoの一部知識不足だったり、インフラの無知さで迷惑を少しかけたと感じているのでそこら辺をある程度勉強したい。
来年の形式がどうなるかはわからないが、入賞したい。