問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…

問題 問題概要 N頂点M辺の無向グラフと各辺の距離が与えられる. また各頂点に対してコストc[i]が与えられる. 各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ. 2 <= N <= 2105, 1 <= M <= 2*105 解法 Dijkstraで各頂点とそのコストを初期位置としてキ…

問題 問題概要 文字列Sが与えられる. '()', '((()))', '()(())'などの'('と')'が対応している文字列を有効な文字列とする. ')('はダメ. また,'?'はどちらにも変換できる. l ,r (1<=l < r<=|S|)でS[l..r]が有効な文字列であるような組の数を求めよ. 1 <= |S| …