A一完のひどい出来。
B. Tree Array
制約から、三乗の解法を考える。
全てのi, j (i < j)について、j が iより先に使われる確率を考えれば良い。（主客転倒って言うのかな？）
そうすると、iとjを結ぶpathにいくつか余計なものがくっついているような図を考えることになる。（木の直径を図示するときのやり方と同じ）
なので、iとj上のpath上の点から始まったとき、jの方に先にたどりつく確率を調べればOK。
……と、ここまではできたが、この確率が2ベキの和になると早合点してしまった。それでサンプルが合ったこともあり、修正できず終了。
実際は、iから距離p、jから距離qの点からスタートしたなら、p回iの方へ進む前に、q回jの方へ進む確率を計算すれば良いので、p*qのマスで端から端への最短で向かう経路数を考えるのと似たようになる。これはDPで求めることができる。
これを前計算すればOK。
多分、もう少し時間が残っていて、落ち着いて考えていたらちゃんとACできたと思う。先にCを考えたりしたせいもあり、Bの正しい方針に至ったときに時間が残っていなかったのが敗因か。
0 件のコメント:
コメントを投稿