IOI2007 2日目 - Game Scripting Memo

1日目に引き続き、国際情報オリンピッククロアチア大会の2日目が終わったようです。選手の皆さま、コーチの皆さま、お疲れ様でした。

さて、2日目の問題ですが、MINERS は、状態が直前2回の各 mine への配給の種類だけだということに気付けば、i回の配給が終わった際にそれぞれの配給状態での最良値を覚えておくだけで動的計画法っぽく解けますので、コード量はそれほど必要有りません。やはり、1問目は（パターンさえ知っていれば）やさしめな問題を配置しているんでしょうね。

PAIRS は、N が 100000 なので、O(N^2) でも行けるんじゃないか、とも思われるのですが、さすがにそこまで甘くないようですね。N * N で city-block 距離を計算するだけなら、一瞬で書けるんですが。メモリ制限も時間制限も微妙にいやらしいのですが、根性を入れて2D木を実装すればおそらくクリアできることでしょう。しかし、手元で頑張って実装した{1-3}D木で750から75000000まで等間隔に並んだ1次元100000個のサンプルを動かした際には16秒かかってしまっています。入力にもよりますが、もう少し効率のいいアルゴリズムがあるのかもしれませんね。ただ、定数倍で頑張れるラインなので、効率的な実装をすれば（vector に何でもかんでも入れるのを止めるとか）もしかしたら普通に2D木でいけるのかもしれません。（追記：2D木では無理でした。1Dと2Dと3Dで別々に処理を実装する必要があります。詳しくは結果のエントリで）

しかしながら、まじめに 1〜3D 木の実装を始めますと、コード量がかなり多くなりますし、バグが入りやすそうな細かい境界条件も多いですので、よほど自信がない限りは本番では最初から突っ込まないほうが正解でしょうね。とりあえず部分点が取れる O(N^2) の回答を submit しておいて、時間が余るまで後回しにすべきかと思います。ここらへんは部分点が入る情オリならではのテクニックですよね。

解き方がもっとも分からないのが TRAINING です。閉路をなくすだけならよくある問題ですが、偶数長の閉路をなくす、という制限がなんともいやらしい。僕自身は2D木の実装にのめり込んでいたので結局解きませんでしたが、おそらくとっかかりの流れは以下のようになるはずです。まず、舗装された道路で全ての都市が木構造を為していますので、適当な都市から初めて、隣り合っている都市が異なる色になるように白黒で塗り分けます。偶数長の閉路を作ってはいけないということですので、まず、異なる色を結んでいる未舗装の道路は必ず取り除かないといけないことが分かります。すると、残るのは舗装された道路と、同じ色の都市を結んでいる未舗装の道路のみとなります。ここまでは簡単にいきます。

この後が問題なのですが、おそらく、未舗装の道路を4つ以上使う偶数長のルートは、必ずそれらのうち2つの未舗装の道路を使って偶数長のルートを作れることが証明でき、未舗装の道路がちょうど2つの閉路を列挙していく、という流れになると思われます。未舗装の道路を偶数個使って出来た閉路は偶数長になることは簡単に証明できるので、あとは3個以上の未舗装の道路からなる閉路は、舗装済みの道路を使うことによって必ず2つの閉路に分割できることが証明できればいいんですが……。何はともあれ、解き方が自明ではない、ということでは一番難しい問題だったのではないでしょうか。（追記：正解は公式の解説を参照してください）

ちなみに、オンラインコンテスト自体はぼろぼろでございました。MINERS はオンラインコンテストの機能をいろいろ触って遊んでいた最中に PAIRS の回答プログラムで上書きしてしまっていることに終わった後に気付き0点。PAIRS は終了直前にバグの取れていない2D木版をあわてて submit したらデバッグ出力が残りっぱなしで、こっちも結局0点でした（＾＾；MINERS は自信がありましたし、PAIRS も N<1000 の部分点は取れるプログラムは書けていましたので、きちんと submit できていれば初日も合わせて300点弱くらいだったのではないでしょうか。高校生向けの大会ではありますが、十分に楽しめました。今後も今年のようにオンラインコンテストを同時にやってくれるといいですね。

さてさて、あとは21日の発表を待つばかり。選手の皆さんはいろいろ悔いも残っているかもしれませんが、せっかくの国際大会です。すっぱりと心を切り替えて、外国の選手と楽しく交流を持ってきてもらえればと思います。IOI は ICPC と比べて観光の時間がしっかり取られているようなので、ちょっとうらやましかったりも（笑）

追記

TRAINING について、閉路を列挙できれば、あとは (M1 or M2) and (M2 or M5) and ... という形の論理式を満たす、重み最小の道の集合を求めるだけだなぁ、と思っていたのですが、もしかしてこれもひと仕事ですか？論理式だけを見ると 2-SAT ではありますが、正項だけなので SAT とも呼べないし、重み付きなほうが問題だなぁ、と思ってすこしぐぐってみたところ、こんな資料(PDF)を見つけました。どうも、正項だけの乗法標準形を加法標準形に変換する「単調な論理関数の双対化問題」という話があるんですね。加法標準形に変換できれば、あとは各項の重みを調べて最小のものを選べばいいだけではありますが、ここまでのバックグラウンドを求めている問題だとしたらすごいですね（＾＾；