読者です 読者をやめる 読者になる 読者になる

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以上にすることができる

みたいに判定する。解いてない。セグ木の勉強しないと

D

場合分け

場合分けの解き方とか

E

凸包