7K12 blog

猫でも分かるアルゴリズム解説

DP

ABC195 E - Lucky 7 Battle

https://atcoder.jp/contests/abc195/submissions/21508217 初期値は dp[N][0]=1 繰り返しは repr(i, N - 1, -1) rep(j, 0, 7) 更新は if (X[i] == 'T') dp[i][j] = dp[i + 1][j] || dp[i + 1][(j + CtoL(S[i]) * NT_NyaaMod::Pow(10, N - 1 - i, 7)) % 7]; …

ARC043 B - 難易度

https://atcoder.jp/contests/arc043/submissions/20924727 初期値は dp[0][0] = ... = dp[0][N-3] = 1 繰り返しは each(i, e, D) rep(j, 1, 4) 漸化式は dp[j].Add(i, dp[j - 1].Sum(0, distance(D.begin(), upper_bound(all(D), e / 2)))) 最終目標は Sum(…

ABC036 D - 塗り絵

https://atcoder.jp/contests/abc036/submissions/20748614 初期値はall(dp) = 1; 繰り返しは DFS 漸化式は dp[now][B] *= dp[next][W], dp[now][W] *= dp[next][B] + dp[next][W]; 最終目標は dp[0][B] + dp[0][W]; 葉からDPを更新することで根が答えになる…

ABC142 E - Get Everything

https://atcoder.jp/contests/abc142/submissions/11902212 初期値はdp[0]=0 繰り返しは rep(i, 0, M) rep(j, 0, Pow2(N)) 遷移は dp[next] = min(dp[next], dp[j] + key[i].a); 出力は dp[Pow2(N) - 1]; 制約からbitDPと分かる。 各鍵key[i]と宝箱の空き状…

GigaCode 2019 E - 車の乗り継ぎ

https://atcoder.jp/contests/gigacode-2019/submissions/13239335 これでdif12Kなのか。天才しかいない。 初期値は all(dp)=ldbl_max, dp[0]=0 繰り返しは rep(i, 1, N+2) rep(j, 0, i) 更新は dp[i] = min(dp[i], dp[j] + (ld)(car[i].x - car[j].x) / (ld…

パ研合宿2019 D - パ研軍旗

https://atcoder.jp/contests/pakencamp-2019-day3/submissions/13169571 DP初期値は0 DP繰り返しはrep(i, 0, N) rep(0, j, 5) DP更新はDP[i][R] = min(DP[i-1][B], DP[i-1][W]) + count[i][R]など DP出力はmin({DP[N-1][R], DP[N-1][B], DP[N-1][W]}) 入力…

Educational DP Contest M - Candies

https://atcoder.jp/contests/dp/submissions/10545854 子供たちが飴を分け合うと言うと重複組み合わせっぽく見えるが、重複組み合わせだとDPが書きづらいので子供i-1から子供iに遷移するとき飴jがどうなるかというDPで実装する。このとき、K個の飴を配ると…