SRM 462
やっぱりSRMは11:00なんていう早朝にやるもんじゃないねｗ
250
1,"11"で0返してて再提出orz
落とし穴いっぱいで撃墜しまくりだーと思ったら自分のも落ちたorzorz
1,"110"とかどう見ても解あるじゃん…
Failed System Test
450
全てのやつを独立に考えて良くて、i回スワップ後にもとの位置にいる確率をp_iとすると、
p_{i+1}=hoge*p+piyo*(1-p)
みたいに書けて、これ計算してから全部まとめるだけ
O(log S + n)まではいける
が、コンビネーションnCrでr<0の場合を考慮してなくて死んだorz
Failed System Test
1000
最悪ケース最小化→二分探索！！！
というわけで二分探索で解けないか考えたところ、
minD[v]=max_u{辺(v,u)を削除したときのv-t間最短距離}
とし、解の上限をubとすると、
(s-v間最短距離)+minD[v]<=ub であるような点だけを使ってtに到達できるかを判定すれば良い
…のはずだが何故か落ちたorz
他の人みんなベルマンフォード的なことをしてたので解法違うのかなーと思ったが、ただバグっていただけだったorz
なぜかダイクストラの初期化する場所をミスり、さらに終点について上の判定をしていなかったorzorz
Failed System Test
