2019-09-18から1日間の記事一覧
0. DP のはじめの一歩 ふと、人生で初めて「この問題は DP だよ」という状況に直面した方が、DP へのはじめの一歩を踏み出すのに良さそうな問題たちをまとめたくなった。 DP のはじめの一歩な問題として、どんな問題がふさわしいかについて、AtCoder Educati…
Codeforces
探索問題
応用的な探索
最適解に含まれる可能性がない要素を挙げる
最短路問題
BFS
グラフ問題
DFS
DP
文字列を値にもつDP
グラフの辺を分割する
辞書順
辞書順最小なグラフ探索
数値を表す文字列同士の比較
各kに対して
整数値のconcatを考える問題
CodeforcesCombined
CodeforcesR2600
勉強になった!!!!! 「辺番号または頂点番号が辞書順最小な最短路」を求める考え方が炸裂する感じ。 最短路として使われうる辺を列挙しておく (この考え方自体が典型) その辺をうまいこと活用しながら探索する という典型の流れになっている。 問題への…