425.1

250

ランダムに上下左右に移動するロボットが、同じマスを通らずにN歩移動できる確率を求めよ、という問題。

上下左右のうち、まだ到達していない場所について探索を続けるDFSを回せば良い。全部のパスを計算してから同じマスを通っていないか確認するのはダメみたい。

500

5x5のボードの中に高々5個の石が置いてある。このとき、すべての石がまとまるのに必要な最小移動個数を答えよ、という問題。

それぞれの石について、どこに移動させるかを決めるのは25P5通りで、これらの移動距離は簡単に求まる。後はこれらが一まとまりになっているかどうかを検証すれば良い。

1000

N点からなる完全グラフが与えられる。これらの辺のそれぞれをある確率で除去するとき、残ったグラフが全点木になる確率を求めよ、という問題。

プリムのアルゴリズムみたく全点木を組みつつ、DPすれば良さそう。複数回同じ状態がカウントされるのを避けるために、直前の状態として可能なものが何通りあるかを計算すれば、カウント回数が分かる。これはある辺を除去したときに、残りの木をなしていれば良いので、リーフになっているノードからの辺を除去してみれば良い。つまりリーフの数。後は下から状態を組む必要があるのだけれど、どうやれば下からになるんだろうか？そもそもこの方針があっているかどうかも不明。

答えはあっているっぽいけど、O(3^N*N^3)なので終わらないっぽい。JavaのHashtableが重いとかそういう次元でもなさそう。メモリリミットにも抵触する可能性あり。