トポロジカルソート
AtCoder
AtCoder500点
ABC-E
水色diff
Functionalグラフ
なもりグラフ
サイクル
サイクル検出
DFS
Union-Find
最小コスト
グラフ
順列の最適化問題
トポロジカルソート
連結成分
連結成分ごとに分解して考える
Kruskal法
最小全域木
全域木を考える
補集合を考える
制約条件:作業の依存関係・順序関係
解空間:O(N!)通りの選択肢
最適化問題
最近話題の Functional Graph の問題！ 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…
JOI
JOI本選
JOI難易度7
AtCoder
AOJ
グラフ
DFS
トポロジカルソート
BFS
DAG
どれか1つ求める
決めてから整合性を確認する
必要条件を列挙したら十分条件になる
queue
後退解析
【問題集】DFS・BFSのステップアップ
NoviSteps1Q
トポロジカルソートせよ、という問題！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …
AtCoder
AtCoder2000～点
AGC-F
順列を題材とした問題
操作:隣接swap
操作:swap
操作
順列テク:逆順列を考える
条件の言い換え
変数変換して扱いやすい同型な問題を見出す
分割統治法
辞書順
最適化テク:制約条件を加えて探索候補を絞る
グラフ
グラフの辺数を削減する
トポロジカルソート
priority_queue
Greedy
天才のGreedy
可視化テク:二次元平面上に可視化する
主客転倒・寄与分解
ソートすることが目的の操作の問題
操作後の結果の最適化問題
思わず解きたくなる興味深い良問
難しいGreedy
これも自力で解けたの、嬉しい！！！！！ 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…
