ICPC 2009 Tokyo

行ってきました、ICPCアジア地区予選。


結果はチーム別で6番め。日本人チームでは3番めでした。

俺たちより上位にいる日本人が東大チームだけだったので、

(まぁいろいろややこしいルールがあるのだけれど)

もしかすると世界大会に行けるかもしれません。

2週間もしたら世界大会行けるか分かるはず、、

いろいろ頑張ったし行けるといいな、行きたいなw



ちなみに世界大会、来年は中国のハルピンというところであるらしく。

2月に開催なのですが、最高気温が10度、最低気温は20度らしいです。

え、最高気温が最低気温より低いじゃないかって？

いや、最高気温が"氷点下”10度で、最低気温が氷点下20度なのですよ笑"



さてまぁせっかくなので、今年はどんな風に問題を解いたか載せてみます。

問題はこちら。http://www.waseda.jp/assoc-icpc2009/contest/problems.pdf

pdfなので気をつけてくださいねw


開始早々、パソコンがサスペンドになるというハプニングが発生。

どうやら相方がログインボタンと間違って、

サスペンドボタンを押してしまったらしいw

まぁそれは簡単に復帰できたので、

面白いこともあるものだとか思いながら問題を読みにかかりました。。

例年に比べて問題文が長くて、

１つの問題を読むのにかなりの時間がかかりそうでした。

なので問題の図を見ながらパーっと問題を斜め読み。。

例年はA問題が一番簡単で、次がB問題、次にC問題...となっているのですが、

問題の図をみたところではなんかA問題もB問題も簡単ではなさそうで。

とりあえずC問題を頑張って読んでみたところ、

それなりに簡単そうだったので俺がプログラムを書くことになりました。

その間に他の2人が問題を読んでくれていたのですが、

何やらさっそくA問題やB問題に正解したチームが現れたようで。

どうも問題を読み終わった友人に問題文を聞いてみると、

どうも問題を勘違いしていたようで、とても簡単な問題でした。

ICPCは解いた問題数だけではなく、"如何に早く解くか"ってことも

重要視されるので、やや時間のかかりそうなC問題を放置して、

慌ててA問題を解くことにしました。


ちなみにA問題はこんな感じ。

1辺1mの立方体がいくつか積んであります。

南からそれを見ると、こんな感じに見えました。

+-+-+
| | |
+-+-+-+
| | | |
+-+-+-+

また、西から見ると、こんな感じに見えました。

    +-+
    | |
+-+-+-+-+
| | | | |
+-+-+-+-+

さてこのとき、立方体は最低でいくつあるでしょうか。。

ただし、立方体が宙に浮くことはできないものとします。


ちなみにこの場合は、7個の立方体があれば実現できます。分かりますか？w

A問題を提出してから3分ほどして、"正解です"との返事が帰ってきました。

ひとまず1問正解ということで、やる気が出てくるのでありましたw

その後B問題も難しくないことが分かったので、さらさらっと実装。

ちょっとバグったものの、まぁ3分ぐらいでバグが見つかって、これも正解。

相方がD問題を解きたそうにしていたのでパソコンを譲って、

C問題を早く解くにはどう書いたらよいかを考えていました。

その後しばらくして相方がD問題を提出、正解しました。

再びパソコンの前に座り、相方と相談しながらC問題を実装。

再び答えが合わずに焦ったものの、3分か5分ほどで見つかったので提出。正解。


ちなみにD問題が説明しやすいので紹介しておくと、、

"床の上に、100個の白黒の碁石が落ちていて、その座標が与えられます。

この時、床の上に長い棒を置いて、その片側には黒石だけ、

その反対側には白石だけになるようにすることができるでしょうか。"

この問題は人間が見たらほぼ一瞬で答えが分かりますよね。

だって白石と黒石が綺麗に2つに分かれていたらYESで、

白石と黒石がごちゃごちゃ入り乱れていたらNOなのだから。

でもコンピュータには目がないので、こういう問題は得意ではありません。

というわけで人間には簡単だけどコンピュータには難しい問題の1つでしたw


さてこの4問解いた時点でうちのチームは10位ぐらいでした。

うちのチームは簡単なA問題からでなく、C問題から解きはじめてしまったので

タイムロスが生じたのでした。そしてこれは予定より低い順位でした。(涙

去年までの俺たちなら、”負けている”という事実に焦って、

悪循環に陥ってしまうところでしたが、、今年はちょっと心に余裕があったので、

みんなで「落ち着いて解いて最後に逆転を狙おう」と励ましあっていましたw

この時点で2時間が経過。コンテストはあと3時間。。



ちょっと大会が終わってから寝不足ぎみで辛いので、

続きはまた今度書くことにしようと思いますw