ACM/ICPC 2006-2007 参加記

チーム kitsune- メンバー紹介

チーム結成からアジア予選前まで

文: 荒木

チーム結成まで

チームkitsune-のメンバーは、昨年度まではそれぞれ別のチームで参加していました。 しかし、年齢制限、研究に集中したいなどの理由で参加できないメンバーが出てきて、 チームを再編成することになりました。 いろいろな人に荒木が声をかけて回った結果、まず末松が同じチームになりました。 そして、荒木、末松の二人で、練習会(OBの人が開いてくれている、pku online judgeを利用した練習会)で 結構いい成績を残すことが出来ました。 その後、林崎が参加し、今のチームが出来ました。

模擬国内予選

ICPCのOB/OG会の人が開いてくれた模擬予選です。 末松が参加できず、荒木と林崎の二人での参加でした。 その上、この時点ではライブラリ(良く使うアルゴリズムを印刷して持ち込むことができる)の整備も出来ていなかったので、あまりいい結果を残せるとは思っていませんでした。

大会開始。 二人で問題を読みつつ、二人で実装しました。 この時点ではまだ、林崎一人に実装を任せるスタイルが確立していませんでした。

まずは4問を林崎が解きました。 その後林崎が実装の超大変な問題を解き(参加チーム中解けたのはうちのチームだけ)、 荒木が林崎の苦手とする幾何の問題を「アルゴリズムC++」を読みながら解いて、一位をとることが出来ました。 一位をとれたことで、チームの実力に自信を持つことができました。

国内予選

模擬国内予選と違って、もちろん3人での参加でした。 模擬国内予選の結果が良かったことに加え、ライブラリも整備していたので、きっとよい結果が残せると皆信じていました。

3人で問題を読み、簡単なA,B,D,Eを林崎に任せ、Cを荒木が、Fを末松が考えました。 A,B,D,Eが解けた後、末松がFにとりかかりました。 Fを近似計算で解こうとしたのですが、なかなかうまくいきません。 そうこうしている間に、同じ部屋で参加していたMakegumiがガッツポーズをしているのが見えました。 その間にCを林崎と一緒に考え、林崎がコードを書きますが、時間が足りずタイムアップ。結局4問Acceptedでした。

結果を見るとチームは国内3位、学内2位。 アジア予選に進出できることになりましたがちょっと残念でした。

後から分かったことですが、Fには難しい厳密解法があり、近似解法では解けないようです。 Fを解いたチームはいなかったので、Fに挑んだ時点で作戦負けだったとも言えます。 なお、国内予選が終わったころ、 今のチームの戦法(荒木、末松が問題読み&アルゴリズム考案をし、コードは全て林崎が書く)が出来上がりました。

夏合宿

ICPCのOB/OG会の人が開いてくれた合宿です。 オリンピックセンターに3日間泊り込みでコンテストをしたりライブラリの交換をしたりしました。

実戦形式の練習会が3回あり、1・2回目で1位をとることができました。 3回目は3位で、少し残念でしたが。

模擬アジア地区予選

ICPCのOB/OG会の人が開いてくれた模擬予選です。

荒木が十数時間の徹夜バイト明けで少し心配でしたが、1位をとることができました。

アジア大会から世界大会前まで

文: 末松

アジア大会

初日

お昼過ぎに三田駅に集合、慶応高校/大学の学園祭を抜けて会場へ。 初日に予定されていたのは開会式とJava Challenge、そしてウェルカムパーティでした。

開会式

開会式。
会場に入ると独特のざわめきがあり、いよいよだなという気分になります。
参加しているチームの多くが日本のチームということもあって夏合宿で顔を合わせたチームも多かったので、いろんなチームに挨拶したり、コンテストに関する雑談をしたりして時間を過ごしました。

この日だけは、私たちのチームのマスコットであるキツネさんも会場に入ることができました。

開会式では参加チームへのお祝いの言葉や細かいルールの説明、そして質問会がありました。そして、本番のシステムを使う練習セッション。

Java Challenge

開会式後はマシンの設定などを行い、その後さっそく「正解のない問題」を解くJava Challenge。 鮭をたくさんとる熊の動きを決定するのAIを作る問題で、二日目に後で熊同士を対戦させるとのことでした。

僕はその辺が苦手だったので、他の人が考えてるのと同じことをやるとせいぜい勝率は5割くらいだろうと思い、ネタアルゴリズムを考えて林崎に実装してもらうことに。元気のなかったコーダーだけど、実装が楽だったのでなんとか気力を振り絞って書いてもらいました。

アルゴリズムは、「敵チームの熊を追いかけて、追いかけてる途中に鮭がいたら取る」というもの。鮭に近づくアルゴリズムを実装するのが面倒だったので、「鮭を追いかけている(はず)の敵の熊」を追いかければいいのでは?という考えです。必然的に同じ場所にいることが多くなりそうですが、同じ場所にいるのであれば5割の確率で鮭を取ることができるはずです。 とりあえず1時間程度の時間で書き上げて、ウェルカムパーティ。自己紹介やらなんやらで、ご飯を食べながら交流する時間が設けられていました。

二日目

コンテスト本戦

午前9時、いよいよコンテスト開始。午後2時までという、お昼ご飯の時間が微妙な日程です。

問題は以下のURLにありますので、参照するともっとわかりやすいかもしれません。 http://www.acm-japan.org/icpc2006/jp/regional/problems.html

C問題はうちのコーダー林崎が得意なサイコロの問題だったので他の問題を読むまで彼にこの問題を丸投げ、しかしどこかで間違えて詰まる。

そうしている間に荒木がA問題を式を入力するだけの数値計算の問題に落としたので計算させるプログラムをちょこっと書いてもらってAccept。

D問題は手の空いたコーダーと話し、ダイナミック計画法で解けそうだという考えをVerifyしてもらってから実装してもらいました。

そんな流れで3問は比較的すぐに解けたのだけれど、その時点で優勝候補の上海交通大学が既に5問。厳しいものは感じましたが、1位が必須なわけでもなく、焦って解けるものでもないので、気持ちを問題に集中させました。
その後全ての問題を軽く問題を考え、得た雰囲気としては、

といった感じ。

G問題を普通に書いて解かせてみたところ問題のSample Inputに対して非常に長い時間がかかったので、問題の特徴を捉えたさまざまな最適化を荒木と林崎で試みました。 その途中で末松がH問題の比較的楽な実装方法を思い浮かんだので林崎に提案、実装、比較的スムーズにAccept。

その次は、C問題のデバッグを林崎に任せ、その間各自が解けそうな問題を選んで末松はFを、荒木はGを考えました。 Gは探索の打ち切り条件を考えたりいろいろ試みましたがなかなかうまくいきません。そうこうしている間にC問題のバグが取れたようでAccepted。これでようやく4問目。

その後しばらくかけてG問題は凸多角形しか解になりえないということを証明し、それを利用したプログラムに変更。 手元の計算機でSample Inputに対して実行したところ数分かかるという状態でしたが、とりあえず出してみたらなんとかなるかもということでSubmit、そしてAccept。5問目、この時点で3位に浮上。あとで聞いた話ですが、この問題の一番ひどい入力がSample Inputにあったということで、Sampleが終わればその他の問題は一瞬で終わるとのこと。コンテスト中にそこまで読みきるか…。

残る問題はB, E, F, I。 Eは問題サイズが小さいので頑張ればなんとかなるのかもとは思いましたが、計算量の見積もりが不可能なのでとりあえず後回し。 Iはアルゴリズムがさっぱり浮かばず、手をつけられない状況。 ということで、末松が引き続きFを考えつつB問題に荒木と林崎が取り組みました。

Bは解の条件を満たすような点が存在するかどうかを問う問題でしたが、同じ問題に遭遇したときに人間が通常考える方法である「解の条件を満たすような領域が存在するか」を考えようとして非常に面倒な幾何の問題を解く方針を選んでしまいました。 他の上位チームはだいたいB問題を解いていたので、このあたりでチームの誰か1人が思い浮かべば結果はもう少し違ったかもしれません。 結局領域を求めるプログラムを頑張って書くも最後までSample Inputがうまく通らず、B問題は間に合いませんでした。

F問題は条件を緩和した問題について考えて何らかのヒントにしようと試みましたがこれもうまくいかず。聞いた話によると画期的な手法はなくて頑張って探索するしかないとか…。そうなるとこの問題も計算量の見積もりができず、手が空いているときに試しに書いてみるというくらいしか解ける可能性はなかったのかもしれません。

B問題で悪戦苦闘している間に5時間のコンテスト時間が終わりに近づき、カウントダウン。 5! 4! 3! 2! 1! 0! 最後のほうでもう1問解ければ気分ももう少し違ったのかもしれませんが、開放感と煮え切らない感じが入り混じったような思いでコンテスト終了を迎えました。

Java Challenge 対戦会

コンテスト終了後は他のチームと雑談をしたり食事をしたりして空き時間を過ごし、そうこうしているうちに前日のJava Challengeで作成したプログラム同士を対戦させるイベントに。

前日考えたアルゴリズムは「何だこの変な動きをする熊は?」という雰囲気で始まって1回戦に勝ったときには半ば失笑(?)みたいな感じでしたが、回を重ねるにつき見ているみなさんも「熊を追いかけている」のに気づいたようで、2回戦、3回戦あたりでは大いに笑いを取ることができました。 時間の関係で障害物を避けるコードを書いていなかったために決勝戦ではその辺をきちんと処理したチームに負けてしまいましたが、決勝戦まで勝ちあがれた運に感謝したいと思います(笑)

表彰式

Java Challengeの後は表彰式。うちのチームは5問正解だったので、なんとか3位(日本では2位)に食い込むことができました。上海交通大学は強いと前から聞いていましたが、終わったときの正直な感想は「もっと勉強して、もっと準備して抜けをなくして、全てを1.2倍に高速化すれば勝てる…かも」というもので、世界の強さを見せ付けられた思いでした。

三日目

Excursion

この日はexcursionということで、全員でみなとみらいへ。現地で2時間くらい自由時間があったので、数チームと一緒に赤レンガ倉庫の方面へ遊びに行きました。

天気が晴れていれば海のほうの見晴らしも良かったと思うのですが、あいにくの曇り空。遠くは霞んでしまってちょっと残念。
その後バスに集合し、元町中華街で解散、中華街での昼食。お店の名前は忘れたけど結構おいしかったです。
お昼ごはんの後はぶらぶらしてからズーラシア(動物園)に。うちのチームマスコットにもなっているきつねさんに会ってきました。閉園間近の時間に到着したのでのんびり見ることができなかったのは残念だけど、人もそんなにいなくて楽しめました。滞在時間は1時間に満たないくらいかな…。今度はもっとゆっくりと行きたいところです。

大学代表決定戦(12/25)

Team Makegumiはマニラで開かれたアジア大会で2位、そしてTeam kitsune-は横浜で開かれたアジア大会で3位ながら、Makegumiには勝利。しかし「国際大学対抗プログラミングコンテスト」の名の通り、世界大会に出場できるのは大学から1チームだけ。 いったいどうなるのかなぁと思っていたら、12月23日に「ICPCの本部のほうではどちらとも決められないので、どっちが出るかを自分たちで決めてください。コイントスでも追加のコンテストでもいいです。結果は25日までに。」という連絡が届きました。ここまできてまさかジャンケンなんてことになるとお互いに納得がいくわけもなく、急遽ICPC OB/OG会の方々主催で追加のコンテストを開くことになりました。問題選定のためにイブを潰された関係者の方、ありがとうございました。

ということで早速、Team kitsune-も24日に大学に急遽集合して練習会を開くことに。クリスマスイブということで、ケーキの問題、星の問題、クリスマスツリーの問題など、クリスマスにちなんだ良問をいくつか選んで最後の準備としました。

そして25日。13時から15時まで、2時間で3問の問題を解くコンテストが開かれました。相手チームと同じ部屋で雰囲気までビシビシ伝わってくる環境。相手チームがアルゴリズムを考え付いたとか、問題を解いたとか、そういう情報も耳にしながらせっせとアルゴリズムを考案してコーダーに提案していき、1時間程度で2問正解。遅れること10分程度、Team Makegumiも2問正解。残る1問を1時間で先に解いたほうが世界大会!という圧力を感じつつ、また相手チームの進捗を空気で感じつつ、コードを書いては修正という時間でした。両チームともアルゴリズムは浮かぶも3問目は結果として解けず、勝負は解けた2問の時間差に。 本当に厳しい勝負でしたが運もあり、2問を解くのにかかった時間の合計はTeam kitsune-が132分、Team Makegumiが134分というごく僅差で勝つことができました。個人的に最後の数分は実装が間に合わないと感じていたこともあり、相手のチームが解いてしまわないことをひたすら願っていました。

コンテスト後は、大学にピザを出前してもらって軽く打ち上げ。僕は非常に消耗してて、食べる前と食べた後はずっと眠ってました。

熱い勝負の後でしたが相手チームの手前全力で喜ぶわけにもいかず。でもあの緊張の後の喜びは相当なものでした。

冬合宿

夜な夜なよその部屋に遊びに行って、問題を出来るだけ短いコードで解くパズルの話なんかをしていました。 ただ、模擬コンテストの予定が毎日あったので、遅くても1時半くらいにはだいたい解散。 合宿という意味では多少物足りない(?)かもしれなかったけれど、毎日7時ごろには起きていたのでそんなものかもしれません。

毎回合宿では流行語であったりネタ画像であったりそういうネタがたくさんで非常に盛り上がるのですが、今回も例外ではなく変な言葉が飛び交う変な合宿でした。気になる人は是非是非参加できるようがんばってくださいっ。

初日は2時間くらいのThinking Contest。与えられた問題について解法をひたすら考える時間でした。コードは1行も書いてはだめで、「書く前にひっかかりそうなポイントに気づく」という目的があったように感じます。

二日目は初日考えたアルゴリズムを5時間で実装するコンテスト。こんな感じでいけるんじゃない?という初日の甘い考えが悉く打破されていき大いに反省。この日は世界大会への出場権のないコーチを集めたチームが優勝し、さらに「現役チームに2問差はつけて勝ちたかった」と大いに煽られました。コンテスト後はWorld Finalに向けて景気付けの飲み会。京都大学のTeam echizen.comとは僕はあまり話したことがなかったのですが、これをきっかけに話すようになりました。

三日目は、本番形式のFull Contest。前日あんなことを言われたコーチチームに負けるわけにはいかなかったのですが、ちょうどうちのチームに相性の良い問題が多かったこともあって10問中8問正解、2位に2問差。終了直前に1問通したこともあって、とても充実したコンテストに感じました。 コンテストの後には前年の世界大会の問題についての議論をする時間。合宿参加者全員の力をもってしても解法がなかなか浮かばず、実際のコンテストに出たら捨てるしかないような問題がいくつかありました。あの辺りが解ければ上位陣に食い込めるのだとは思いますが、まずは解ける可能性のある問題を確実に解くことからですね。

四日目は、三日目のコンテストの解説会。三日目の問題はきれいな問題が多かったこともあって答えを聞いてしまえば当たり前のもの。そのせいもあってスムーズに進み、お昼過ぎに現地で解散。

解散後はみんなで食事に行き、コンテストに関する話や就職に関するなかなか面白い話を聞けました。

合宿を通して感じたことは、まだまだライブラリの整備が足りないことと、グラフの知識が不十分なこと。幾何の問題はライブラリが解ける解けないを左右することもあるので、世界大会までにしっかりと準備する必要を強く感じました。

最後になりますが、合宿に際して問題を作成したり合宿場所の手配をしていただいたスタッフの方、どうもありがとうございました。

世界大会

文: 林崎

世界大会へ向けての準備

ライブラリの整備

横浜大会の時点では、最小費用流をはじめとして重要なライブラリ群が欠けていました。また、世界大会では持ち込めるリファレンスの量がA4 25ページに制限されていることもあり、コード群を整理して取捨選択する必要もありました。そこで、2月の冬合宿前から3月にかけて、ライブラリの追加、デバッグ、整理等を行いました。

林崎は、Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics) を読んでグラフ理論を勉強しつつ、最小費用流面白いなー、とか思いつつグラフ理論系のライブラリを追加していました。最小費用流大好きです。
# まぁ、グラフ理論の本を読んだのは半分は趣味みたいなもので、全部必要だったとは思いませんが、面白かったのでよし。

Team Notebook の作成

世界大会では、リファレンスや筆記用具等は「Team Notebook」というバインダーに綴じて、Team Notebook以外は一切持ち込み不可、という形式になっていました。我々のチームのTeam Notebookはこんな感じで作りました。バインダーや計算用紙等はオフィス・デポで揃えました。



世界大会 - 諸々のイベント

世界大会(World Finals)は3/12-3/16の5日間に渡って開催されました。 といっても、本番のコンテストは 3/15 の一日だけで、他の日は講演とか観光とかのイベントが用意されています。

今年の世界大会は Japan という国の Tokyo (正確にはUrayasu) という所で開催されました。 今年は海外旅行できなくてちょっとしょんぼりでしたが、海外開催の年の人は海外旅行を楽しんできてください。 来年はカナダの森のお城だそうで。いいなぁ。

Japan での開催ですが、世界大会なので、国外からたくさんの contestants が参加しています。 食事やパーティーや各種イベントが何回か開かれますので、そういった際に私も他の国からの人と話をしました。 有名人も何人か来ますし、普段接することのないプログラマーな人々と交流できる良い機会ではないでしょうか。

この節では、コンテスト本番以前のイベントについて紹介したいと思います。

3/12 - ホテルに到着、Welcome Party

世界大会会場はディズニーランドの近くにあるヒルトン東京ベイホテルでした。 基本的に、本選も含めイベント等はこのホテルの中で行われました。

ホテルに着いたら、 まずチェックインや、 諸手続を行い、 それが済んだらそのまま Welcome Party です。 世界大会ですので英語オンリーです。
ホテルの部屋から眺め。景色がきれい。Mt. Fuji が見えます。
諸手続の時にいろいろおみやげがもらえたのですが、その中にICPCシャツを着た怪獣のぬいぐるみがあったので、そのシャツをきつねに着せてみました。

3/13 - 講演(Tech Trek)とディズニーシー

この日の午前中は Tech Trek という講演会でした。 スポンサーであるIBMの偉い人や、Second Lifeの話と実演とか、Ruby開発者のまつもとゆきひろ氏の講演とか。

まつもとゆきひろ氏の、「Web 2.0というのが実際に何であるかは知らないけど、良いネーミングだったというのは確かだね」(原文英語)という発言には会場から拍手が。

講演会の後はディズニーシーでexcursion。 入場券をもらって移動して遊びました。 私はチームのメンバーと一緒に回りました。 重力加速度を利用して加速度や落下感を演出してるんだなぁ、とか技術的な面で面白かったり。 どうでもいいですが、昼食の量が足りずにちょっときつかったです。

夜は Cyber Cafe というものが開催されました。 これは、ホテルの中にある、本来は日本料理屋である空間を借りて、 そこにネットワーク設備とかデスクトップPCとか Dance Dance Revolution とか持ち込んでいろいろ遊べるようにしたものです。 鉄板の上に Thinkpad が並んでいる Thinkpad 焼き的光景が広がっていました。

3/14 - 練習セッション、日本文化体験

最初に Opening Ceremony。 昨日までは前座で、今日から本番ということでしょう。 挨拶や、スタッフの紹介、それに加え、日本っぽいものということで踊りや三味線(?)の演奏などがありました。

その後で、本番前日ですので、コンテスト環境の練習セッションがあります。 練習セッション自体は普通で、Handouts に書かれている指示に従って解答を Submit してみたり Wrong Answer を出してみたり、といったものでした。
# 秘密の番号が云々みたいなネタは無しです。

その後は、日本文化体験セッションということで、座禅、折り紙、合気道、書道などの体験、アニメに関する講演の中からいくつか選んで参加できるコーナーでした。私が参加したのは座禅と折り紙でした。

まず座禅。 臨済宗の僧の方をお招きして、座る。 そして、禅に関するお話を聞く。 日本語で熱心に質問している外国からのcontestantがいたりしました。 私としては、座禅は初めてだったのですが、これは良いと思い、世界大会後もたまーに自分で座禅をしてみたりしています。

次に折り紙。 講師の方が折り方を(英語で)説明しながら折る。 普通のものは普通に折れたのですが、はばたき鶴は全然羽ばたかず、他の参加者と一緒に何で羽ばたかないんだろう(むしろ講師の人のはなんで羽ばたくんだろう)と首をかしげていました。

世界大会 - コンテスト本番

3/15、ついに本番です。

コンテスト本番

以下、各問題ごとに振り返ってみます。問題解説は手を抜いているので原文を参照してください。

Problem A+

両親と子供のうち、2人の血液型(A/B/AB/O, RH+/RH-)が与えられるので、残る1人の可能な血液型を列挙せよ。

簡単な問題。全通り調べるだけで Accept。その割には、RHのルールを勘違いしていたりして妙に時間がかかってしまった。

Problem B

CBACBACBACBACBA みたいな順番で、A, B, C, ... の荷物が倉庫に入ってくる(アルファベット一文字が荷物一個)。倉庫では、これを順番にスタックに積んで、A, B, C, ... の順で出荷する。いくつスタックが必要か。

解けず。簡単な問題、だったらしい。ほとんどのチームは解けていた。

最初の解法は間違っていた。他のチームのAccept数見て、LISを取るとかしてSubmitしたがWrong Answer。そのまま時間切れ。

greedy で良いらしい、という話を終了後に聞いた。

またB問題か!

Problem C

θ度傾いた斜面上の道(線分列)が与えられる。それを何度か回転させて、全ての道が常に上り坂か水平になるようにしたい。回転させなくても元からOKか、回転させればOKにできるか、何度回転させてもダメか、を答えよ。

それほど難しくない問題。

θが0度の場合は常にOK。θが0度でない場合は、各線分ごとに「x度回転すればOK」という範囲を計算して、その共通部分を求める。

誤差で何度かWrong Answerを出したりして、かなり時間を取られたが、最終的には Accept。

Problem D

格子点上に頂点のある多角形 P が与えられる。Originとは、全頂点が格子点上にあるという条件を満たしつつ、Pをできるだけ縮小したものとする。Originを 1, 2, 3, ..., n 倍拡大した多角形の内部(辺上は含まれない)に含まれる格子点の数の合計を求めよ。

解けず。

Originは、元の多角形Pの各辺の方向ベクトルを(dx,dy)とすると、全dx,dyの最大公約数gを求め、Pを 1/g に縮小した。多角形の中に含まれる点の個数は 面積 = (内部点数) + (辺上の点数)/2 - 1 という公式から求めた。しかし、少なくとも1つミスって通らず。

Problem E

ベルトコンベアがあって、その上を荷物が一定速度で動いている。現在位置Pから一定速度で歩いて荷物を取りに行く。最速で何秒かかるか。

着手せず。ベルトコンベアのどの区間で取りに行くかを決めて、それぞれ調べたりするのかなぁとは思う。

難しいが、時間があれば不可能ではないのだろうか。

Problem F

最大4x4のマスのゲーム盤があり、穴(白丸)が空いていたり玉(青丸)が載っていたりします。壁があったりもします。盤を傾けると玉が転がり、壁にぶつかったら止まります。途中に穴があれば玉は穴の中に入り、穴は塞がれます(再度別の玉が通過しても穴に入りません)。玉と穴は同数あり、それぞれ番号が振られています。全ての玉を同じ番号の穴に入れるために最低何回盤を傾ければ良いか求めなさい。

幅優先探索でAccept。最初の盤面から、上/下/左/右に傾けた時の結果盤面を計算していく。違う穴に入った場合や既出盤面は枝狩り。玉は最大8個でマスは最大16個なので、玉の位置を考えるとステートは少なくとも 16*15*...*9 = 2^29 くらいでは抑えられる。実際にはもっと少ない。私のチームが First Accept でした。

Problem G

最大5種類のメッセージが最大1000個のパケットに分割され順不同に入ってきます。適切にバッファリングを行い、メッセージ1のパケットを順番に全部出力し、次にメッセージ2のパケットを順番に全部出力し、... みたいな感じに出力したい。メッセージの順番はどうでもいい(メッセージ2を全部出力してからメッセージ1を全部出力し、...とかでも良い)。最低限必要なバッファサイズはいくつか?

メッセージの出力順番が決まれば、単純なシミュレーションで必要なバッファサイズは求まる。メッセージが5種類なので、メッセージの出力順番は高々 5! = 120 通りなので、全部調べればよい。

割と簡単な問題。なのだが、問題文を読み間違えて何度かWrong Answer。というか、問題文を正しく読みましょう問題。最終的にはAccept。

Problem H

三角形が1000個くらい与えられる。和集合の面積はいくつか?実際にはもう一ひねりあってさらに面倒。

着手せず。

Problem I

管で繋がれたタンクに水を注ぐシミュレーション問題。気体の圧力や膨張などを考慮する。

着手せず。やってられません。

Problem J

グラフのある点 s からグラフの枝を辿って点 t まで行きたい逃亡者がいます。あなたは、グラフの枝を何本か切って、逃亡者が点 t に到達するのを阻止したい。最低何本枝を切れば阻止できますか?枝を切るのはいつでも良い(複数回に分けて切っても良い)。

着手せず。全然分からず。無理。終了後、他の人とも一緒に考えたが解けず。最初に思いつくのは最小カットを求める方法だが、2回に分けて切ると最小カットよりも少ない回数で阻止できる場合がある。それっぽい解法はいくつか思いついたけど、全部反例が出てダメ。

グラフ問題の難問。

コンテスト後 - 表彰、Celebration Party

Contest was over. しばらくフリータイムがあったのですが、もう一問解きたかったぜ、とかコンテストには付きものの思いを抱きつつ、終わった脱力感にぼーっとしていました。 後は、J問題の解き方について他の日本人と話したり。すごく面白くてすごく難しい問題が出る、それが世界大会。

その後、結果発表と表彰。

Bill Poucher 氏という、世界大会の最初からノリノリなおじさん(ICPCの超偉い人)が仕切ります。 彼の顔は覚えておきましょう。

結果が秘密にされていた終了一時間前(だったかな?)以降のsubmissionの結果を、Bill Poucher 氏が審判長と解説トークをしながら下の順位からopenにしていく発表形式。 Acceptだったりそうでなかったりで、大いに盛り上がりました。
1位はWarsaw Universityの8問。 結果発表の時にスタンディング・オベーションが起きました。これはすごい。

我々は4問で26位。 京都大学に負けてしまったのは悔しい。

この後は、World Finals Celebrationとしてお楽しみタイム。 中国雑技団とか、スリの達人とか(誰だ、審判長のunderwareとかリクエストしたのは!)、手品みたいなのとか。 コンテストが終わった後ということもあり、かなり楽しめました。

終わった後は各自部屋へ。 飲まないかという話もありましたが、酒のフェッチに失敗したので流れてしまった。

ちなみに、私はホテルのロビーで某社のエントリーシートを徹夜で書くとかいうおまけもありました。

まとめ

私は今年がICPC参加3回目でしたが、本格的に練習をし、準備をしたのは今年が始めてでした。 チームメイトの二人といろいろ練習したり勉強会を開いたり大会に出たりと、楽しい一年でした。

またこの一年で、別に全てICPCに起因する訳でもありませんが、実装力は確実に上がったと思います。 ダイクストラ程度ならそらで書けるようになりました。 ソースコードもきれいになった模様です。国内予選直前の自分のソースを見たらけっこう汚かった。

私たちのcontestantとしてのICPC参加はこれが最後になりますが、 後輩たちには色々と期待しております。 がんばって勝ち抜いて上位を取ってください。

また、今まで参加したことのない人(学部3年の人とか)も、興味があれば一度参加してみるのはどうでしょうか。 プログラミング能力といっても色々あり、人によってICPCのようなプログラミングコンテストに向いた性質の人とそうでない人(例えば大規模開発系向きな人)がいると思います(私は前者だと思います)。 なので、ICPCはプログラミングの全てを包括する訳ではありませんが、プログラミングの練習の一つとして、また上位を目指す人にはバトルフィールドの一つとして、いかがでしょうか。