ICPC国内予選2007

国内予選

去る7月6日に国内予選があったのですが、ありがたいことに今年もMakegumiのコーチをやらせていただいておりました。
コーチとして戦いを見守るのももう公式戦だけでももう4度目になりますので、気分的には慣れたものですが、やはりもどかしいものです。まあ、もう私なんか鈍りきってしまって、何も言えることはないのですが。
結果は http://www.logos.ic.i.u-tokyo.ac.jp/~chik/icpc2007/jp/domestic/result.html こちらから見れるとおり、Makegumiは2位でした。1位のUnknownの皆さんはおめでとうございました。去年のことを考えると若干残念ではありますが、別にどこが勝ってもおかしくはない状況だったし、時間差勝負で、しかもここまで競っているとなると、改めて勝負は水物であるなあと思う次第であります。
問題は今年は易化したと思います。きっと今年は去年の1.5倍ほどに予選突破チームを増やすことになったからなのだとは思うのですが、ちょっとこれはバランスが悪かったと思います。それに加えて作業色が強くなったのも個人的にはあまり面白くない。どっちかというとMakegumiは難しい問題をぽこっと通すイメージがあるので、ちょっとその辺でもつらかったと思います。

考察

ときに、私も裏でコーチとして観戦・応援しながら問題をぼちぼち解いていたので、この辺で問題の考察でもしてみようと思います。問題は現時点では http://icpc.logos.ic.i.u-tokyo.ac.jp/icpc2007/common/guest_top_en.php ここから見られるようですね。

問題A

ついにリハーサルレベルまで落ちた問題A。なめながら和と最大、最小値を調べるのがお手ごろでリーズナブルだろうけど、ソートしてもとくにペナルティーはなさそうであるなあ。

問題B

やけにややこしいけど、PCの番号が何も意味を持たないことに気づけば、問題は意外なほど単純になる。時刻も昇順に入ってくるし。

問題C

問題の記述がかなりわかりにくい。Inputのところに問題の続きを書くのはどうかと。ピースのカットが行われると、元のピースはなくなってまったく新しいピースが2つ出現するという理解でよいのだろうか。各カットはおそらくO(logn)でできるのだけど、問題のサイズが小さいので、O(n)でも、O(nlogn)でもなんでもよさそうな感じ。

問題D

どう見ても最短路ですね。

問題E

は、おいといて。

問題F

多分、国語の問題。私は30分ぐらい問題を読んだ挙句に、結局問題を正しく把握できずに時間内にバグが取れなかったのでありました。要は書いてあるとおりに実装しろということなのですが。ちなみに、とてもHaskell向きの問題なのでHaskellでも解いてみました。よろしければ後ろのソースをご参照ください。

問題E

おそらく一番難しい問題でしょうね。方針によってコーディングの難易度は大きく変動すると思われるのでいろいろ考えてみましたが、いまいち書きたくなるほどシンプルな方法が思いつかないので保留しています。1.棒が何度回転できるかを二分探索で求めて、それを繰り返す。つまり、ある扇形が与えられたときに、それが多角形に包含されるかが求められればそれだけで解けるのですが、これが微妙に簡単ではない。どうしたものか。2.支点から回転させて棒が突っかかる可能性のある角度をすべて求めて、そのminだけ棒を回転させ続ける。min=0なら終了。これは図形の内部と外部を判別するスマートな方法が思いつかない。3.精度が結構粗くてもよいので、長さ*角度<10^-3になるような角度ずつ棒を少しずつ回転させていく。長さは500以下だから、10^-6ぐらいずつで回転させると、トータルで最大20πほど回転させればよいので、気長に待てば計算が終わるような気がする。でもまあなんというか、誤差が累積するような気がするなあ…。
とか、考えているうちに気力がなえてしまった…。

後記

やはり現役はうらやましいですね。私もあと2歳若ければ。終わったあと今年も白木屋で祝勝会をしていました。PFI密度が濃すぎたといわざるを得ない。なんでコーチの私が飲まされるの。Unknownの三人の表情は晴れやかであった。やはり勝者はそうでなくては。Makegumiは次は名前のとおりにならぬようにがんばってください。もう今年は最後なので、本当に世界大会の舞台を経験してもらいたいと思っていますよ。

おまけ

1分おきにスコアボードを取得してみたので、よろしければどうぞ。

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/guest_standings_en.php.zip

ソース

一部Haskellのソースつき。
Dはグラフライブラリを使ってみたけど、あんまりすっきりはしなかった。なんでNodeがIxじゃなくてIntなのだろう?Shortest Passがなかったときにパターンマッチで落ちるのもどうかと。Fはかなりすっきり。EqとOrdの関係がまったくないのはご愛嬌。map (show . norm . read) と書けるのは相当気持ちいい。

http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/a2.cpp
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/b2.cpp
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/c2.cpp
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/d2.cpp
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/f2.cpp
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/d2.hs
http://fxp.infoseek.ne.jp/tmp/icpc/2007_dom/f2.hs