アジア予選マニラ大会

文責:吉野 寿宏

マニラ行きが決定するまでの経緯

国内予選によって国内のチームの選抜が終わると、 次はいよいよ世界大会に進むチームを選抜する地区予選の時期がやってきます。 アジア地区予選は日本(今年は愛媛でした)をはじめ、韓国・ソウルや中国・北京など 各地で行われます。世界大会への出場権を確保するためには、 これら世界大会で優勝する必要があります。(厳密にはワイルドカードチームなどの適用があるため、 2位や3位でも行ける場合もあります。) もちろん各国の強者がそろって参加してくるわけですから、これはかなりの難関なわけです。

しかし国内予選でよい成績を修めた何チームかには特典がありまして、 本来自分の参加すべき地区予選サイトの他にもう一箇所、 海外のサイトにも参加することができるのです。私たち Gokuri-Squeeze は なんとか国内予選で優勝することができましたので、海外派遣されることが決まりました。

実は最初に希望を出していたのはインドの方でした。

インドあたりって、エキゾチックな雰囲気もあって興味はありますが、 なかなかこういう機会でもなきゃいけないよねーという話になって選んだわけですが。

しかし、治安などの都合上もあって、北京かソウルかマニラにしてくれと 言われてしまいました。韓国は去年行きましたし、中国はものすごい強豪ぞろい。 となると、残るはマニラということに。確実に地区予選でよい成績を残すためには、 (多少言葉が悪くなりますが)強豪ばっかりのサイトに殴りこんでいっても ほとんど勝ち目はないわけです。なので中国はできるだけ避けたかったとかなんとか。

かっこいい言葉でいうと戦略的撤退とかいいます。がーん。

マニラ行きの朝

そんなこんなで月日は経ち、ついに出発の朝となりました。

午前中の便を選んだため、朝 7 時ごろ成田でカウンターに集合というハードスケジュールです。 この時間帯はいつも使うスカイライナーまだ走ってないよ! 仕方ないので駅から近い メンバーの家に一晩泊まって、5 時ごろに京成線にゆられてとことこ成田へと。 駅までの道のり、夜明け前の寒風が肌にしみます。そして電車にのって 90 分。 徹夜してるので、座ると寝てしまいそうです。

この日は成田に近づくにつれひどい霧がかかっていて、 ほんとに飛行機が飛ぶのか微妙に心配でした。チェックインやら出国手続きやらを 済ませて搭乗ゲートに向かうと、100m 先が霞んでるような状況なんですね。 しかし別に遅延という話も聞かず、飛行機は無事定時に出発。

フィリピンのニノイ・アキノ国際空港までは、日本からおよそ 4 時間といったところ。 時差が 1 時間あります。飛行機を降りるとそこは南国でした。日本での寒さが嘘のよう。 入国手続きを済ませ、荷物を受け取ってから、まずは両替所へ。 あとついでに、帰りの航空券のリコンファームも行っておきました。

フィリピンの国内通貨ペソは、国外持ち出し量が制限されているために、 日本ではなかなか両替できません。レートはだいたい、1 ペソ= 2 円くらいです。 物価を考え合わせると、感覚的には 1 ペソが 10 円くらいかなと。

マニラにて

会場となった University of Asia and the Pacific は、オルティガス市中心部に位置しています。 空港から会場まではタクシーでおよそ 1 時間といったところ。私たちが会場についた頃には、他の参加チームも集まって開会を待っているところでした。 マニラサイトは東南アジア諸国からチームが集まる巨大なサイトで、今回の参加チームは 80 を数えたそうです。

マニラでは交通渋滞がひどい。会場まで行くときに EDSA と呼ばれる都市の動脈道路を通ったのですが、ここはほぼ常時渋滞しているらしいです。 一部地区を除いて交通信号がほとんどないので、車を運転するときは「前が空いてたら進め」で OK のようです。歩行者の横断や車線変更もしかり。

On-site registration を済ませたところに、一人のスタッフが近づいてきました。マニラサイトには海外からの参加が多いので、海外チームには一人ずつ student counselor (UA&P の学生がボランティアでやってくれています)がついてくれるのだとか。 市内観光なども、あちこち案内してもらいました。

初日はチーム登録を行った後、開会式にてスケジュールやルールの説明がおこなわれます。その後は場所を体育館に移して歓迎パーティーとなりました。 食事は、まあわりとありふれたタイプのものでした。多少スパイスなどの使い方にエスニックというかアジアンテイストな感じはしなくもないけれども、ベースはよく見知った料理が多いみたい。 パーティーの席では交流を盛り上げるためのビンゴゲームが企画されていました。各マスに条件があり、その条件を満たしている人を探してサインをもらうというルールです。

私は結構人見知りするほうなので、あまり自分から話しかけるということはしません。なので、こういう場合相手から会話を切り出してもらえるとすごく助かったりするのです。 今回はわらわらと大勢に取り囲まれまして、テンションに圧倒されつつも結構楽しかったかも。 みんな社交的でいいなあ。

2 日目・午前中

この日はマニラは雨。 それでも朝の時点で気温は 25 度とかあります。泊まったホテルの向かいには学校があったのですが、プールに人影が見えました。

午前中は暇なので、マニラ市内観光に連れ出してもらうことに。 近所にショッピングモールがいくつかあるということで、CD を見たり本を見たりして。スターバックスでコーヒーを飲みつつ、お互いの学生生活について語らったりしました。 街中では、まだ 11 月半ばというのにクリスマスリーフやらツリーのかざりつけやらがあちこちで目に付きます。フィリピンでは人口のほとんどがカトリックのため、クリスマスは毎年一大イベントになるのだとか。リオのカーニバルみたいなものでしょうか。

しかしショッピングモールってだいたいファッション系のお店が多いですね。私とかはあんましブランド物には興味がないので、大方のショッピングモールユーザとは嗜好が違う気がします。たぶんえらく安上がりな観光客です。(笑)

練習セッション

午後からは、まず練習セッションが行われます。 チーム数が多いというのもありますが(マニラ大会には、各地から 80 チームが参加しています)、部屋が結構狭かった感。段々畑スタイルの講義室の長机に 3 台ずつ PC がおいてあって、その間のスペースを等分して使うようになってました。 それでもおっつかなくて、結局 4 部屋ほどに分かれていました。

マシン環境はといえば、Windows2000 に Cygwin やら VC++.NET Toolkit やらがインストールされているもの。 Windows だとエディタに何を使うかが悩みどころです。 結局、普段は xyzzy やら emacs なので、Cygwin の X server を立ち上げて emacs を使いました。ちなみに周りのチームは、メモ帳派が多かったみたいです。(あとで「emacs 使ってたのお前らだけだー(笑)」とか言われました。)

練習セッションの問題は、98 年ごろの Dhaka の問題の一部だったようです。 日本だと「二つの数を足し算せよ」とか「行数を数えよ」とか、練習の名のとおり超簡単なものが来るので、ちょっとびっくり。

2 日目・夕食

練習セッションが終わったところで、counselor の人と待ち合わせて日本料理店「Kitaro」へ連れて行ってもらいました。

とりあえず、よく聞いた事のある料理が並んでいます。丼物のところには「Oyakudon」(親子丼)・「Katsudon」(カツ丼)・「Bibimba」(ビビンバ)とか。…ビビンバって日本料理だっけ? 私はとりあえずビビンバをチョイス。かなりスパイシーですけど、かなりおいしいです。ごはんも普通(ちゃんと炊いてあった)でした。

しかし、飲み物として "Green Tea" なるものを頼んでみたら…メロンソーダからアイスと炭酸を抜いたような飲み物がでてきました。 あるいは、カキ氷シロップを薄めた奴といいますか。どこが Tea なんだろう。(笑

本番当日

マニラサイトでは、コンテスト開始は午後からです。寝坊しがちな IS の人間にもやさしいです。(笑) なので、ゆっくりと睡眠をとって、朝ごはんをしっかり食べて。万全の体制で臨みます。

登録を済ませた後、まずは席順の抽選会。…が、これがなかなか終わらない。結局全チームがくじを引き終えたころには、もう開始予定時刻を過ぎていました。 Gokuri-Squeeze は、前日の練習セッションでは No.20 でしたが、当日は No.41。各部屋には 21 チームずつ押し込まれるので、実は部屋は変わったけど場所的には前日の位置と同じだったりします。

コンテスト開始前に、環境設定の時間として 20 分ほどが用意されていました。 この間に各チームはマシンにログインして、エディタやコンパイラなどの環境を設定し、PC2 でちゃんとサーバに接続できるかどうかをチェックできます。

ICPC では問題が解けるごとに風船が運ばれてくるのが恒例行事となっています。風船の色で、どのチームがどの問題を解いているかが分かるので、解くべき問題を迷った時には判断材料として使うこともできます。 しかし今回はチーム数が多く、部屋がいくつにも分かれていますので、他の部屋にいるチームの風船を直接見ることはできません。かわりに、どの問題が解けているかという風船のリストが、Web ページとして公開されていました。 せっかく Windows なので、Active Desktop で貼り付けてみたりして、開始の合図を待ちました…。

コンテスト開始!

さて、そんなこんなでコンテスト開始です。 まずはテンプレートを打ち込んだあと、手分けして問題をざっと読んでしまいます。

とりあえず最初の問題である A を読んでみたところ、パターンスキャナの問題。規則的に生成される長い文字列の中から、8 文字以下程度のパターンが何回出現するかを数えよ、という要請です。 文字列の生成は指定されたパターンの繰り返しで行われるので、うまくすれば高速に求めることはできるかもしれません。 しかし、いかんせん境界の処理とか、絶対ミスが頻発することが予想されたため、とりあえず生成して比較というナイーブなコードでいいんじゃなかろうかということに。しかし文字列が 8M 文字と長いため、時間制限が怖く、ちょっと後回しに。

その間に、問題 C と F が読めたのでとりかかります。

C は、異なる額の現金の入った、高さの異なる箱が一列に並んでいて、それをいくつか選択するという設定です。このとき、選択された箱はもとの列において左のほうにあった箱よりも高さが低くなければならない、という条件がついています。 この条件の下で、中に入っている現金の額を最大化せよというのが問題。左から右へ、一方向に見ればいいので、簡単な DP の問題です。 しかし、それだけだとさすがに簡単なので、数値がカンマ区切りで、間に空白を含むかもしれないという設定になっていました。このへんは書くだけというのもありまして、あっさり通すことができました。

F は問題文が結構長かったのですが実は、指定された範囲にある、ある数の倍数のうちから、あらかじめ指定されたいくつかの素数の倍数となるものはいくつあるかを求める問題でした。 指定範囲というのが高々 10,000,000 くらいまでなので、とりあえず単純に数えるだけですね。

次に取り掛かったのは D です。 D は文字列のパターンマッチングを行う問題。正規表現を簡単にしたようなものと思えばよいでしょうか。 パターンの 1 文字は元の文字列の 1 文字にマッチするということだったので、とにかくルールを書いてシミュレーションすればおしまいです。 ただし問題文の用語定義が微妙だったこともあって、clarification が何度かでていました。問題文に記載されているテストデータが間違っていたり問題文が曖昧だったりするときは、審判団に PC2 のシステムを用いて問い合わせるのですが、これを clarification と呼びます。

ちょっと心配要素はありましたが、とりあえず書き上げて一度 submit してみました。しかしあえなく Wrong Answer。 問題文と、今までに出ていた clarification の内容をじっくり検討したところ、表示の優先順序などが異なっていたことに気づき、修正して submit。今度は通りました。

そして問題 B。N 面ダイス(ただし各面の数字は 1 から 200 までで、同じ数字の面があることもあります)をいくつか投げ、その目の合計が最大となる数字とその確率を求めよという問題でした。 DP でいけるのでは? と気づいてさっくり書いてみたら、これまたさっくり通ってしまいました。 確率を保持しておくより、場合の数で保持しておいて最後に場合の総数で割る方式をとっていたのですが、後ほど検討してみたところ、ひょっとすると範囲をはみ出す可能性があることに気づいて冷や汗。でも通ったからいいか。

で、ここらへんで再び問題 A に戻って。 32bit 単位でビットマスクとりながら比較する方式に変更して、高速化されたことを確認して submit。通りました。 どうやら、実際制限時間は 2 分あったということなので、ガリガリまわすだけでもよかったみたいなんですけど…。(苦笑)

中盤戦

コンテストも半ばをすぎた頃。 問題 E, G, H を残している状態で G が書きあがったのでとりあえず submit。ところがなかなか返答が返ってきません。 どうしたのかと思いながら、並行して解いていた問題 E を送ったのですが、あえなく Wrong Answer という結果に。どうも問題の要請に曖昧な部分があったので、clarification を送ることになりました。

問題 E は、ディレクトリツリーのようなもの T と、そのツリー内のノードの部分集合 S が与えられ、「あるノードとその子孫のノードを選択する」という操作のみを用いて、S に含まれるノードを全て選択する最小の操作を求めよ、という問題でした。 S に含まれないノードを選択することを許すと、木の根を選択してしまえば自明に S の全てのノードが選択されます。もちろん、この解は自明すぎるがゆえに、問題にはなりえません。しかしながら実際サンプルデータを見ると、S に含まれないノードを選択している例が含まれています。

審判団から返って来た答えでは、「明示的に T のノード定義リストに含まれていないかぎり、親を選択できるとは限らない。したがってそういう選択はできない」ということ。しかし今度は別のサンプルデータで、T のノード定義リストに含まれていないノードを選択していました。 どちらにせよサンプルデータとかなり矛盾するのですが…ともう一度 clarification を送ってみました。今度は「問題にミスがあるので、しばらく審判団は協議している。他の問題をやっていてくれ」との答え。

G の結果がまだ返ってこないので、念のため G をもう一度 submit しておいて、最後の一問である H に手をつけ始めました。 H はデータベースの JOIN 操作のようなものを行えという問題でした。通常データベースならカラムに名前がつけられており、それでどのカラムをキーにして JOIN すればよいのですが、この問題では名前がついておらず、データセットから判別せよということでした。 条件など問題の設定がわかりにくいが、実装をがんばれば解ける類の問題という認識。サンプルデータや要請に関して Clarification もいくつか飛んでいました。 しかし、2 度目に送った G の返答がなかなか返ってこないことにやきもきしつつ、H のコードを書き進めるしかありませんでした。

ラストスパート

最後 1 時間ほどのところで E の問題修正がでました。 結局のところ、S に含まれる以外のノードは選択してはいけないということで、T の定義すら見る必要はなく、S の内容を prefix match でごりごり消していけばいいだけという問題に。あらあら。 で、コードを直して submit。今度は通りました。

それから set<int> やら reordering やらが乱れ飛ぶ H のコードを、頭がわやくちゃになりつつもなんとか書き上げて。 とりあえず動くものはできたけど、チェックしてみたら最後に出す答えの順番が違ってるー! というハマリがあったのですが、もうこの時点で残りは数分しかありませんでしたので、今からの修正は間に合いません。無茶を承知で一度投げて…。 この頃になると、スタッフが私たちのディスプレイを一緒に覗き込んでいたりします。(席が一番後ろだったもので。)

…そして、戦いは終わりました。 ちなみに、G の返答はついぞ返ってくることはありませんでした。(後に結果を見たところ、ちゃんと解けていたらしいですが。)

表彰式

終了のアナウンスが流れると、会場は一気になごやかムードに。 達成感にしばしば浸りつつ、夕食会へとなだれこみます。「がんばったねー」「問題どうだったー?」とかお互いにトークしてました。

表彰式は、コーチミーティング終了後の 19 時ごろより開始。 前置きとかはもうこの際ナシです。どんどこ大学名を読み上げては、賞状を渡していきます。 複数チームが来ている大学なんかだと、自分の大学が呼ばれたときは全員で大いに盛り上がりますね。

で、なんとか 10 位前後まできて…「あとはとりあえず全員ステージにあがれー」との指示。 私たちもステージ上にあげられて、10 位から再び賞状授与がはじまります。9 位、8 位と進み、ついにはステージ上には残り 2 チームとなりました。

風船の状況を見ていた感じでは、もう一つのステージ上に残されたチームである Atheneo 大学チームとうちが結構競っていたみたいでした。終了 1 時間前の時点で風船の更新はストップしたのですが、この時点で両チームとも 5 問。他には 5 問のチームはありません。 その後 E が解けているので、G が解けていて 7 問、解けてなくても 6 問が確定しています。 しかし、うちのチームは何度か Wrong Answer ももらっている上に、動きが遅いので(最初は弾丸スピードですが、ある程度難しい問題が残る状況になると「a bit slow but sure」を目指して多少ゆっくりになるのです)、ちょっと微妙かなあと思っていました。

 "And the first place goes to..."

 "University of Tokyo!"

結果的には両チームとも 7 問解けていたことになり、勝負は時間になりましたが、30 分差でなんと優勝してしまいました。 紙ふぶきが降って来たり、写真をとられたり。あとはもうひたすら握手やら「Congratulations!」の嵐でした。

ICPC はなるべく多くの大学から参加者を集めるという目的があるので、参加年限に制限があります。大学入学後 5 年を経過してしまうと、もう参加できなくなるのです。 Gokuri-Squeeze のメンバーは今年全員修士 1 年でしたので、今年はラストチャンスでもありました。 その最後の年にこのような結果が残せたことは、大変光栄だと思います。

帰国の途

翌日の帰国は午後便でしたが、おみやげを買ったりしたかったのでちょっと早めにホテルをチェックアウトして、タクシーで空港を目指します。 相変わらず道路は混雑していますが、完全にストップしているわけではなく、それなりの速度で進んでいます。また、郊外方面だったためか、30 分ほどで空港までついてしまいました。行きは一時間近くかかったというのに。(笑

とりあえずチェックイン・出国手続きなどをしてから、空港内の免税店を見て回ったのですが、なんかあまりフィリピン名産、みたいなものは多くありませんでしたね。ちょっと残念。 結局ドライマンゴーと、あとはどこにでもあるけどチョコレートを少し買いました。

午後 15 時ごろにフィリピンを経ち、日本に帰りついたのは 20 時ごろ。もうすっかり夜になっていました。 お疲れ様でした、と挨拶をして別れ、なつかしの我が家へ。

Copyright © 2005- Team Gokuri-Squeeze (gokuri _AT_ isers _DOT_ jp)