AIで解説 AtCoder攻略　DP – 経理のAI仕訳帳

DPページの位置づけ

項目	内容
必修度	重要
学習目安	標準〜発展
前提	配列・累積値
対象問題	254問（推定値あり254問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	6
標準	0〜799	46
標準〜発展	800〜1199	31
発展	1200以上	171
未算出	—	0

過去の計算結果を状態として保存し、重複計算を避けます。状態の定義と遷移を日本語で説明できることが出発点です。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

DPの見分け方

同じ部分問題が何度も現れる
最後の選択から直前の状態が決まる
桁や添字を一つずつ処理できる

DPの実装前チェック

dpの添字が何を表すか書く
初期値と遷移順を決める
空列や障害物などの境界を確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC214 C Distribution（公式解説）を解きます。各頂点へ到着する最短時刻を、隣の頂点から来る場合と最初から持っている時刻の小さい方で更新します。円環なので2周分を走査します。

N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

answer = T[:]
for _ in range(2):
    for i in range(N):
        nxt = (i + 1) % N
        answer[nxt] = min(answer[nxt], answer[i] + S[i])

for value in answer:
    print(value)

全探索で経路を列挙すると指数的に増えますが、状態を到着時刻1つにまとめてO(N)で更新できます。

DPの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC410 A G1	公式解説	公式Editorialの方針を g1 game dp として整理する。	-992
ABC428 A Grandma’s Footsteps	公式解説	公式Editorialの方針を grandma steps dp として整理する。	-744
ABC159 A The Number of Even Pairs	公式解説	和が偶数になるのは偶数同士または奇数同士だけなので、各グループから2個選ぶ組合せを足す。	-612
ABC427 B Sum of Digits Sequence	公式解説	公式Editorialの方針を digit sum sequence dp として整理する。	-404
ABC421 B Fibonacci Reversed	公式解説	公式Editorialの方針を reverse fibonacci dp として整理する。	-391

次に解く

問題	公式解説	出題意図	difficulty
ABC188 C ABC Tournament	公式解説	Simulate each tournament round and find the index of the weaker finalist.	-83
ABC435 C Domino	公式解説	公式Editorialの方針を domino dp として整理する。	11
ABC229 C Cheese	公式解説	価値の高いチーズから重量上限まで取り、最後は必要量だけ切り取る分数ナップサックを行う。	45
ABC431 C Robot Factory	公式解説	公式Editorialの方針を robot factory dp として整理する。	63
ABC391 C Pigeonhole Query	公式解説	Maintain each pigeon position and nest occupancies; update the number of overcrowded nests after moves.	141

挑戦問題

問題	公式解説	出題意図	difficulty
ABC456 C Not Adjacent	公式解説	Count arrangements with no adjacent selected positions.	183
ABC209 C Not Equal	公式解説	Sort C and multiply the number of available choices C_i−i for each position.	264
ABC424 C New Skill Acquired	公式解説	公式Editorialの方針を new skill subset dp として整理する。	274
ABC416 C Concat (X-th)	公式解説	公式Editorialの方針を concatenation kth として整理する。	282
ABC214 C Distribution	公式解説	円環上の次駅への到着時刻を、前駅からの遷移で2周分緩和して最小値を得る。	309