cafelier@SRM

SRM425 Div1

SRM | 22:31 |

SRM425 の成績・ソース (要ログイン) : WA/AC/-- : ひどいポカをした

250 開く

• 『ロボットが4方向ランダムウォークします。n歩。4方向それぞれ進む確率が与えられる。同じマスを2度踏まない確率は？』

• 同じマスを踏まないパスを全探索して個数数えるだけだろー
  • n ≦ 14 だと、4^n = 2^28 = 3億弱 の全探索は時間マズいかな？
  • 最初の一歩は対称だから上に進む場合だけに固定して考えればよくて、2^26 だと通るとかいうアレではないか
  • 実装。サンプル通った。submit！

• (※ Challenge されて落ちました）

500 開く

• 『5×5のチェス盤に5個以下の駒が配置されてる。全部の駒が連結になるように動かすときのマンハッタン距離での動かし距離総和を最小化』

• 状態空間は…25C5通り。少ない。幅優先で探索すれば終わる。
• 実装
  • 盤面の状態は25bitで表せるのでint一個で。
  • 連結判定は毎盤面 Union-Find を走らせて確かめることにした。最近 Union-Find をインラインで書くのが趣味
• できた。submit

1000 開く

• 『各枝の壊れる確率が設定されてる無向完全グラフがあります。壊れてちょうど全域木が残る確率は？』
  • 頂点数は16以下

• 分割統治でダメかな。"頂点 1..8 で全域木が残る確率" × "頂点 9..16 で spanning tree が残る確率" × "1..8 --- 9..16 の辺が一本だけ残る確率" で再帰で解けるような気がする…？ 2^16回くらいの計算
  • "辺が一本だけ残る確率"の実装に意外とてまどる。100%壊れる辺とか0%壊れる辺のあたりでゼロ除算の危険があってうざいなー
  • 実装完了した
  • サンプル通らない

• よく考えたら、1..16 が全域木だからといって、その一部の 1..8 が全域木とは限りませんね、はい。全部バラバラで"1..8 --- 9..16" から8本生き残って全体としては繋がるケースとか、いくらでもある
• これはダメだ
• 全然思いつかない

撃墜タイム

• 開始 1 分で自分の 250 が撃墜されて泣いた
  • 進む確率違うんだから、4方向対称なわけないですよねー。
  • そもそも後ろに戻るパスは有り得ないんだから全部数えても 3^14 で余裕です

感想

• 250は250なんだからそんな変な工夫がいるはずないのにねえ。1000まだわかってない。あとで考える。