SRM 626 Div2
SRM 626 Div2
Easy
数列aが与えられる。aの部分列の要素の和をすべて合計するといくつになるか
累積和を使った。
Med
aとb、それぞれの数字までが書いてあるサイコロがある。aを持っているアリスが勝つための期待値でいいのかな
勝ったときの数字と勝った回数を求める
Hard
N個の頂点とE個の非負の辺からなるグラフがある。charge回まで特別な力を使い、コストを回復できる。1から出発してNまで行く最小コスト。Nは通りすぎても構わない
ダイクストラ法 or ベルマンフォード。aからbへの経路が複数ある可能性があるので隣接リストを使う。拡張ダイクストラを実装する。
dp[i][j] := 残りi回チャージできるときのjへの最小コスト
初めてHardを通した
Codeforces #262 Div2
B
a,b,cが与えられる
x = b * s(x)^a + c
を満たすxを求める
s(x) := xの各桁の数字の合計
xが109未満なので全探索は無理。s(x)の最大値はxの最大値が999999999なので81となる。1 <= s(x) <= 81を満たす。そしたら81までループを回して、上記の式を満たすものを探す。解法をよんですごく面白い問題だと思った。こう言う問題を解きたい
C
n個の花がある。m日間、連続するw個の花に対して水をやる。水をやった花は1だけ高くなる。一番小さい花を最大化する
にぶたんする。RMQつかったりする
C(d) := すべての花の高さをd以上にすることができる
みたいに判定する。解いてない。セグ木の勉強しないと