2020-02-05から1日間の記事一覧
AOJ
順列テク:マッチングと見る
RUPC
順列を題材とした問題
二部グラフ
フロー
二部マッチング
最小費用流問題
条件の言い換え
操作
最小コスト
操作:swap
個別の要素の動きに注目する
Greedy:各要素について独立に考えてよい
絶対値やminを扱う問題
f(i,j)をiとjとに分離する
マッチング
順列テク:順列は互換(swap操作)の積として表せる
【問題集】フローのステップアップ
最適化問題
今の RUPC / AUPC の先駆けとなった合宿の北大セットの問題!!! このセットは、全問題のタイトルの頭文字が 'D' というセットだった セットへのリンク 北大アーカイブへのリンク 問題へのリンク 問題概要 長さ の順列 が与えらえる。これらを並び替えて完…
Codeforces
復元
DFS
木
グラフ
構築:木
構築
Greedy
決めてから整合性を確認する
必要条件を列挙したら十分条件になる
主客転倒
CodeforcesDIV3
CodeforcesR2100
面白かった!!! 問題へのリンク 問題概要 頂点の木が与えられる。木の各辺に対して、以下の条件を満たすように 1 以上 1000000 以下の整数値を割り振りたい。 条件は 個ある 番目の条件は、2 頂点 と整数値 が指定されて、 を結ぶパス上の辺の値の最小値が…
Codeforces
Greedy
LIS
文字列
Greedy:どちらも可なら厳しい方
二分探索
二分探索:lower_bound
色に関する問題
復元
アナグラム
操作:swap
ソートすることが目的の操作の問題
CodeforcesDIV3
CodeforcesR2000
これと同じでは!? atcoder.jp 問題へのリンク 問題概要 長さ の文字列 が与えられる。 いま、文字列の各 index に色を塗ることを考える。色を塗ったあと、隣接する異なる色をもつ 2 文字を swap することができる。swap した結果得られる文字列がソートさ…