atcoder.jp N!の総和系なので、確率・期待値でやるべき問題。 まずは1回のコストの期待値を考える。答えはこれにN!をかけてやればよい。すると、ブロックj を取り除いたときに、ブロックiが連結である確率をP(i, j)としたとき、1回のコストの期待値はΣa[i] *…

atcoder.jp xを有理数(つまり、整数とは限らない)として、x(x+1)(x+2)...とみなすと、剰余代数系ではある整数yが存在して y(y+1)(y+2)... を計算するのとおなじになる。これが最重要。 x(x+d)(x+2d)... = d^n * y(y +1) ... (y+n-1) (ただしy=x*d^(-1) mod 1…

atcoder.jp なんとかこういう問題の本質がわかった気がする。 まず状態遷移を考えると、今までにAがi回勝って、Bがj回勝った、という状態をS(i, j) とおく。これに引き分けがk回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態…

atcoder.jp トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。 問題文で追加されているという辺は必ず子へのショートカットとな…

atcoder.jp 日経のコンテスト出ましたがこれが通せなかったため解法をマスターしておく。この手の問題は得意だったはずなのに通せなかったのは少し反省。 「辺をいくつか除いたときの連結成分ごとのほにゃらら」は逆から考えてUnion Findで処理する。ここま…