IOI2007 1日目

国際情報オリンピックのコンテスト1日目が終わったようです。クロアチアで本番を頑張っている選手たちから1時間遅れでオンラインコンテストが試せましたので、ちょっとだけトライしてみました。

5時間で3問というのは ACM/ICPC の極限状態と比べたらかなり余裕があります。しかし、IOI は個人戦ですので、孤独な戦いを5時間行うと考えるとたいへんですね。選手の皆さま、おつかれさまでした。

1日目の問題を見ると、ALIENS は 300 回という使用制限をクリアするためのバイナリサーチもどきの工夫が少し要りますが、実装はそれほどたいへんでないですし、SAILS は greedy に解けるはずですので、一番たいへんだったのはメモリ制限が厳しい FLOOD でしょうか。

と思って結果を見たら、SAILS が間違えまくっていました(汗)。よくよく考えてみると、以下のようなケースがあるので、単純に greedy にはいかないのですね……。

4
1 1
1 1
3 2
2 1

最大で 2^(100000*100000) くらいの状態がありますので、安易にバックトラックも出来ませんし。んー。どうしたらいいんでしょう。左右の交換は問題を変えないので、マストを背の順に並べてみるとか……?(追記:解説をみたら、それで当たりでした)

ICPC では、全てのテストケースに通ったかどうかが submit した時点で分かるので、こんな感じかなぁ、と思ったら、とりあえず submit して通るかどうか見る、という手をしばしば使います。しかし、情報オリンピックでは submit 時には sample input に通ったかどうかしか出ないので、終わってみないと本当に正しいプログラムを書けていたかどうかが分かりません。深く考えるのが苦手な自分には、なんとも辛いところ。(追記:回数限定で少し詳細な結果を得ることもできたようです)

また、ICPC と情報オリンピックの一番の違いは、ICPC は各問題で全てのテストケースに通らないと点が入らないのに対して、情報オリンピックではテストケースに通るたびに点が入ることでしょう。そのため、情報オリンピックでは設問からさらにこれだけ条件を絞ったテストケースが何点分ある、といった部分点情報が問題に記載されています。

FLOOD に関しても、座標値の最大が1000000もなければ簡単なのですが……。とりあえず、40点分の部分点狙いで vector > is_water で実装してしまいましたが、見事に40点しか取れませんでした(涙)。グラフの閉路を求めて、それが包む頂点群をマークしていく、という感じで実装すればよかったんでしょうかね。

凸ではない多角形と点の包含判定をどう書くかがとっさに出てこなかったので実装しなかったのですが、無限遠に半直線をとばして辺との交差数を数えればいいんでしたっけ。あぁ、昔、頂点との交差部分の処理を間違えてはまった思い出がふつふつと。そして、頂点がグリッド上にしか存在しないのだから、x を遠くにとばして y を 1 だけずらせば、半直線と頂点が重なることはないから判定を省略できる、という番くんの素敵なソリューションに感動した10年以上前の合宿での思い出も蘇ってきました。そう考えると、情オリって昔から似たような問題が出ていたんですね(笑)(追記:実は幾何的な処理をしなくても十分に解ける問題でした。柔軟な発想が重要です)

それはさておき、コンテストの2日目は日曜日です。オンラインコンテストは日本時間の日曜日16:30から開始のようです。チャレンジしやすい時間ですので、ご興味がある方はお試しあれ。