ICPC 2003 体験記

2002年のアジア地区予選大会は、11月3日から5日の3日間、金沢工業大学で開催されました。

我々 チームlighthouse が金沢へ着くと、そこで待っていたのは荒れ模様の天気。 雷に雨に・・・タクシーに乗っているとあられまで降ってきたのだった。嵐の前の嵐?と 言ったところでしょうか。

以下は、11月4日に行われたコンテストの様子のレポートです。

練習セッションでのlighthouse


問題A

試合開始!打ち合わせ通りに一人はPC2へログインし、#include<iostream> などなどの、どの問題にも使う共通のソースを打ち込みにかかる。もう二人は手分けして問題を読み始めるが、 問題Aが簡単と見えたため、まずこれを解いてしまうことに決定。

問題Aは、3つの自然数m,a,bが与えられたときに、積ができるだけmに近く、比率がa:b〜1:1の間 となるような二つの素数を求める、という問題。ちなみに「宇宙に送ったメッセージを長方形に並べると 絵ができて情報を伝えられる」というようなサイドストーリーがついている。問題自体はmの範囲が 100万以下と限られているので、m未満の素数を全部ならべてかけ算して試す、一番単純な方法でも スピードは十分だ。最初にPCへ向かっていたtossy-2がそのままコーディングを開始し、 エラトステネスのふるいにメインループ・・・とプログラムを書き上げ、テストデータでチェック。OK! 早速Submit。

次の問題は?

この間に他の問題を読み込んでいたmkasaの説明をもとに、次に早く解けそうなのはどれだろう? と3人で相談を開始する。まずは消去法で、問題C, Hを後回しにすることに。Cはテキストで書かれた ワールドカップの勝敗表のようなものを読み込むという複雑な作業の必要があって、「絶対一つくらい ミスしそう!」という点で意見が一致したため。Hは誰もとっさに解き方の手がかりすら思いつかなかったため。 ちなみに大会終了後、Hの簡潔な解法を他のチームとの雑談で聞いて、感心したのであった。(^^;

ここでAがAcceptされた、と画面にポップアップ。順調順調。

問題B

次に取りかかることにしたのは、多項式同士が等しいかどうかを判定する、という問題B。 方針は、地道に展開して項の順序でソートして係数を比較、という単純な手で十分そうなので あとは実装あるのみ・・・と思ったのだが、実装開始してみるとなかなか面倒であることが判明。 やっぱり他に当たろう、ということになった。

問題F・問題E

続いて手をつけ始めたのが、問題F。「これ実は簡単じゃない?」と閃いたmkasaが 実装開始。数字の並んだ紙を適当に切って複数の数にして、その和が目標値に 近くなる切り方は?という問題だった。実際スムーズにテストデータも通り、無事accept。 これで2問目だ。周囲を見渡すと、風船の二つあがっているチームがちらほら見える。出遅れたかな?

次に解けそうと考えたのが問題Eの"Ninja House"。こちらはtossy-2がサックリと解決。

問題D

残る問題の中から選んだのは問題D。三角形型のメッシュの頂点に石を置いていって、 囲碁のように生き死にを判定していくもの。印刷して用意してあったチームの アルゴリズムライブラリからUnion-find法を用いてmkasaがプログラムを組む。

・・・と、ここでなんと突然会場の照明が消えて薄暗くなってしまった。雷のせいで 停電とのこと。UPSが働いているので大会運営系統には支障はないとのアナウンスが あったが、かなりビックリした3人であった。

停電!

気を取り直して書き上がった問題Dをsubmit。後になってUnion-findなんか 使わなくてももっと単純なサーチで大丈夫だった・・・と反省するmkasaであったのだが、 しかし無事これもAcceptされた。

問題B再び

ここで一度避けていた問題Bに再び取りかかることに。入力をparseして、 多項式の積や和の計算、はたまた同類項をまとめるコードなど、ICPCに してはなかなか大量のソースを組んでいくtossy-2氏。テスト、submit! 結果はあえなく "wrong answer"。ソースを印刷してデバッグにかかることにする。

問題G

この間に、問題Bに取りかかる二人の裏で問題Gを検討していたkinabaが、 Gのコーディングに入る。「嘘つき族」と「正直族」がいて、「yさんは正直者ですか?」と xさんに訊いたら「yes」と返ってきて云々かんぬん、という、論理パズルによくありそうなもの。 正直者と嘘つきの人数は与えられていて、誰が正直者かを答えればよい問題。

正直者のxさんに「yさんは正直?」と訊いたら、返事がyesならyは正直、noならyは嘘つき。 嘘つきのxさんに「yさんは正直?」と訊いたら、返事がyesならyは嘘つき、noならyは正直。 ということは、xさんやyさんの素性に関わらず、yesならxとyが同じグループで、noならxとyが 同じグループということがわかる。これは簡単だ!と考えて、人を質問のたびに同じグループに まとめていくプログラムを書いて走らせてみる。最後にグループの数が2つにまとまれば それが答えで、2個にならなければ、情報不十分、が答えになるはず。 テストデータで走らせると...あれ?合わない。

よく考えると、グループが2個でなくても「グループの人数を足すと正直者の人数になる組み合わせ」 方が1通りに定まれば、その時も正直者全員がわかるのだ。つまり、この問はこの組み合わせの 探索問題と言うことか...(T_T)

あらためて考え直すために、問題Bへタスクスイッチ。

問題B・問題G 再び再び

幾つか修正すべき点を発見したtossy-2が再び問題Bへ。今度も"wrong answer"・・・残念。 また問題Gに戻る。残り時間がなくなってきたので出来るだけ速く書けるアルゴリズムで行こう! と決めて、組み合わせを全探索するプログラムを書く。当然指数オーダで非常に遅いのだが、 うまくいけば儲けもの、と。しかしそうは問屋がおろすはずもなく、"time limit exceeded"。

再び問題Bの修正版をsubmit。通った!残り時間20分くらいだろうか、この時点で5問 解いているチームは自分たちを含めて3チーム。6個風船があがっているところは見あたらない。 これはもう一問解かねば、とマジメな問題Gの解法を考え出す。動的計画法で計算量を多項式に 落としたバージョンを組んでsubmit!

終盤では審判プログラムも混んできて、結果はなかなか返ってこない。この隙を利用して 完全に捨てていた問題Cと問題Hを・・・とアルゴリズムを考えるが、ロクなものは思いつかず。 しかも先ほどの問題Gの結果は "time limit exceeded"。うーん。

微調整してsubmit→"time limit exceeded"。
微調整してsubmit→"time limit exceeded"。
微調整してsubmit→"time limit exceeded"。
というわけで結局解けずに、試合終了。もう少しだったのになぁ。。。


最終結果は5問正解。3位という結果に終わることが出来ました。 ちなみに雷のために緊急稼働することになったUPSは、 コンテスト終了後残り17分しか持たなかったそうだ。ギリギリセーフである。 大会運営された方々、どうもありがとうございました。

ACM PROGRAMMING CONTENST