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