TopCoder部【SRM 440】

EASY　163.28/250.00　→　Passed

インクレディブルマシーンきたこれええええ！！


――というわけで、まさかのインクレ物理の問題でした。
問題の詳細はめんどくさいので書きません。


解法は、2次方程式を解きながら二分探索しました。

MEDIUM　231.16/500.00　→　Passed

N×M(N,M<=50)サイズのフィールド（空白、壁から成る。どこかの空白の上にはゴールが置かれている。ゴールはフィールド上にただ一つ存在。任意の異なる空白2箇所を選んだとき、常にそれら2点を結ぶルートがちょうど1つだけ存在）が与えられる。
主人公を任意の空白およびゴールからスタートさせることができ、その後の移動は、ゴールするまで、上下左右4方向のうち壁がない方向にランダムに一歩進むことを繰り返す。
主人公がゴールするのにかかる歩数の期待値を、各マスからスタートさせたときについて求め、それらの平均を出力せよ。


という問題でした。


マスiからスタートした場合の歩数の期待値をXiとすると、各マスに関して1次方程式が1本立ちます（たとえば、X1=0.5*X2+0.5*X3+1 など）。
フィールド上の空白の数（ゴールは除く）をnとすると、未知数n個の連立1次方程式が合計n本立ちます。ちなみに解はただ1通りに定まります。


で、これをガウスの消去法でも使って解きます。
nは1000ちょっとあるので間に合わなそうに見えますが、この問題の場合、「i行目にj行目のp倍を足す」という操作の大半はp=0なので、それをスキップしてやれば余裕で通ります（証明略。怪しい気もするけど通ったからどうせあってる）。疎行列って素晴らしい。




つまるところ、ライブラリをはっつけて一発な問題です。ああ持ってない自分の単独負けですね。


……とか思っていたのですが、まわりにこの方針で解いた人が誰もいませんでした。なぜに。

HARD　手をつけられるようになるのはいつの日か

CHALLANGE　+0.0　-0.0

結果

・61位
・R：1939 → 2032