ICPC 2023 アジア地区予選横浜大会にチーム DELIAIR (torisasami, tokusakurai, sapphire15) で参加しました。最終結果は 9 完で 8 位でした。

チーム結成まで

DELIAIR は 2021 年 4 月に結成しました。それまでの経緯を簡単にまとめてみます。

torisasami との出会い

torisasami とは大学に入学したとき (2019) のクラスが一緒でした。私が競プロを始めて間もない 10 月頃に torisasami のスマホのお気に入りに atcoder があるのを見て勝手に開いたら、黄色間近の青だったのでかなりびっくりしたのを覚えています。それ以降は torisasami に色々教えてもらいながら勉強していきました。この頃は緑から茶色に落ちたりしてモチベーションが下降気味だったので、torisasami との出会いがなければ競プロを続けていたかはかなり怪しかったと思います。

ICPC 2020 参加未遂

その後は torisasami と切磋琢磨して両者黄色にまでなり、クラスメイトもう一人を合わせて 2020 年の 11 月頃の国内予選に参加を考えていました。ICPC サイトに登録はしていたものの、誰も ICPC の練習をしていなかったり、そもそもコンテストシステムがどのようなものなのかを知らなかったため、結果として参加は見送ることになりました。

sapphire15 の加入

もう一人のクラスメイトは、進学先の学科の授業が忙しくて競プロと疎遠になってしまい、その後は ICPC のことはしばらく考えていませんでした。2021 年 3 月に torisasami が橙になったタイミングで「今年は ICPC 出たいね」という話を持ち掛けたら、twitter でチームメイトを募集してくれました。そこに同学年の sapphire15 が駆けつけてくれ、DELIAIR が結成しました。もっとも、チーム名が決まったのは夏頃なのですが。

今大会への意気込み

結成当初は大学 3 年で、みんなでコドフォバチャを毎日のようにやったりと競プロのモチベが高く、全員上を目指してどんどん力をつけていったと思います。この年度の地区予選は出場が叶わなかったものの、Give us sociablity のコドフォジムでのバチャ練習に頻繁に首を突っ込んだりしていたのもいい思い出です。

大学 4 年になって、みんな研究室に配属されたり院試があったりと、競プロばかりやってないで将来を考えないといけない時期になってきます。torisasami と私はそれでもコンテストやバチャに定期的に行っていましたが、sapphire15 はこの辺りから競プロモチベも落ちてきたようで、私もチーム練習に無理に誘うのは申し訳ないという気持ちを持つようになりました。そんな中でも、Universal Cup の登場によってチーム戦で顔を合わせる機会が増えたのは本当にありがたいことでした。

大学卒業後は全員大学院に進学したので、もう 1 年このチームでやれることになりました。しかし、torisasami や私もインターンなどを通してついに社会を意識するようになり、もうこれで終わりなんだな、就職なり D 進なりみんなそれぞれの道に別れていくんだな、という気持ちは日に日に強まっていきました。

思い返せば、このチームで 2 年半やってきて、楽しかったこと、悔しかったこと、面白かったこと、意見が合わなかったこと、嬉しかったこと、革命が起きたこと、起きなかったことなど、本当に色々なことがありました。全員同学年で、互いに言いたいことを好きなだけ言い合える関係にあったのは恵まれていたと思います。

余程のことが起きなければ今大会が最後の ICPC。正直に言うと、地区予選が終わって欲しくないという気持ちがありました。

そうは言っても時の流れを止めることはできないので、大会に向けてできる限りのことはやりたい、本番では後悔したくないという思いは強く持っていて、それは 2 人にも伝わっていたと思います。

大会に向けての練習

今年は Universal Cup や multiuni があったので、チーム戦練習は主にそちらで行いました。特に、練習では以下のことを意識しました。

US 配列を使う
ライブラリは毎回写経する（写経しやすいライブラリを作る）
チーム内で役割分担をはっきりする

US 配列については 2 ヶ月間これしか使わずに練習をやりましたが、もう JIS 配列を使えなくなるくらいには使いこなせるようになりました。

ライブラリの写経についても、AOJ ICPC も含めて色々な問題をやっていたら、自然と遅延セグ木をソラ書きできるくらいにはなりました。

役割分担については、各人の得意分野に基づいて以下のようにすることにしました。

sapphire15: 問題の考察（特に初手の方針）の案を出す、構築をする
torisasami: 問題文を読解する、sapphire15 の考察を議論して詰める
tokusakurai: 大雑把な解法の実装を具現化する、高度典型っぽい問題の考察

大会前の Univerdsal Cup 2 回は、torisasami の家に行って対面で練習をやりました。

5h コンの経験を通して、最終的なチームとしての戦略は以下の通りになりました。

tokusakurai が最初に環境構築をする
torisasami と sapphire15 はそれぞれ最初に B 問題、A 問題を解き、それ以降は別々に問題を読み進める
実装は基本的に tokusakurai が担当する。2 人が入出力形式とざっくりした概要、アルゴリズムを教えてくれれば後は何とかする
torisasami が自信がある場合は実装を任せる場合もある
ライブラリ写経も tokusakurai がやる
パズル系の構築は sapphire15 に任せる
2 人で同じ問題を考えているのに進まないとロスが大きいので、出来るだけ同時に 2 問以上考えている状態を維持する。

torisasami 得意の adhoc な数え上げや sapphire15 の得意な構築パズルが出ればいい所まで行けるのではないかと予想していました。

大会 1 日目 (11/25 土)

横浜上陸

朝 9 時に起床し、爪切りや支度をして 10 時頃に家を出て会場に向かった。10 時 40 分頃に横浜駅に到着したので、昨年同様会場までぶらぶら歩いて行くことにした。曇りで気温も低く、あいにくの天気であったが、それでも横浜の街はどこにでも人が溢れかえっているような賑わいを見せていた。さすが土日である。夏にインターンに行った某社の横浜オフィスを発見してここにあるのかーと思うなどして、ぶらぶらと torisasami と待ち合わせをしている桜木町駅まで歩く。待ち合わせの 12 時までには少し時間があったので、すぐ近くにある横浜北仲ノットの 46 階展望台へと足を運んだ。以前東京都庁に登った際、友人に横浜に無料で登れるマンションがあるという噂を聞いていたので、一度行ってみたかった場所である。

エレベーターは古いものだったので、昇降だけでもだいぶ時間がかかった。降りた後は 12 時も近かったので桜木町駅に戻ったのだが、なんと torisasami が既にいて驚きを隠せなかった。彼とはもう 4 年以上の付き合いだが、待ち合わせをして間に合ってきたのは初めてかもしれない。

桜木町駅を出てからは、汽車道を進んで会場の横浜産貿ホールマリネリアを目指した。赤レンガ倉庫もまた賑わっていたが、残念ながらスケートリンクの営業には一週間早かった。30 分程歩いて会場近くのザ・ラーメン屋に到着する。やはりこれがないと ICPC は始まらないというものだ。驚くべきことにザ・ラーメン屋は満席だった。並んでいる間暇だったので、会場近くに来ていると言っている sapphire15 を誘って三人で一緒に入店した。

大会初日

食事を終えるとすぐに会場に向かう。会場はすぐ近くにあり、入ると SPJ の Kite_kuma くんがチームメイトの到着を待たされていたので、ほくそ笑みながら先に入室した。チームの席は昨年同様一番前だった。入ったら最初にチーム紹介ドキュメントを見たが、The Raspberry Candies の所にしれっと "DELIAIR = rniya fan club" と書いてあるのを見つけて早々に気分を害した。

少しするとコーチの Irvan 先生が来る。とても気さくで面倒見の良い、素晴らしい先生だ。先生とは挨拶を交えた後、他のチームはまだ来てないのかと聞かれたため「うちの大学は時間にルーズなやつばかりですみません」と謝っておいた。他チームは先生に心配かけさせていることを反省してほしい。

その後は、他の東大チームや夏合宿で交流があったチームなどと少しお話をした後、開会式が始まった。内容はそんなに覚えていないが、インタラクティブ用のツールがあるということには驚いた。

そうこうしている間にリハーサルコンテストが始まった。コンテストでは、CLion のライセンス認証で苦戦して sapphire15 に怒られるなどした後、テンプレートと実行用のシェルスクリプトを書いて約 1 時間で 4 問全てを解いた。余った 1 時間で、torisasami に印刷してきてもらったライブラリの写経をした。セグ木、遅延セグ木、modint、NTT、HLD を書くことができたのでいいタイピング練習になった。

リハーサルが終わった後はチーム紹介が始まった。事前に準備していたチームとそうでないチームで二分化されている印象があったが、私は少し用意していたことを喋った。海外チームの方にも DELIAIR の意味が伝わっていれば幸いである。海外チームは台湾が多く、韓国やベトナムのチームがいないのが意外だった。

解散後

1 日目のプログラムが終わった後はまずホテルへと向かった。ホテルは torisasami が 9 月に airbnb で予約した"ルームイン上海"というところで、家を宿泊施設として貸しているようなところだった。怪しい名前だったので不安だったが、ひとまず無事に泊まれそうなところだったので安心した。

ホテルに荷物を置いた後は中華街に繰り出した。食べ放題に行きたかったが、1000 円台の店は怪しい所ばかりだったので結局昨年行ったのと同じ店に行った。店では研究や研究室の話になり、純粋だった DELIAIR も人生のステップを上がっているんだなという感慨に浸った。

食事を終えてホテルに戻ると、今度はホテルに備え付けのタオルと着替えを持って銭湯に向かった。湯加減の良いジャグジーで torisasami から聞いた AOJ ICPC の問題を考えたり、明日の作戦について話し合ったりした。

銭湯を上がった後はコンビニでヤクルト1000 (torisasami 推し) と明日の朝食のパンとおにぎりを買ってホテルに戻った。その後はなぜか torisasami の高校同期と通話することになり、一時間程通話した後 23:30 頃に就寝した。しかし、下の階に泊まっている人たちの出入りの音がうるさく、1 時間以上は寝付けなかった。睡眠も数時間に一回起きてしまうようなものであったが、布団が柔らかかったので体は十分休めることができた。

大会 2 日目 (11/26 日)

ICPC の朝は早い。朝 7 時半に起床し、食事をしてから会場へ向かう。外は雨が降っており、rainy って rniya の並び替えだなとか意味の分からないことを言っている間に会場に到着した。

部屋に入るやいなやトイレに行きたくなった。行ってみると ICPC 参加者で長蛇の列が形成されており、ホテルで用を足さなかったことを後悔した。本当はやってはいけなかったかもしれないが、2 階のトイレを貸していただいて事なきを得た。

そんなこんなで、持ち込んだノートを復習してたりしたらあっという間にコンテスト開始時刻になった。

コンテスト

前日の反省を生かしてサクッと CLion の環境構築を済ませ、テンプレートとシェルスクリプトを書いた。2 人には並行して問題の読解・考察を進めてもらった。

A 問題の内容は YOKOHAMA の作り方の数え上げだということを sapphire15 から聞き、dp を書いた (0:20 AC)。

続く B 問題は、長さ 2C 以下の遷移だけ見ればいいという考察を torisasami から聞き、累積和と dp を書くと通った (0:30 AC)。

次に F 問題の内容を sapphire15 から聞いたが、これは $\mathbb{F}_2$ 上の rank 1 行列なのでいつものという感じである (0:44 AC)。

D 問題は、sapphire15 は初見で「構文解析だ！」と声を上げていたが、違ったようである。torisasami が解法を詰めていて、区間 DP で解けるという。それはそうなので、実装してみるとまさかの WA。落ちる原因がわからず、コードを印刷して torisasami にも確認してもらうが、間違っているところはない。問題を確認すると、BNF に 1 という文字が入っていないのに異変を感じ、2 桁以上の数字は使えないことに気づいて AC (1:04 AC)。ここでの 3 人全員の足止めは痛恨となった。

残りで解けている問題は K だけらしいのでそちらに向かう。話を聞くと、円の内点を見つけることさえできればあとはできそうだったので、丁寧に実装をした。ジャッジ側で用意されているインタラクティブツールがとても便利で助かった (1:31 AC)。

G,E,C で 3 問数え上げがあると聞いたので、modint ライブラリを書いた。こういう場面でソラ書き出来るというのは心強い。E も G も解けそうだが、E はまだ微妙に詰め切れていないようなので先に G をやることに。sapphire15 がメモ化再帰で全部やればいいので、実際そうだなと思って書いてみると通る (1:56 AC)。

E 問題も解けそうということなので内容を聞く。基本的には bit DP で、 $a_i,c_i$ が両方含まれているあるいは両方含まれていない場合に $b_i$ を入れてはいけないという条件になるということを torisasami から聞く。私はその時点で $O(2^n\cdot n)$ に落とす方法が見えたので、書いてみると通る (2:10 AC)。

ここまでで既に 11 問中の 7 問を正解していて昨年の 5 問を優に超えているわけだが、順位は 7-10 位程度で解いても解いても一向に上がらない。このような早解きコンテストでは、序盤の遅れがどんどん積み重なってくるのが非常に辛い。

H 問題は torisasami が見えていて、燃やす埋めるになりそうというので、とりあえず最大流を写経して確認してもらう。考察の話を聞くと、実際に燃やす埋めるの形に帰着で来ているので書いてみる。サンプルの出力が答えの約 2 倍になるのでおかしいなと数分考えてしまったが、ペアを重複カウント & 同じもの同士のペアもカウントしてしまっていた。修正するとサンプルが合ったので、提出 (2:58 AC)。

残りはもう 3 問しかなく、順位表的に解かれているのは I と J。J は貪欲で良さそうと 2 人が言う。もしこの貪欲が正しければ HLD + 遅延セグ木で解けるので、とりあえずそれを書いてみることにした。この 2 つの写経は AOJ ICPC の Do use segment tree と全く同じ状況なので、その問題のタイムアタックをしていた甲斐があったなと思ってなんだか嬉しかった。実装は 30 分くらいでできたが、提出すると WA が出る。冷静にコードを見返すと、遅延セグ木で頂点 $i$ に該当する情報をそのまま $i$ 番目の点に入れてしまっていたのに気づき、修正して提出するとまたも WA が出る。この辺りで、貪欲も良く考えたら嘘くさくないかと思うようになり、反例を考えるもそちらもなかなか作れないという歯痒い状況に陥ってしまった。

J は貪欲が嘘だと沼なので、より解かれている I に一旦向かうことにした。torisasami は濃度でソートして貪欲でできないかということを考えていたが、私は見た目が LP なのでそちらの線で考えてみることにした。sapphire15 が双対を取ったらどうか？と言ってきたので、丁寧に行列表現に書き下して双対を取ってみる。その間に sapphire15 が J の貪欲の証明ができたと言うので改めてコードを見返してみると、遅延セグ木の初期化の部分を修正していたつもりがまだ間違っていたのに気づいて蒼ざめた。再修正して提出すると今度は AC (4:19 AC)。このミスはあまりにも初歩的すぎて本当に申し訳なかった。

残った時間で I を考えていたが、双対 LP をこねくり回しても釈然としない。torisasami は最後の希望にかけて自明な必要条件を書く。ラスト 2 分でサンプルがあって提出するも、さすがにそれで通るほど ICPC は甘くない。ここでタイムアップとなった。

Yes / No

今年は全体的な難易度が低めだったせいか、順位が全然確定せず、全チーム Yes で 2 周目に入るという状況が何度か起きていたのが面白かった。前半の企業賞は台湾チームのラッシュだったのも凄い巡り合わせだなと思った。

9 チームが 9 完以上ということで、Yes / No でも順位は 1 つしか上がらず、最終順位は 8 位だった。しかし幸運にも OptTech 社から企業賞をもらうことができたのは非常に嬉しかった。

Speed Star は Yes / No の結果がどうであれ優勝が確定していたが、最後の C 問題も通して唯一の全完を決めていて流石の一言だった。World Finals でも存分に暴れてきてほしい。

コンテストを振り返って

昨年の ICPC を見るに 7 完・8 完の勝負になると思っていたが、実際は 9 完・10 完の勝負というのは全く想像もしていなかった。D・J 両問でのロスは非常に悔やまれるが、それがなければ I や C が解けたかというとそうではないとも思う。

もちろん悔しい気持ちで一杯ではあるが、DELIAIR として全力を出し切ったつもりではあるし、何より周りのチームがとても強かったので、この結果を素直に受け入れるしかないと思う。最後にやらかすのがなんとも DELIAIR らしい。

懇親会

昨年とは違い食事付きの懇親会だった。

インターンでお世話になった某社には挨拶しに行こうと思ったので、まずそちらに行った。人事の方や社員の m さんとコンテストの結果について少し話した後、会社の宣伝を頼まれてクリアファイルと会社説明をいくつかもらった。

その後は食事を始めた。食事はあり得ないくらい大量にあったが、麺やポテトなどの炭水化物が特に多かった印象がある。気になっている企業のブースを見に行ったり、インターン先で知り合った競技プログラマーたちと話したりしているうちに、スポンサー賞の OptTech の方から声をかけて頂いた。話があるから後で企業ブースに来いということである。

取った分の食事をいったん済ませてから、チームメイトを揃えて OptTech 社のブースに行った。広告代理店ということで、機械学習を用いて最適な広告を選ぶという事業を行っているという話だった。気になった点を少し質問した後、記念撮影をしていただいた。

ICPC2023 アジア地区横浜大会に出場された選手の皆さんお疲れさまでした。また、当社の企業賞を獲得された東京大学のDELIAIRの皆さん、おめでとうございます！ #icpc pic.twitter.com/0LunHjJX3x
— オプトテクノロジーズ/Opt Technologies (@OptTechnologies) 2023年11月26日

企業ブースを離れた後は、近くにいた早稲田勢の方に足が吸引されてしまった。早稲田は 2 チーム 4 人（コーチ含）の 8 人とかっつさんの合計 9 人がいたので「早稲田も人が多いですね」と言ったところ、層が厚い世代が抜けてだいぶ人が減っているという話を聞いた。suta さん、ikefumy さん、siro53 さんのお三方は初対面だったが、tokusakurai ですと名乗ると、全員に知ってますと言ってもらえて嬉しかった。色々なお話をさせてもらったが、「ikefumy さんが、学業崩壊して機航に放り込まれた hotman さんとかっつさんを反面教師にした」という話と「Hyado さんが英語の授業で誰も PC を使ってないのに一人だけ最前列でパソカタをしていたり、床に座り込んで競プロをしてた」という話が特に印象に残っている。卒業してもネタが尽きないさすがの sociability だ。かっつさんの仕事の話も色々聞いたが、ここに書くのは控えておく。

食事 3 周目を取った後は、某社の企業ブースに行って r さんから仕事の話を聞いた。ヒューリスティック的な問題の中でも離散最適化を交えたアプローチをされているということを聞いて面白そうだなと思った。昨年に続いてタンブラーを頂いた。

近くに東大チームが集まっていたのでそちらに顔を出した。nok0 さん (26 位) が ALGO ARTIS ARC の懇親会の話をしていて、私 (41 位) も行きます的なことを言ったところ、torisasami (23 位) がそんなメール来てないと言う。登録情報を確認していると、なんとメールアドレスを登録していないことが発覚し、DELIAIR はこういうところがダメだと改めて思わされた。

最後はまた早稲田勢のところに混ぜてもらって話をしていたが、あっという間に終了時刻になった。B1 のお二人も元気そうで良かった。今後の ICPC での活躍に期待。食事は予想通り半分以上余っている感じだったので、予算を割く場所を間違えてないかと思ったりもした。

解散後

ICPC 横浜大会の全てのプログラムが終わった。解散後は真っ直ぐ帰る気になれなかったので SPJ の 3 人と tabr, torisasami の計 6 人で中華街方面のカフェへと歩を運んだ。Kite_kuma くんは我々と The Raspberry Candies が引退することに萎えていたので、SPJ も一緒に引退することを勧めた。Kite_kuma くんが D 進したりしなかったりするらしいが、それはさておき 3 人とも社会には全然興味がなさそうで面白かった。自分も一年前はそんな感じだったかもしれない。

人と話している間は疲れを感じることはなかったが、電車で皆と別れた後はどっと疲れが湧き出て危うく乗り過ごしそうになった。

ICPC 引退

年齢制限のため ICPC はこれで最後となりました。

もっと練習しておけば良かったという気持ちもありますが、最後が他チームと比べて相対的に苦手なセットだったのでツキがなかったかなと思います。

同大学から最大 3 チームという制限によって Asia playoff に参加できないということになっていたら相当悔しかったはずですが、Speed Star が見てて気持ちが良くなるほどの圧勝劇を繰り広げてくれたためすっきり引退することができました。

チームを組んでくれた 2 人には本当に感謝しています。torisasami はいつもしょうもない話で楽しませてくれて、sapphire15 は深い知見や考察で幾度となくチームを助けてくれました。気の置けないチームメイトと 2 年半やれて本当に楽しかったんだな、と全てが終わった今になって初めて気付かされました。かなり緩いチームだったので、革命を起こすためにはもっと厳しくやる必要があったかな。

同じ大学で歳の近いライバルチームである SPJ・The Raspberry Candies の存在も、私たちの ICPC 人生を彩ってくれました。彼らの存在がなければこれほど ICPC に熱くなることはなかったと思います。大体同時期に競プロを始めて ICPC に参加し、国内予選での同校制限の壁を乗り越えて、こうして二年連続で一緒に地区予選に出ている仲間 (敵) が何人もいたのは本当に恵まれていたと思います。一緒に引退しましょう。

ICPC に選手として参加することはもうありませんが、来年以降もコーチ・スタッフ・スポンサーなど何らかの形で大会に関わっていけたらと思います。

トークサクライ

ICPC 2023 アジア地区予選横浜大会 (2023/11/25-26)