ICPCアジア地区予選横浜大会観戦記+α

http://www.acm-japan.org/icpc2006/jp/index.html

先週のマニラに引き続き、東京大学のMakegumiのコーチとして
横浜のアジア地区予選に行ってきました。
といっても、今年は私は東京に住んでいるので、
会場まで電車で30分ぐらいというなんとも近場でした。

しかし、なんといいますかね。
あまりにも歯痒い。
見ているだけというのも辛いものですね。
願わくば、もう手を出しちまいたいですよ。
自分がもう参加できないのが悔しくて悔しくて仕方が無いですね。
夢は後継者に託すものと思いつつも、
この抑えられない衝動はどうしてくれよう？
とか何とか言っても、私も皆と一緒におとなしく観戦していたわけですが。

今年は結果的には上位は結構競っていましたね。
(ある一つを除いては、ですが…)
私個人的な意見を言わせてもらうと、
問題の難易度的にももう一つぐらいは解いて欲しかったし、
解ける実力のあるチームもあったと思われます。
なにより、SJTUが7問解いてますからね。
私がコーチをしていたMakegumiはちょっと残念な結果でした。
ちょっと問題Bにはまってしまっていたように見受けられましたね。
これで東大からは世界大会にどのチームが行くのかは
すっぱりとは決められなくなってしまいました。
マニラ2位のMakegumiか、横浜3位のkitune-か、
直接対決で負けている分Makegumiが不利なようにも思いますが…。
あとはアジアディレクターの指示を仰ぐのみです。

さて、いきなりですが、今回の問題について詳細な解説をすることにします。
問題が公開されてから自分で解きたい、という方は
今のうちに引き返すのがよさそうです。
なお、問題の難易度の正確な把握のために、問題I以外は解答を作りました。
問題Iは有名アルゴリズムの問題らしいので、ちょっと解く気がしません。

http://fxp.infoseek.ne.jp/icpc2006/yokohama/a.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/b.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/c.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/d.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/e.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/f.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/g.cpp
http://fxp.infoseek.ne.jp/icpc2006/yokohama/h.cpp

いずれもまだジャッジ入力が公開されていなくて、
サンプルしか通していないため、
No-Wrong Answerを食らうかも知れません。
No-Time Limit Exceededは多分食らわないと思います。

まずは全体を眺めての感想ですが、
泥臭い問題が多くなったなぁという印象ですね。
日本のリージョナルは例年海外に比べてどろどろした問題が多いと思いますが、
今年は輪をかけてその傾向が強くなったという感触です。
探索があまりにも多いので、探索をしっかりがりごり書ける人が
今回は良かったんでは無いでしょうか。
そのほか、去年から変わったこととしては、
易しい幾何がいくつか出されて、
最終問題が幾何じゃなくなった。
この辺りは変わってもおかしくなかったと思うところ。
とりあえずはABCDが簡単なので、
プラスいくつ解けるかという話になってきます。

以下、各論。

- - - -

問題A

三次元空間上の三点がなす角度を求める問題。
A・B = |A||B|cosθさえ知っていればそれまでだろう。

問題B

与えられた多角形の内部に、その全体を見渡せるような
領域が存在するかどうかを判定する問題。
多角形のそれぞれの辺で領域をクリッピングしていけば、
最終的に領域が残るかどうかで判断できるので、
クリッピングライブラリを持っていればそれを打ち込んでもいいが…。
この問題の場合、"そのような領域を求めよ"ではなくて、
"そのような領域の存在を確認せよ"なので、
あきらかに問題としてそれよりは簡単。
なので、クリッピングを持っていなくてもあきらめてしまってはいけない。
方法を次に述べておきます。

メインのアイデアとしては、全てを見渡せる領域があるかどうかは
図形内部の点を全て調べればよいということ。
しかし、現実的にそれをやるのは不可能なので、
ここさえ調べれば十分、という代表の点を選んでやることにする。
どのような点を調べればよいか？
領域は明らかに多角形の辺を延長した直線によって分割されるので、
おのおのの領域の中の点を一つずつ調べれば十分である。
誤差を考えれると境界上の点で十分で、突き詰めるとそれは
直線の交点でよいということになる。
つまり、多角形の辺を伸ばした直線の交点を列挙してやって、
それらの点のなかに図形内部全てを見渡せるものがあるかをチェックすればよい。
見渡せるかどうかは、その点と各辺が為す三角形の符号付面積の符号が
全部一致するかどうかで分かる。
これでこの問題はとても簡単に解ける。

問題C

対面が同じ色で、三色に塗り分けられた立方体が8パズル状に並べられていて、
それをごろごろ転がしてある特定の状態にするのに最短手数を求めるというもの。
ただし手数は30まで。
明らかに計算量の上限が3^30なので、
IDA*なり枝刈DFSなりなんでも通りそうな気がするが、
盤面の状態数が7(さいころの置き方6通り+空)^9≒4000万なので、
手数の上限がなくともBFSが間違いなく終わる。
オーバーヘッドを減らすために、盤面はintにエンコードしておけばいいだろう。
多少実装が面倒。

問題D

k個の互いに異なる素数の和でnをあらわす方法の数を求める問題。
n<=1120,k<=14
みえみえのDP。

問題E

ナンバーリンク、
数字2対、盤面9*9まで、障害物あり、最短距離を求める問題。
全探索+枝刈。
昔Cマガ電脳クラブに15*15ぐらいで数字10対の問題が出ていたような気がする。
それが現実的な時間で終わるので、
これももちろん間に合う。
Cマガ電脳クラブの問題は一月仕事だが、
これは5時間しか時間が無いので、
枝刈はあっさり目でもOK。

ア)┌┐ イ)┌─┐ウ)┌──┐エ)┌─┐ 
   ││    │  │   │    │   │  │
                               │┌┘

ア：コの字(0)
イ：コの字(1)
ウ：コの字(2)
エ：途中でくっつく

この程度を刈ればよい。
コの字の間が三つ開くのは、

┌───┐ 
│┌─┐│
  │×│

のような場合があるので刈れない。

あとはこれを実装するだけ。
探索としては、一本をまず伸ばして、経路を作り、
それからもう一本を幅優先探索するのがいいだろう。
コードは書いてみると意外と1時間弱で済んだ。

問題F

x^n (n<=1000)を計算する最短の演算数を求めるという問題。
たとえば、x^31 なら、
x^2=x*x, x^4=x^2*x^2, x^8=x^4*x^4, x^16=x^8*x^8, x^32=x^16*x^16, x^31=x^32/x
で6ステップということになる。
計算の途中で出てきた値は再利用できる。

うまい方法がありそうで実は無い問題。
解いたチームの片方はDFSで、もう片方はBFSで解いたらしい。
どうやったら計算量の推定が出来るのか知りたいところだが、
分からないけど突撃したとのこと。
うまい解法が無いという自身があればそういけるのか？
最初から探索で解けると聞けばそりゃ解けるけど、
そうじゃなけりゃ解法を探してしまうような気がする。

私はDFSで解いてみた。
かなりアグレッシブに枝刈を入れると、
ようやく現実的な時間で解けるようになった。
・現在までの最短を越えたとき
・後一手で解けるとき
・後一手で解かなきゃいけないのに解けないとき
・残りを全て倍倍にしていっても目標に到達できないとき
このあたりで、1から1000まで全て計算して90秒ぐらいになった。
さらに、最長が13であると仮定して、
11手の時点で計算を打ち切ると一分を切るぐらいになった。

しかし、ちょっとこれは大変だと思う。
解いたチームは優れたバランス感覚を持っていると思う。

問題G

棒がいくつか与えられるので、それで多角形を作ったときの最大の面積を求める問題。
ただし、棒の端が置けるのは格子点上のみ。
棒の数は6つまで、長さは300まで(整数)。
棒の数が7でも8でも9でも10でもなくて6な時点で探索臭がぷんぷんと。
棒の順列、720回それぞれで全探索をしてやればいいが、普通にやると計算量が間に合わない。
というのも、ピタゴラス数の組み合わせが36個もある長さがいくつもあるので、
それが6つ入ってくると、単純な全探索だと、36^6≒21億になってしまうので、
これを720回もやっていてはどう考えても間に合わない。
(しかも親切なことにサンプルにこの例が入っている)
選択肢としては2つ。
ひたすら枝を刈るか、
両側探索をするか。
枝刈は、反時計回りになっていない、2π以上回転した、y座標が負になった、
残りを全て使っても出発地点に戻ってこれない、最後に作った辺と出発点の位置関係がおかしい、
直前の辺を逆走した、などなど、いろいろ考えられるが、
かなり頑張らないといけない上に、図形的性質をたくさん使わなければならなくて辛い。
おそらく両側探索をするのがこの問題では正着だと思われる。

両側探索だと、探索空間は大幅に減って、36^3≒4万ほどになる。
これに加えて、合流地点を第一象限に限ることによって、保存ライン数を4分の1に、
permutationで回転を省くと、探索回数6分の1、
さらにミラーを省いて2分の1。
これぐらいをすれば十分現実的な時間で終わってくれるようになる。
反時計回り、時計回り縛りを入れるとさらに半分ぐらいになる。
両側探索はややコードは長くなるが、
図形的な知識を使わなくて言い分、いろいろと実装は楽である。

私の実装では、出来上がった図形が凸多角形かどうかまともに調べていないが、
凸多角形が出来たほうが明らかに大きいだろうから無視している。
何も根拠は無いが…。

問題H

BNFみたいなのが与えられるので、
それの言語のうち、特定の長さの、辞書順最初の文字列を答えるという問題。
各非終端記号に対して、ある長さの辞書順最初の文字列を
キャッシュして計算してやればいいはず。
右辺に非終端記号が2つ以上有った場合、
振り分けの数がとんでもないことになるので、
最初に2つ以上出てこないように変形してやる必要がある。
非終端記号だけといわず、全ての文字を逐一ぶちぶちきってやると楽だ。
これで計算量は特に問題にならないので、あとは実装するだけ。
実装もそこまで大変ではないはず…。

問題I

グラフの k-th shortest path を求める問題。
長さが同率の場合、パスの辞書順で順位をつける。
これは難しいとは思うが、
例年と違って、明らかに捨て問と判断するのは厄介かもしれない。
解法は良く分かりません。

- - - -

全体を通して振り返ってみると、やはり探索が多いなぁという印象です。
Eはどこもサブミットすらなかったですが、
そこまで難しくも面倒でも無いと思います。
難易度は、解いてみた感じだと、
A,D