推移性に着目する
Dilworthの定理
DAGの最小パス被覆
双対性
最大安定集合・最小点被覆・最小辺被覆
最大安定集合問題
推移性に着目する
二部グラフ
二部マッチング
マッチング
フロー
【問題集】フローのチャレンジ
【問題集】フローのステップアップ
NoviSteps4D
AtCoder
AtCoder625点
橙色diff
ABC-G
文字列
文字列検索問題
SuffixArray
N個の文字列の問題
連続部分列を扱う問題
最大スコア
最適化問題
グラフの問題として考える
Dilworth の定理から、DAG の最小パス被覆!! かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…
AtCoder
AtCoder300点
ABC-B
DFS
グラフ
グラフの頂点の次数に着目する
BFS
トーナメントなど対戦表に関する問題
灰色diff
算数と数学
算数と数学:パズル
推移性に着目する
条件の言い換え
NoviSteps4Q
想定解法が天才的に思えたとしても、愚直なグラフ探索でも解ける! 時には腕力で頑張るのも有効! 問題へのリンク 問題概要 競技プログラマ がいる。 組については、どちらが強いかが分かっている。具体的には に対して は、 より強い ということが分かって…
Codeforces
EducationalCodeforces
CodeforcesR1700
文字列
辞書順
推移性に着目する
prefixとsuffix
順列の最適化問題
解空間:O(N!)通りの選択肢
順列テク:順列は互換(swap操作)の積として表せる
そのまま覚えたいシンプル設定の中堅以上の典型問題
思わず解きたくなる興味深い良問
順列を題材とした問題
非自明な比較関数でソートする
N個の文字列の問題
探索順序を工夫して解く
すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…
発想一発 問題へのリンク 問題概要 二つの整数 が与えられる。 の倍数であって の倍数でないものが存在すれば、それを一つ出力し、存在しなければ -1 を出力せよ。 考えたこと の倍数とは、 であるが、余計なリスクを回避したければ普通に を選んでおきたい …