この記事は夏のブログリレー21日目の記事です

はじめに

これは 8月30日から9月6日にかけてアゼルバイジャンの都市 Baku で開催された ICPC2025 World Finalsの参加記です。

我々は東京科学大学のチーム「Bocchi The Tech」として参加しました

チームメイトは simasima と Series_205 で コーチは tatyam です

大会以外について

twitterにそれぞれの日程で何をしていたのか写真を色々あげたので見ていってください

準備

大会の少し前あたりからはチームメンバーと一緒に WF の過去問などを解いたりしていました。基本的にオンラインでやっていて、大会直前に対面練習をすこしだけしました

ライブラリなどはplayoffで使っていたライブラリに何か追加しようみたいな話があり、追加する部分は Series_205 にほとんど任せっきりになりました (ありがとう)

practice

まずはパソコンのセットアップから
前に一度簡易的なAIコードアシスタントを使えたことがあった気がするので、CLionを用いてセットアップ
ひとまず色々書ける様にしたが、そんなものは存在しなかったので色々使い慣れているVSCodeに変更
全完可能セットっぽかったので全完を目指してACを増やしていく
最終的にB問題だけが残りsimasimaが実装をしたものの、ACにならず…残念
終わったあと、Screen walkers に聞きに行ったところ探索の範囲が足りてないらしい?(考察をちゃんと聞いてない)
あと、ジャッジのスピードが異様に速い or TLE時の強制終了が30秒とかになってるかのせいで手元で24秒程度かかるコードがWAになるらしい

ICPC Challenge

準備

codeforcesの環境でひらかれるらしい
事前に聞いてた情報だと、あまり問題としてちゃんとしてなくてテストケースなどちゃんと見たほうがいいらしい

3時間しかないもののgeneratorやテストケースをしっかり見る方針で行くことになった

問題概要

画像の配置を決める問題でした

4, 6, 9, 12, 14, 18 などの特定の幅や高さによって嬉しさが決まっていて、画像をとある幅に空白がない様に埋めていきます

スコアはT字の数、嬉しさの合計、大きさの種類の分散、合計の高さなどによって決まる問題でした

コンテスト本番

序盤は自分が環境構築をしつつ最低限のACコードをかきつつ、残りの二人がgeneratorなどをみつつ考察をする形に
自明なACコードを書き終わり、提出したところ TLE
何これ？cinのしすぎか何かで処理が終わってないのか？と思ってたら Series から入力高速化の提案が

cin.tie(0)->sync_hogehoge(0) 

を入れたところ 700 msec で AC
なんだこれ？入力でTLEって許されて良いのか？

最初のACを出した時点で20分程度経ってた気がするが、ちょっと実装を考えるか何かで隙間時間が生まれた
サンプルにいい感じの解があったのでサンプルにあるケースはこの間に埋め込んでおいた

ここからSeriesが幅,高さがどちらも6の倍数の画像のみをつかって画像の大きさの分散やスコアの合計がいい感じになる様に実装を開始

その間にsimasimaに問題概要や考察の結果などを聞き、自分でも考察を開始した

長さ 4 を含む大きさの画像を使いずらいなーと考えていたら、短冊形に設置していくことを思いついた。しかし、作りやすいとはいえ結局分散は良くならないかなーなどと考え、とりあえずSeriesの実装が終わるのを待つことに

Seriesの実装が終わり提出したところ、168点と上位には届かない様な点数

ここで少しパソコンが空いたのでその隙に短冊に設置していくDPを書くことに
いい感じに全探索できるかなと思いDPの高速化は一切せず提出したところ200点 + TLE となかなか悪くない数字

ここでいい感じのTLE対策を思いつかなかったため、TLEになるケースを探してみることに、
幅が大きくtotal_nの大きいケースでTLEしてそうなので一時的に最初のSeries の書いた解法とmergeをした
すると 260 点とかなりいい感じの点数が出た

DPをする時に幅を決めた際の置き方を全探索しなくても良い(いい感じのタイミングで探索を終了させる)ことに気づき、それを入れてみたところTLEが消え264点になった

この時点でもうかなり時間がなかったのでグループ内でシャッフルをして何度か試行し、一番よかった解を出すコードを書こうとしたがバグを埋め込み時間が足りず

結果としては20位になりました
もう少し早めにDPに気付けていれば、シャッフルする前にスコアを微調整する方を選べば、色々反省点はありますが、明日はWF本番なので深く気にしすぎないようにしました

ICPC World Finals

いよいよ ICPC 本番がやってきます

我々のチームの戦略としては 以下の記事の戦略に近く、simasima がほぼ全ての問題の考察を行い、残り二人で実装をしまくる形です

初動では僕がセットアップを担当し、残りの二人は前と真ん中からよみはじめます。パソコンの画面では基本的に左側で実装をし、右側では常に順位表を確認できる様にしておきます

セットアップも終わり、自分が後ろから読み始めた頃 L のAC が出始めます。

L はy軸のみを考え、どれだけ日差しを見ないかの問題なのでそのまま実装を始め、AC

その間に F 問題が解けたらしく Series が実装を始める

考察の終わっていらしい J の考察を受け取る。 J の方はまだAC が出ておらず、FA を狙いにいくかという話もあったが、いまいち細かい部分の場合分けを考えられず、Dをそのまま Series が実装

その後、I 問題も受け取り D のバグらせている間に実装を開始、一度種類数をN にするタイミングで入力を受け取り忘れておりバグを埋め込むなどしたものの、結構早めに直すことができ AC

そのまま J の実装に移る。できない条件は sum > h, h < n*2-1, h = sum-2, h = 2 のどれかだけであるので、その条件を最初に除き実装を開始

再帰的に問題を解いていくのだが、自身のサイズ + 2 の大きさのブロックを処理をする部分で頭をバグらせ、ペナを出す。一旦、Seriesに実装を渡し、実装を考え直す。その後、実装をしなおして提出するもまたもWA、intを使っていることを指摘され long long に直すと AC (マジでごめん)

Series が H を実装している間に A の考察が渡される。この時点で 6完しており、8完するとメダルが見えてくるよという事前情報があったため、後ろの問題は読まずにAの実装を無限に考える

H がバグらせている間に実装を始めるとかなり早く実装が終わり、サンプルがあっていたので提出、 WA

右の部分木の操作列が左の操作列より長かった際の処理を頭から飛ばしていた

H が通されたのち、その部分の処理を書き AC

8完できたものの、メダル圏内には遠く及ばない

Series が E を解けたらしいので B を simasimaと一緒に考察 (大きいケースはもう解けているらしい)

何も思いつかん

E で WA が出ており、Seriesから解法を教えてもらう。違うルートで連結になっている際の処理がなさそうなのでそれを指摘するとそこで間違っているらしい。

それを直す方法も思いつかず、simasimaが B を書いている間にコンテスト終了

27位になりました...

コンテストの感想

あまりに基本的な部分が足りていない感があり、悔しさが少し大きい

まだ自分にはあと1回 WF へいく権利があるものの、同じ様な実力で行けてもまた同じ感じになるとしか思えない

次回の WF では もっと強くなって帰ってきます

Yes/No ではそんなこともあり、見どころは東大の優勝争いになりました

東大が10完をしていると10完内最速であり、かなり優勝の期待が高まります。10完した際にはもう優勝だろと喜んで見ていると、G問題を終了2分前に通し11完したチームが現れ、2位に (悔しい)

11完したチーム、強すぎるだろ

終わりに

今回、全てのコンテストで微妙な結果となってしまったが、得られたものは大きかったと思います。

また、次の WF に向けてもっと強くなりたい気持ちが高まりました。

あと、今回スーツケースの鍵を無くしました。スーツケースに鍵がかかっていないタイミングだったので結果何事もなくて良かったのですが、荷物の管理がなっておらず反省...

明日のブログリレーは@n3です