世界大会

ICPC

http://icpc.baylor.edu/icpc/


ちょっとこの間まで世界大会のお手伝いに行ってきました。
ディズニーランドとかはあんまり興味なかったのですが、
世界中からスーパープログラマが集結する機会というのは
やはり貴重なので、今年もその場に立ち会えてよかったです。


会場にいる間はもうずっと自分がもう出られないことが
ひたすら残念で残念で、現役の選手がうらやましくて
たまらなかったです。ことさら、問題がやさしかったなら。
オープン参加でもいいからあの時間を共有したかった。
終わったあとにコンテスタントと感想戦をしたのですが、
やはりそれが面白かったです。
全問題の結論がでるまで検討したかった。


表彰式は今年もすごかったです。
ワルシャワ大は神といわざるを得ない。
残り時間一時間でスコアボードが凍結されていて、
表彰式の時にサブミットしてた問題が通っていたかどうか
公表されていったのですが、
ほかのチームがどんどんWAになっていく中、
ワルシャワは7→8問、
その瞬間、会場はもうスタンディングオベーションでした。


ちなみに、コンテスト期間中の一番驚いたのは
26行の最小費用流のコード。
練習セッション中の印刷物を運ぶのをやっていたのですが、
どこかのチームがとても短い min_cost_flow とかいう関数を
印刷していて、それが数えてみると26行しかない。
しかも、それも無理に詰め込んだ感じではなくて、
いたって普通のコードで、
ほんとうにこれで最小費用流が動くなら、
去年の世界大会でロシアチームに「As Usual」
とか言われたのも納得せざるを得ません。
というわけで、どなたか26行以下で
最小費用流のコードを書いてみませんか？
そして、私にこっそり教えてください。


大会期間中はコードが書けなかったので、
とりあえず、帰ってきてから8問分ほど書いてみました。
せっかくなので、問題の考察をしてみようかと思います。

http://icpc.baylor.edu/icpc/Finals/2007WorldFinalProblemSet.pdf

問題はここから参照できます。


・問題A

両親と子の三人のうち二人の血液型(ABORh)が与えられるので、
残りの一人の血液型でありうるものを列挙せよ。


血液型は冗長に数えても36通りを考慮すれば十分なので、
三人の血液型の組み合わせ36^3すべてをチェックすればよいだろう。
適当に書いたら98行になった。


・問題B

A-Zの番号の付いた荷物が港にやってくる。
荷物はやってくる順に何列かのスタックに積む。
積み終わった後に番号の若い順に荷物を回収する船が来る。
その際、スタックの下のほうにある荷物は
回収できないので、ある船が来た時、
その船が回収する荷物はすべてスタックのトップにあって欲しい。
スタックは最小で何列必要か。


問題の要求より、小さい番号の荷物の上に大きい番号の荷物を置くことは出来ない。
荷物がやってくる順に、既存のスタックの上にその荷物が置けるなら置く、
置けないなら新しいスタックを作る、
複数置ける場所があるなら、よりスタックトップが小さい番号のところに置けばよい。
置ける場所があるなら置いたほうが良い理由は、いまやってきた荷物をx,置こうとしている場所のトップをyとすると、
置いた場合のスタックトップの組は(x,*)、置かなかった場合の組は(y,x)で、前者は後者よりも完全に良いから。
複数箇所おける場合に小さい番号のところに置いた方が良いのも同様に。
コードは大変簡単に書ける。


・問題G

ルーター(？)にいくつかのメッセージを細切れにしたいくつかのパケットがやってくる。
各メッセージをまとめて順番に出力するために必要なバッファの最小のサイズは？


ある番号のメッセージを出力し始めたら、そのメッセージが終わるまで
ほかのメッセージを出力できない、という仕様を
各メッセージを細切れに出力しても良いと読み違えたチームが多かったらしい。
しかし、よく考えるとそれだとバッファサイズの最小値も何も一通りしかないような気がする。
解法は、メッセージが5個しかないので、メッセージを出力する順番をすべて試せばよい。
あとは書くだけ。


・問題F

4*4の盤面に番号の付いた石と番号の付いた穴がある。
盤面を4方向に傾けて、その方向に全部の石を移動させることが出来る。
全ての石を対応する穴に落とせばゴール。
最短手数を求めよ。


ありうる盤面のパターンは多分とても少ない。
石の数は8個まであるが、石が多いとほとんど身動きが取れないし、
少ないとそもそもパターンが少ないし、一度でも盤面を傾けると
石は壁沿いにしか存在できないので、やはりもっと少ないだろう。
というわけで幅優先探索。
コードはこれまた適当に書いたら95行ぐらいになった。


・問題C

二次元平面状にジグザグの経路が与えられる。
これをある角度傾けた時にすべて上り坂になっているようにしたい。
元の経路を時計回りに何度回転させればそうなるか？
あるいははじめからそうなっているか？
それともどう回転させても無理か？


各線分について回転させて上りになるか、下りになるか、切り替わる角度を0から2πの範囲で列挙。
あとは角度を下からなめていって、上り坂の数が線分の数に等しくなることがあるかどうかを調べればよい。
θ=0の場合は明らかに引っ掛け、常にOK。


・問題D

格子点上のポリゴンが与えられる。
そのポリゴンと相似で、格子点上にのる最小のポリゴンを求め、
それの1倍、2倍、...、M倍の大きさのポリゴンの内部の格子点の数の
和を求めよ。答えは64ビット符号付整数に収まる。
1000角形まで、Mは100万以下。


ピックの定理を使えばよいらしい。
格子点上の図形は、
(面積)=(内部の格子点の数)+(辺上の格子点の数)/2-1
が成り立つ。
1倍の図形について、面積sと辺上の格子点の数aを求めると
答えは Σ(i=1..m) s*i*i-a*i/2+1 となり、これは展開すると
s*m*(m+1)*(2*m+1)/6-a*m*(m+1)/4+m
になる…のだが！
割る6とか引き算とかが出てくるので、これは答えが64ビット符号付整数に収まったとしても
計算途中の値も収まるとは限らない。
というわけで、ここでは多少時間がかかっても一つずつ級数を計算するのがベター。
100万だから計算が間に合ってしまうのがなんとも。
日本チームはここに引っかかっていた可能性が高いということ。
一つずつの計算なら、引き算は入るけど、
途中の値が求める値の二倍を越えないので、
unsigned long long で計算すれば十分かと思われる。
(あるいはJava使ってるチームだったらBigIntegerで何も考えずに書けるのだろうなあ)


さて、ここからが本番。


・問題I

多分2チームしか通してない問題。


筒状のタンクが何本かあり、
隣り合うタンクはパイプで繋がれている。
それぞれのタンクの高さと、パイプの高さが与えられる。
パイプの高さは左から"単調増加"。
一番左のタンクからゆっくりと、
あふれるまで水を注ぐ。
タンクにどれぐらい水が入るか？
物理法則はだいたい現実に即する。


たぶんあってる解法：
タンクをつなぐパイプの両端が水没しているなら、
両端の水圧はつりあっている。
一番左のタンクは最終的には水が満タンになるので、
左端のタンクと一つ右のタンクを繋ぐパイプにかかる水圧は簡単に求まる。
この水圧になるように、一つ右のタンクに入っている水の量を推定する。
一つ右のタンクの水の量が分かれば、同様にもう一つ右のタンクの水量を推定し、
同様にさらにもう一つ右の…と計算していき、すべてのタンクの水量を計算する。
その際に、前のタンクとつながっているパイプにかかる水圧および、
現在のタンクを含む空間が「閉鎖」されたときの圧力を持ち回り、
これを用いて計算する。


まず最初に、一番左から一つ右のタンクについては、
前のタンクとつながっているパイプの水圧P1=1+0.097*(水面からパイプまでの高さ)、
閉鎖された時の圧力P2=1。


各イテレーションは3パターンに場合わけされる。

┌┐
││  ← ③
│├  ← ②
││  ← ①
┤│
└┘

① 前のパイプから次のパイプの高さの間で水面がつりあうとき
② 次のパイプまで水面が達するが、次のタンクに注ぎ込まれた水の高さがパイプにまで到達しないとき
③ さらに水面が上でつりあうとき


①〜③のいずれになるかは、それぞれ境界まで水を注いだ時の水圧を計算すれば分かる。
①と②の境界まで注いだ時、次以降のタンクの体積の合計をVとし、
現在のタンクの高さをH、前との連結部の高さをh1、次との連結部の高さをh2とすれば、
前との連結部にかかる水圧は、
(P2*(V+H-h1)/(V+H-h2))+0.097*(h2-h1)
②と③の境界まで注いだ時は、
(P2*(V+H-h1)/(V+H-h2-h2))+0.097*(h2-h1)
これとP1を比較し、①〜③に場合わけする。


①の場合、水面の高さをxとすると、
P1=(P2*(V+H-h1)/(V+H-x))+0.097*(x-h1)
二次方程式を解けばxは求まる。
水は次のタンクに注ぎ込まない。
よってイテレーションはbreakして、計算は終了。


②の場合、次のタンクに注ぎ込む水の高さをxとすると、
P1=(P2*(V+H-h1)/(V+H-h2-x))+0.097*(h2-h1)
一次方程式を解けばxは求まる。
水は次のタンクに注ぎ込むが、その量はxと分かっている。
さらに次のタンクには注ぎ込まない。
よってイテレーションはbreakし、計算は終了。


③の場合、水面の高さをxとすると、
P'=(P2*(V+H-h1)/(V+H-h2-h2))+0.097*(h2-h1) として、
P1=(P'*(H-h2)/(H-x))+0.097*(x-h1)
二次方程式を解けばxは求まる。
水は次のタンクに流れ込み、計算する必要がある。
P2←P'
P1←(P'*(H-h2)/(H-x))+0.097*(x-h2)
と更新し、イテレーションを継続。


この繰り返しにより全てのタンクの水量が求まるので、答えが出る。
最後のタンクにはさらに次に高さ0のタンクがあって、
高さMAXのパイプでつながっているとすれば最後のタンクは必ず①になってくれるので、
例外処理せずにすんで楽。
ここまで計算してしまえばコードを書くのは(多分)簡単。
でも、とても書き間違いをしそう。
しかもサンプルインプットでは①のケースしか検証できない。
通すのは大変そう。


・問題E

これも2チームしか通していない問題。


コンベア上を荷物が流れているので、
ちょうど荷物にぶつかるように歩いていくという問題？
あんまり詳しく問題の仕様を聞いていないので、
解法は良く分からない。
解いたチームの話によると、バイナリサーチ。


ここから誰も解いていない問題


・問題H

三次元空間上に三角形がいくつか(1000個、頂点は300個)ある。
Z軸方向上方から三角形を見下ろした時、可視部分にペンキを塗らなければならない(？)。
可視部分の"実際の"面積を求めよ。小数点以下2桁。
座標値は100を越えない自然数。
三角形は互いに触れないし、共通部分も持たない。


要求精度が小数点二桁ながら、
三角形が1000個あり、一辺が100の正三角形を
斜めに剣山みたいにたてて置くと全てが見えて、
その場合答えが1000万のオーダまでいくので、
要求精度としては9桁必要になる。
メッシュなどはちょっと不可能ではないだろうか。


一つ思いついた解法としては、スキャンラインによるもの。
三角形が共通部分を持たないので、
上から見た図形としては三角形が重なりあったものになる。
よって、x-y平面を線分の端点と交点のy座標で帯状にスライスすると、
そこに入っている図形は台形のみになる。
あとはその中央辺りで空間を切断して、三角形の入っている区間とその三角形の傾きが分かればよい。
…のだが、ナイーブに実装するとO(n^3)(n=三角形の数)になってしまうような気がする。
うまく実装するとO(n^2)になりそうではあるが、
ちょっと私は書いてる途中で良く分からなくなってしまった。


・問題J

無向グラフ(ノード数50、エッジ数1000)があり、
点1にスパイがいて、点0に向かおうとしている。
点0にいかれては困るので、エッジをなるべく少ない数爆破して、
スパイが点0にいけないようにしたい。
最小本数を求めよ。


同じノードの対に複数エッジがあるのは、一部爆破するのは無意味なので、
単にエッジの数で重み付きグラフにしてしまえばよいとして。
これは単なる最小カットではない。というのも、

１
├┬┐
２３４
├┴┘
０

のようなグラフがあったとき、これの答えが2になるというサンプルインプットがある。
これはスパイが234のいずれかに移動した瞬間にその両端を爆破してしまえばOKということで、
スタート地点からの最小カットを求める意味が無いということ。
また、後の議論により、エッジを時間差で爆破するのが適切であるというケースも見つかった。
これにより、全点からの最小カットを求めて、1から0へのパス中の最小の最小カットが
最大になるようなものを求める、というものでもない。
時間差で破壊するものを考慮しなければならなくなって、
ちょっともうお手上げで、どうして良いのかわからない。
探索がありうるのかとも考えたが、
完全グラフを考えると、ノードの次数が49まで行くので、
あるノードからどのエッジの組を破壊するかの組み合わせだけで2^49通りあるので、
とても無理だという結論に至った。
というわけで、この問題は完全にお手上げ。


・総括

6問目と7問目の境が大きい。
その中で8問通したワルシャワ大学はやはりすごいと思った。
問題EとJは後でちゃんと考えたい。