DP
解法1：dp 考え方 回答例 解法1：dp考え方Editorial - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)アライグマ「E問題はDPなのだ！ 分子のところだけ見ると、コンテストに参加するたびに、新分子＝パフォ＋旧分子×0.9になるのだ。残りはkだ…
dp 考え方 回答例 dp考え方操作が終わる方から決まるので，$N$から小さい順に考える． $\mathrm{dp}[i]=i$が出たあとでもらえる給料の期待値． $\mathrm{dp}[N]=A[N]$ $\displaystyle \mathrm{dp}[i] = A[i] + \sum_{j=i+1}^{N}\mathrm{dp} [j] \times \frac…
解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i品目を食べて状態がj(0:お腹を壊していない/1:壊している)のときの食べた料理の美味しさの総和の最大値回答例 N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] dp = [[0]*2…
解法1：DP 考え方 回答例 解法1：DP考え方dp[i][j] = i個目まで決めて，capslockON(j=1), OFF(j=0)のときの最小値回答例 X, Y, Z = map(int, input().split()) S = input() dp = [[0]*2 for _ in range(len(S) + 1)] dp[0][1] = 1 << 60 for i in range(len(…
解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方$f(n)=$1から初めて最終的にピッタリ$n$になる確率． $n=1$：$f(1)=1$ $n\neq 1$：$\displaystyle f(n) = \frac{1}{6} \sum_{k} f(n/\!/k)$（$(n\% k =0$かつ$k \in \{1,2,\ldots,6\})$） $n\neq 1$…
解法1：DP 考え方 回答例 解法2：再帰 考え方 回答例 解法1：DP考え方 後退解析をする（先手の勝ち負けが確定している最終状態から，逆に考えていく）． modの逆数：modの逆数 - 競プロはじめました youtu.be 回答例dp[i][j][k] = 先手がiにいて, 後手がjに…
解法1：メモ化再帰 考え方 回答例 解法1：メモ化再帰考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，再帰的に計算できる． 回答例 import sys sys.setrecursionlimit(10 ** 6) from functools import lru_cache N, P = map(int, input().s…
考え方 回答例 考え方dp[i][j][k] = i個目までみてj個和をとったときのk (mod D)の最大値．回答例dのループ範囲に注意． N, K, D = map(int, input().split()) A = list(map(int, input().split())) dp = [[[-1] * D for _ in range(K + 1)] for _ in range(…
考え方 回答例 考え方modの逆数（modの逆数 - 競プロはじめました）さえわかれば，普通のDP．回答例dはゴールまでの距離． nxt(次の位置) = move(今いる位置，出目) dp[i回目に][位置jにいる] 確率． N, M, K = map(int, input().split()) mod = 998244353 i…
考え方 回答例 再帰関数 DP的 考え方残り$n$ターンのときの期待値を$f(n)$とすると，\begin{aligned} f(1) &= \sum_{i = 1}^{6} i \times \frac{1}{6} \\ f(n) &= \sum_{i = 1}^{6} \max\Bigl(i, f(n - 1) \Bigr) \times \frac{1}{6} \end{aligned}回答例再…
考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…
考え方 回答例 考え方dp[i][j] = iコ目まですべてを使ってjにできる方法（HとTの文字列）．i + 1に遷移できるためには，dp[i][]が$i$コの文字列からなる必要がある．回答例初期化ではダミーの文字$X$を入れることで，遷移できるものを区別した． N, S = map(…
考え方 回答例 考え方「$\mathrm{dp}[n] = n$個から開始したときの答え（先手が取れる最大数）」とすると，（$A_{1} = 1$よりすべての石を取り尽くすことでゲームが終了するので）後手が取る石の個数は$n - \mathrm{dp}[n]$となる． $n$個ある状態で，はじめ…
考え方 回答例 考え方dp[i][j]=$i$コ目まで決めて，$j$コ選んだ場合の最大値．回答例 N, M = map(int, input().split()) A = list(map(int, input().split())) dp = [[-1<<60] * (M + 1) for _ in range(N + 1)] dp[0][0] = 0 for i in range(N): for j in r…
考え方 回答例 考え方dpを使うことはわかる．ただし，（座標範囲がデカ過ぎるため）座標をindexにしたdp[x][y]は使えない．「3通りの移動の仕方を何回ずつ選んだか」が「最終的な座標」と1対1対応するので，これをindexとして使えばよい．回答例次がキレイ S…
解法1 考え方 回答例 解法2：BFS 考え方 回答例 解法1考え方頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる． 求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．回答例 N, M = map(int, input().…
考え方 回答例 考え方DPで前から決めていけば良いことはわかる．DPを更新するためには， 前から何番目まで決めたか すでに使った文字の集合 最後に選んだ文字の種類 がわかれば良い（dp[i][j][k]で表す）．使った文字の集合はbitで管理できる．【更新ルール…
考え方 回答例（配るDP & いもす法） 考え方配るDPなら区間への遷移．貰うDPなら区間への遷移．よって，よくある累積和を取りながらのDP． 【類題】 EDPC - M - Candies - 競プロはじめました ABC249E - RLE - 競プロはじめました 回答例（配るDP & いもす法…
解法1 考え方（貰うDP） 回答例（貰うDP） 考え方（配るDP） 回答例（配るDP） 解法2 考え方（貰うDP） 回答例（貰うDP） 解法1考え方（貰うDP）「dp[i] = $i$までの全てに餌をあげる方法を決めたときの最小の合計コスト」とすると，「$i$と$i + 1$に餌をあ…
解法1：鳩の巣原理＋bit全探索 考え方 回答例 解法2：DP＋経路復元 考え方 回答例 解法1：鳩の巣原理＋bit全探索考え方200で割った余りは200通りだけであるから，201個調べれば必ず同じものがある．$2^{N} > 200$となる最小の$N$は$8$なので，先頭の$8$個を…
考え方 回答例 参考 考え方 「dp[i][j] = $i$番目まで選んだときに和が$j$となる場合の数」としたくなる 不等式の両辺が動くと困るので，片方を固定したい．和については↑のようにdpで考えたいので，maxを固定したい． $\{(A_{i}, B_{i})\}_{i}$を$A_{i}$に…
EDPC - M - Candies - 競プロはじめましたの類題だが，今回の方がはるかに難しい．．． 配るDP & いもす法 貰うDP & 累積和 配るDP & いもす法文字数が少ない問題に帰着させられそうなので，dpを考える．「dp[i][j]=圧縮前の長さが$i$・圧縮後の長さが$j$の…
ある区間から遷移する問題． 貰うDPなら累積和（ある区間からの遷移），配るDPならいもす法（ある区間への遷移）となる．個人的には，いもす法の方がわかりやすい． 方法1 (貰うDP & 累積和) 考え方 回答例 方法2 (配るDP & いもす法) 考え方 回答例 背景 方…
考え方 回答例 考え方左から見ていくと，コの字の辺を追加していく形になっている（初期状態のみ特殊）．各ステップで3辺のうちどれを切るかをきめるとdpで解ける．dp[i][j][k]を， 左から$i$番目まで決まっていて， $j$本の辺を取り除かれていて， 上と下が…
考え方（包除原理） 回答例 考え方（包除原理）dpで解いたが，組み合わせ＋包除原理でも解けそうと思いつつ実装できなかったのでメモ． Editorial - UNIQUE VISION Programming Contest 2022（AtCoder Beginner Contest 248）$\sum_{i=1}^{N} A_{i} = x$の場…
考え方 回答例 考え方まずは，$X$を偶数回云々を抜きにした，一段簡単な問題を考える．再帰で全ての道順を試して，$K$個の辺を通ったらreturnする方針では間に合わない（$\pmod{998244353}$を要求されていることからもわかるように）．そこで「ある頂点に行…
考え方 回答例 考え方「入力の全てのパターンに対応する到達地点を調べる」方法だと$2^{100} = (1024)^{10} \sim 10^{30}$で間に合わない．到達地点の候補は，$1\leq X \leq 10,000$の範囲なので，$10^{30}$よりずっと小さい．そこで，到達地点としてあり得…
$\mathrm{dp}$で考える場合， $\mathrm{dp}$を中心に考えると，「貰うDP + 累積和」になり， 累積和（階差）を中心に考えると，「配るDP + 階差 (いもす法)」になる ということだと思う． 貰うDP + 累積和 考え方 回答例 配るDP + 階差 (いもす法?) 考え方 …
考え方 平均値 中央値 二分探索＋DP 回答例 考え方公式解説がわかりやすい．二分探索＋DP． Editorial - AtCoder Beginner Contest 236平均値\begin{aligned} & \frac{1}{n} \sum_{i=1}^{n} x_{i} \geq K \\ & \Leftrightarrow \sum_{i=1}^{n} (x_{i} -K) \g…
考え方 回答例 考え方こうやって遷移できるんですね．なるほどぉ〜．長さ$j$の文字列を作るとき，新しい文字を$k$個使うとすると， 新しい文字（$i+1$番目の文字）を入れる場所を，$j$個の候補から$k$個選べば， あとは，$i$種類の文字で長さ$j-k$の文字列を…
