ICPC地区予選総集編
夢が始まった場所。
2012年
すべては2012年の地区予選から始まった。僕がこの大会に出ることになったのも、かなり偶然だった。
競技プログラミングを始めたのは高校時代。先生がクラスへ勧誘に来て、国際大会に出たすごい選手が数万ドルの全額奨学金をもらい、プリンストン大学に合格した、という話をしていた。当時の省大会の参加費は30元ほど。先生はこれを一言でまとめた。「30元払って、30万元稼ごう」。
それで始めて、すっかりハマり、全国大会で銀メダルを取り、上海交通大学への推薦入学も決まった。
上海交通大学に来る学生がどれほど強いかは分かっていた。僕よりはるかに上の人ばかりだ。その中でもICPCチームは世界一を何度も取った超強豪。大学では競技を続けるつもりなどなかった。どう考えても無理だと思っていた。
転機は2012年、アメリカへ来たときだった。上海交通大学で2年、ミシガン大学で2年学び、両方の学位を取る2+2プログラムで、僕は3年生からアメリカへ移った。ミシガン大学は2011年世界大会で学校史上最高の2位、金メダルを取ったばかりで、その実績が計算機科学科の建物に大きく掲示されていた。
僕は見ただけで気に留めなかったが、ルームメイトはそこに勝機を見つけた。上海交通大学は強い。でもミシガン大学はそうでもないのでは？ 調べると、2011年世界大会の強さは二人の化け物級選手に支えられていた。一人は引退後に僕たちの学生コーチとなり、もう一人は中国IOI代表経験のある一学期だけの交換留学生だった。二人ともその後は世界大会に出る資格がなく、抜けた途端にチームは崩れ、2012年は世界大会にも進めなかった。
ルームメイトは2011年地区予選の問題と順位表を読み、結論を出した。「これなら俺でもいける」。
三人一組の大会なので、彼は僕を誘った。そして一言で僕を落とした。「もう一度、夢を追ってみたくない？」
2011年の問題を出し、「これ簡単、次も簡単」と六問続けて見せた。全部サービス問題に見えた。そして言った。「ほら、これで世界大会に行けるじゃん」。
僕は参加することにした。
この年のチーム選抜は二転三転し、最後には完全に折れた。
校内選抜前、僕たちはコーチにチーム編成を聞いた。二人で組みたいが、先に固定できないか。公平のため無理で、順位どおり上位三人、その次の三人で組むという。これは点数調整が必要なのでは？
もっとも、練習ではずっと僕たちが1位と2位だったので、調整する意味もなさそうだった。
ところが本番で崩れた。ルームメイトはそれまで好調すぎて油断し、難問に時間を使いすぎ、簡単な問題を大量に残した。しかも選抜は週末の二日間から好きな日を選ぶ方式だった。僕たちは初日に出て、彼は失敗しても2位だったので大丈夫そうに見えた。ところが二日目、練習に一度も来なかった未知の強敵が二人現れ、あっさり彼を抜いた。
計画は爆発した。僕はその二人の中国人留学生と組むことになる。僕は別に構わないが、ルームメイトにはつらい。友達のオーディションに付き添ったら、友達だけ受かった、というよくある話そのものだった。
結果は僕が7問で1位、二人が6問、ルームメイトが4問。差が大きすぎて、誰かが自分から辞退しない限り覆せない。
結局、誰も辞退しなかった。僕は二人と組んだ。以後、一人を問題読み担当、もう一人を「おまけ担当」と呼ぶ。前者はその後二年間、世界大会で問題を読む役になるが、この時点ではまだ普通に実装もしていた。
おまけ担当は高校時代かなり有名で、2008年中国情報オリンピック優勝者の曹欽翔と並び称されたこともあるらしい。それほどなら、どれだけ強いのかと思う。
そして彼は、とんでもない規模で僕たちを困らせた。
地区予選前、今年はワイルドカードが一枠来ると聞いた。僕たちは通常三校が進出し、今年は四校になると思っていた。上位はカーネギーメロン、ウォータールー、トロントの三校。前二校は世界大会のメダル圏付近に何度も入り、トロントにもその年は元IOI代表がいたと聞いた。
この三校は地域だけでなく北米全体でもトップ級で、ウォータールーとCMUは世界大会で北米首位をよく取っていた。後にMITへ中国出身の強豪が多数入って、北米の勢力図は大きく変わった。
当時の世界大会全体を見ると、北米は比較的弱く、アフリカ、アラブ、南米よりは強いが、欧州やアジアとは平均レベルに大きな差があった。つまり僕たちは、弱い地域の中の最強地区にいた。
でもワイルドカードがあるなら問題ない。三強を除けば次は僕たちで、残りの学校はその年ほとんど競争にならなかった。
気楽に構え、唯一の目標は4位を守ること。大学の練習に少し参加しただけで、追加練習はしなかった。二人とはまだあまり親しくなかった。
本番は全九問で、最初の八問は明らかに簡単だった。ただし多少の実装量はある。世界大会基準ならゼロ同然だが、当時の僕たちの実装力も普通で、簡単な問題にかなり時間がかかった。CMUは1時間半で六問、3時間ほどで八問を解き、スコアボード凍結前に全完した。
僕と問題読み担当は4時間以上かけ、どうにか六問を実装して通した。その間、おまけ担当は最後、つまり最難関の問題から読んだ。普通は難易度順ではないが、たまたま最後が最難関で、彼はたまたま後ろから読んでいた。
幾何の問題だった。少しでも経験があれば、地区予選のこの種の幾何は、最強チームの早すぎる全完を防ぐための難問だと分かったはずだ。ところが彼は自信満々で「いける、難しくない」と実装を始めた。序盤に60行ほどを書き終え、最後までデバッグできなかった。当然だ。公式解法は場合分けだけで200行以上。60行で通そうというのは無理がある。
序盤のPC時間を大量に使った。中盤で幾何を諦め、七問目へ。普通の為替換算と最短路だったと記憶している。罠は浮動小数点だと誤差で落ち、64ビット整数で分数を管理する必要があること。彼は浮動小数点を使い、また失敗した。
一時間後、問題読み担当が分数で書き直したが、やはり通らない。結局どちらも解けなかった。後で見ると、配列一つの初期化漏れだった。最初に0を入れれば通った。
僕が一度も読まなかった八問目は簡単な最大流だった。見ていれば解けた。でも現場では読む機会すらなく、PC時間は残り二問のデバッグに消えた。
最終成績は六問。CMUは全完し、ウォータールーとトロントも3時間前後で八問まで進んだが、全完には届かなかった。
反省会で、おまけ担当は自分が実質何もしていないことに気づいた。二問書いて両方失敗、得点への貢献ゼロ、PC時間だけ大量消費。
ルームメイトは二軍で、さらにひどい経験をした。アメリカ人のチームメイトの名前を中国語音写すると、あまり賢そうに聞こえなかった。大会前は気にしていなかったが、試合後ルームメイトが激怒し、それ以来「まさに名は体を表す人」と呼ぶようになった。
どうせ参加賞状態のチームだと分かっていたので、ルームメイトも本気ではなく、多くの時間をその人になんとかコードを書かせることに使った。アルゴリズムは何を説明しても伝わらず、コードは何を書いても動かない。見ているだけでつらかったらしい。
僕たちは全体8位。上にはCMU四チーム、ウォータールー二チーム、トロント一チーム。この並びを見ると、進出しても少し気まずかったかもしれない。
一か月待った末、進出できないと分かった。実は通常枠は二つで、三つ目がすでにワイルドカードだった。強い地区なので毎年そこまでは来るが、四つ目はない。
災いの中に福もある。進出しなくてよかったのかもしれない。行っても完全に参加するだけになっていただろう。おまけ担当はそのシーズンを最後に出場資格がなくなった。僕、問題読み担当、そしてルームメイト改め数学担当の三人は、ちゃんと練習し、世界大会を単なる旅行にしないと決めた。
まずい。旅行したかっただけなのに、どうして急に夢まで持ってしまったのか。
当時の僕は、世界大会との縁がこの先どれほど続くか知る由もなかった。
シーズン後半の2013年初め、三人と大学の仲間で多くの練習をした。CMUと僕たちの学生コーチは友人で、ともにUSACO委員だったため、CMUの合宿にもよく参加し、アメリカIOI代表に混じってボコボコにされた。三人で公式戦にはまだ出ていなかったが、非公式戦はかなり経験した。ただ、非公式だと役割分担が適当で、書きたい人が書く。当時はまだ問題読み担当と数学担当の区別もなかった。
十年以上前のメールを掘り返し、副コーチが送った太古の写真を一枚見つけた。
2013年
2013年。また点数調整を考える時期が来た。半年以上、真面目ではあるが死ぬほどではない練習を続け、基礎力は前年よりはるかに上がっていた。
今年は伏兵がいるのか。分からない。実際にはいなかったし、大学の状況を考えればいないはずだった。三人とも中国の省大会一等賞レベル。大学からプログラミングを始めた学生に負ける理由はない。
校内選抜は無事に上位三人。実装が非常に速い新人がいて、七問中三問を二人より速く書いた。ただ、速いだけで最終的には四問。僕たちは全員五問以上だった。
地区予選で僕たちの目標は進出、コーチの目標はウォータールー撃破。ミシガン大学は世界大会でウォータールーを上回り銀メダルを取ったことがあるのに、地区予選では一度も勝っていなかった。強豪だからこそ、コーチはずっと目標にしていた。
実装の分担は相変わらずほぼランダム。問題読み担当も二問以上を書き、ひどいバグを自力で見つけてシミュレーション問題を通した。数学担当は最後のIという簡単な問題で、途中の値が18桁を超えて多倍長整数が必要か悩み続けた。同じ大学の別チームが通したのを見て、不要だと確信した。彼らの実力は知っている。多倍長整数など絶対に書けない。そこで交代し、一瞬で通した。
幾何のGは見た瞬間に捨てた。何だこれ、人間が解く問題か？ 結果的に大正解で、リファレンス実装は300行近い。後にCodeforcesへ公開され世界中の強豪が挑戦したが、十年たっても五時間以内に通した人はいない。
最大の波乱は最大流のE。モデル化だけでも難しく、問題読み担当と僕が解法を思いついたときはかなり興奮した。実装して提出、TLE。最初の線形探索を二分探索に変えて提出、またTLE。
しかもかなり遅そうで、提出から結果まで毎回五分かかった。
もう手がなかった。線形探索なら毎回グラフを作り直さず、元のグラフで増加路を一本ずつ探せるとは理論上知っていた。でも書けない。たぶんそれが正解だった。
残り12分、適当な最適化と定数倍改善を入れ、ひたすら提出した。判定が遅く、全部キューに詰まった。
終了約五分前、七分前に出した提出が通った。その後にも何本出したか分からない。AC表示を見た瞬間、三人で叫び、会場中に聞こえたと思う。誰かが拍手し、さらに人が加わり、会場の選手たちから大きな拍手をもらった。
とても温かい会場だった。スコアボード凍結後のACは表示されないので、みんな何が起きたかすら知らなかったのに。
僕たちは7問、首位と同じ題数の2位で進出。そしてウォータールーを倒しただけでなく4位へ押し出し、世界大会進出まで阻止した。後で分かったが、最後の問題が通らなくても進出でき、学校順位も2位のままだった。学校順位とは各校の最高成績チームだけを比べた順位だ。実はかなり安泰だった。
その年の練習も前年とほぼ同じ。時間が合えばチーム練習、合わなければ各自練習。問題読み担当と僕は大学院のアルゴリズムを履修した。大半の学生には大学院で最難関級の授業で、後に僕が博士課程で五年間TAをして、その難しさをさらに理解した。
ところが当時の二人はこれを楽な授業として取った。教室の後ろで世界大会の問題を話し、授業はほぼ聞かず、二人ともA+だった。
このシーズンは北米招待大会NAIPCにも出た。前年のシカゴ大学招待大会が改称したもので、北米の世界大会進出チームを招く非公式戦。当時は進出と無関係だったが、北米制度の再編後、徐々にNACへ発展し、正式な選抜体系に入った。
当時のNAIPCは豪華だった。会場はホグワーツのような大図書館の閲覧室。現地開催の体験もよく、賞金も世界大会級を目指し、優勝1万2000ドル、2位6000ドル、銀賞3000ドルだった。
僕たちは4位で銀賞、3000ドルを獲得。競技人生で最初で最後の賞金だった。いい時期に当たった。その後賞金は急落し、数年後には金賞が250ドルのAmazonギフトカードになった。初年度に今後十年分の予算を使ったのか。
全21チームで、僕たちの地区の進出三校は3、4、6位。北米では本当に強い地区だった。
大会内容はほとんど覚えていない。3時間ほどで最後の一問を通した後、何も分からず残り二時間を過ごした記憶だけだ。
世界大会前、僕は卒業のため上海交通大学へ戻り、二人はアメリカに残った。それで終わり。まともな練習はしなかった。
2014年
新シーズン。前年の世界大会の反省から、今度こそしっかり練習する。さすがに緩すぎた。
いや、どうして年々本気になっているのか。
人間の欲には限りがない。一度手に入れると、もっと欲しくなる。最初は世界大会へ旅行したかっただけなのに、今度はメダルを狙い始めた。
選抜には新事情があった。僕は大学を卒業し博士課程へ。同学年の上海交通大学出身者も大勢ミシガン大学の大学院へ来て、強い選手も多かった。さらに数学担当が、国立台湾大学から来た大学院生が世界大会金メダル経験者でCodeforces赤、つまりトップ級だと調べた。僕たちは「赤レートの化け物」と呼んだ。
彼が出たら、三人のうち一人は確実に落ちる。
幸い説明会で会い、もう出場資格がないと分かった。ほっとした。
上海交通大学から来た他の強者も出ず、三人でまた上位を独占して組めた。
地区予選は波乱だらけだったが、結果に疑いはなかった。前年に大きな「ウォータールー」を喫し、長年の世界大会連続出場記録を僕たちに止められたらしいウォータールー大学は、雪辱を誓って戻り、8問で優勝。次の二校が7問、その次は5問。上位三校が断然強かった。
問題は不気味な難しさだった。前年世界大会の超難問路線を真似たのか、開始20分間は誰も通さず静まり返った。地区予選どころか世界大会でも異常だ。ウォータールーの初ACが42分、2位と僕たちは一時間後。中難度から始まり、簡単な問題がない。22位以下は一問、42位以下はゼロ。普通の参加者には最悪の体験だったと思う。
当時印象に残った問題はない。後で見直すと最後の幾何Iが非常に良く、計算幾何で前処理し、最大流で解く本物の世界大会級だった。もちろん現場では即捨てた。ウォータールーは凍結後に通し、優勝にふさわしかった。
僕たちは3位で少し不安になった。保証枠は二つで、3位はワイルドカード頼み。でもこの結果なら、さすがに僕たちの地区へ来るだろう。
無事にワイルドカードを得て進出した。
NAIPCにも出て6位、銀賞。ただし賞品は前年と比べものにならず、一人150ドルのAmazonギフトカード。この大会、一年で破産したのか。
この年は大量に練習した。世界大会でいい成績を取りたい。
2016年
前年は関わらなかった。学生コーチがまだいて、僕の出番がなかったからだ。ところが博士5年目の彼は、学位をやめて起業すると決めた。
僕は本当に驚いた。中国人的な感覚では理解しにくい。5年目で卒業間近なのに、なぜやめるのか。つらくても少し耐えれば卒業できるし、埋没費用が大きすぎる。
でもアメリカ人はもっと自由だ。やりたいから起業した。
大学には空白が残った。教授のコーチと副コーチは普段、学生の練習をほぼ管理せず、学生コーチが担当していた。彼が去り、僕が入った。まさに緊急登板だった。
まず選手探しから苦労した。前年は僕たち三人が引退し、地区予選は悲惨。二軍が最高で12位、次が三軍、四軍、一軍は30位以下。順位どおりに組む校内選抜でも、大事故は起こるらしい。
人材がいないので自分で探した。夏に入門アルゴリズム授業のTAをしていたので、成績上位者全員へ参加を勧めた。進出できるほど強くは見えなかったが、いないよりましだ。
学期開始後、練習会を作り、上位者へ順に連絡し、上海交通大学の後輩から競技経験者も発掘した。必死に説得して参加させた。
最終的に中国の省大会一等賞経験者を三人見つけた。進出を狙えるはずだった。
現実は容赦ない。実装力不足で本戦進出を逃した以前に、校内選抜で三人一緒にすらなれなかった。
練習では常に上位三人で安心していたが、本番で大事件が起きた。
本当の兄弟である二人のアメリカ人を、兄と弟と呼ぶ。二人が1位と3位へ入った。2012年の伏兵と違い練習にはずっと来ていたが、ここまで上位は初めて。本番で覚醒したらしい。
僕の三人は2、4、5位。どう組むのか。本人たちは三人でいたい。特に一人は英会話が非常に苦手で、外国人と組めば双方つらい。
教授コーチは上位三人を主張し、僕は本人の希望も聞こうと主張。何度も揉め、最後は兄弟が同意すればよいとなった。
兄弟は同意した。本人たちもこだわりはなかったのだろう。上位に来ただけで予想外で、世界大会進出など考えていなかったはずだ。
1、3、6位が一軍、2、4、5位が二軍となった。
ここで6位の重要人物が登場する。僕は彼を「香港記者」と呼ぶ。中国人で香港の大学に通い、一学期だけ交換留学に来ていた。本物の記者ではなく、競技界の噂なら何でも知っている情報通だからだ。どこへ行っても西側の記者より先に着く、という昔の有名な冗談そのものだった。
選抜後、練習法と必須アルゴリズムを聞かれた。大学でプログラミングを始め、競プロはその学期からで基礎は薄い。でも速成法はあった。長年この地区へ出て、問題傾向は分かっている。ほぼ毎年最大流が出て、年々簡単になっていた。校内選抜にも最大流を二問入れ、解ける人を探していた。
他は無視して最大流だけ勉強しろ、と言った。
これが大当たりだった。兄弟は最大流を全く知らない。香港記者が本番でその問題を解いたから題数が足り、最後10分の逆転で2位進出できた。なければ10位以下だっただろう。
ただ当時、僕は二軍へより多く時間を使った。個人的に呼びやすく、呼べば来る。一軍は公式練習くらいしか来なかった。
三人の実装力には驚かされた。TAのオフィスアワーに誰も来ず、基礎練習へ呼んだ。単純な単一始点最短路。それを省大会一等賞三人が90分たっても書けない。僕は心が折れた。自分も初年度はこの程度だったのか？
練習でも簡単な問題を通せず、本番でも実装力不足で落とし、一軍に完敗した。
一方、兄の実装力は非常に高く速い。香港記者によると、速いだけでなく構造も厳密で、OOPを守り、ばらばらの関数やグローバル変数でなくクラスを作る。コード量が増えて速度を落とすため競技では珍しいが、バグ時には圧倒的に探しやすい。
一軍は無事進出し、僕は大喜び。また世界大会旅行だ。開催地がアメリカだと知り、今度はがっかりした。
香港記者は次学期に帰国し、チーム練習はほぼなし。オンライン練習もしたらしいが、効果はお察しだ。上海交通大学時代の僕たちも「練習した」とは言っていた。
他は残っていた。アルゴリズムの基礎が弱い、というよりほぼないので、補講を始めた。
完全なボランティアで、主な目的は兄弟に基本アルゴリズムを叩き込むこと。世界大会へ行くのに、定番を何も知らないのはまずい。
ここで別のアメリカ人が目に入った。彼には「アメリカ2号」という呼び名をつけることにする。校内7位で三軍の先頭だったが、当然、結果には満足していなかった。
兄弟の出席率は6割ほどだが、アメリカ2号は毎回来た。時間がなく内容が多いので授業は非常に速く、三、四週後にはほぼ誰も来なくなった。一度、彼だけを相手に一コマ全部講義した。
一学期で、自分の知識を全部渡した気がする。どれだけ身についたかは分からない。
2017年
また新しいシーズン。
前年同様、人を集めて回った。ただ、アメリカ2号が多くのアルゴリズムを学び、兄の実装速度もさらに上がったらしいので、今年は少し自信があった。
説明会で北京大学卒の大学院生二人に会った。前年の三人と違い、二人とも北京大学ICPCチーム経験者。一軍ではなくても二、三、四軍にはいた。競技経験だけでなく正統なICPC経験があり、実装速度も保証されるはず。僕は興奮した。上海交通大学四軍にも入れなさそうな僕から見れば、北京大学二軍なら地区予選くらい余裕で、面倒を見る必要もない。
実際、何もしなかった。
ところが校内選抜で二人とも崩れた。大会自体は非常によく作れたと思う。全問題に二人以上の正解者がいて、全12問を解いた人はいない。優勝9問。理想的な結果だった。
唯一の後悔は数学問題。導出が巧妙なので入れたが、実際は結論を知っていれば瞬殺、知らなければ手がかりゼロで、現場で導いた人はいなかった。これはよくなかった。
問題数と差が十分で、最後まで大逆転が続いた。元数学担当をオンライン観戦に誘い、最後30分を見た。残り15分、アメリカ2号が堅いアルゴリズム力で9問の首位。残り4分、兄が例の数学問題を思いつき8問で2位。それまでは「あの数学問題のせいで兄が一軍を逃したら残念」と話していたが、自力で逆転した。
上位三人は兄、アメリカ2号、そして初めて見るアメリカ3号。北京大学の二人は4、5位。主にペナルティが高く、僕の数学問題にもやられたらしい。アメリカ人は知っていたが、二人は知らなかった。あの問題がなければ二人とも一軍だったかもしれない。
この編成には満足した。一軍は兄とアメリカ2号がいれば地区予選の実力は十分で、新人の実力は大して重要でない。二軍も北京大学の二人がいれば、冗談抜きで三人目が誰でもよさそうだった。上位五人は断然強く、5位が8問、6位は5問だった。
本戦で一軍は期待に応えた。兄が強すぎた。問題は他の人が読んだが、コードは全部彼。一人で1時間14分に六問を書いて通し首位へ。その後失速しても二問追加し、地区の学校順位2位で世界大会進出。
二軍も同じ題数でペナルティが高いだけ。一軍がいなければ学校順位3位で、おそらく進出できた。
今年はそれで終わり。北京大学の二人は来年も出ると言い、次はもう安泰だと思った。
世界大会が中国開催だと知ってまた無言になった。無料の海外旅行を全くさせてくれない。大学のお金で帰国すると思うことにした。
2018年
また新シーズン。
北京大学の二人は続けて参加した。そもそもまだ出られるのか、真剣に議論した。一般には大学入学から五年以上だと出られないと思われていたが、当時ルールを読み直した僕たちは、入学年条件と生年月日条件は「または」で、どちらかを満たせば資格を得られると理解した。
アルゴリズム授業のTAを利用し、上海交通大学出身の博士課程の後輩も見つけた。競技経験はあるがICPC経験はない。問題ない。実装は北京大学の二人に任せ、彼は分析専任でいい。かなり説得して、また中国人三人のチームができた。開催地は早くからポルトガルと決まっていたので、四人のチャット名は「ポルトガル旅行団」。世界大会の結果はどうでもよく、地区予選を抜ければ旅行できる。
ところが校内選抜で大事故。北京大学の一人目、上海交通大学の一人、北京大学の二人目が8、5、4問で1、3、5位。5位を一軍へ入れるのは難しい。2位はアメリカ3号で6問。要するに1位だけ断然強く、残りはみんな補助役だった。
5位の彼は自業自得だった。開始一時間ほどから最難関に挑み、最後まで通せず、データが間違っているとまで疑った。後で解法を教えると自分の方法が違うと分かった。どうしてそんな試合運びをするのか。
北京大学の二人目はその場で諦め、一人目、上海交通大学の一人、アメリカ3号が一軍に。ポルトガル旅行団は正式に解散した。
この一軍も少し頑張れば世界大会へ行けたはずだが、地区予選でまた簡単な問題を実装できなかった。学校順位3位にはなったが、1位9問、2位8問、彼ら5問で、ワイルドカードは出なかった。
本当に自分たちとの戦いだった。どう転んでも3位なのだから、少しまともにできればワイルドカードを取れたかもしれない。
ポルトガル旅行団は完全に解散した。
僕のコーチ人生もここで終了。同じ地区予選会場へ六回通い、選手として二度進出、コーチとしてさらに二度進出させた。十分に輝いた時期だったと思う。
このときの僕はまだ知らない。僕と世界大会の関係に、まったく新しい章が始まろうとしていた。