制約条件:K個以下
AtCoder
ACLpractice
二次元グリッド
可視化テク:二次元情報を二部グラフにして考える
二部グラフ
マッチング
二部マッチング
フロー
そのまま覚えたい典型問題
最小費用流問題
N個からK個を選ぶ設定の問題
順列の最適化問題
順列を題材とした問題
最大スコア
制約条件:K個以下
復元
どれか1つ求める
最適化テク:解を変形していく(最適性を失わずに)
下駄を履かせて負辺除去
フローを流す際にバイパス辺を用意する
解空間:O(N!)通りの選択肢
【問題集】フローの入門
最適化問題
D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です！ 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…
AtCoder
青色diff
旧ABC
Greedy
辞書順
文字列
コーナーケース
順列の最適化問題
制約条件:K個以下
解空間:O(N!)通りの選択肢
アナグラム
Greedy:辞書順最小を求める
旧 ABC の C 問題の中でも、個人的に最難だと思う問題！ 現代の ABC で出題されても水色 diff になると思う。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の各文字を並べ替えてできる文字列 のうち、 となる が 個以下であ…
AtCoder
AtCoder500点
ABC-E
ある量を固定して考える
ある量を決めるとGreedy
Greedy
全探索:ビット全探索
全探索
二次元グリッド
区間
0と1の問題
水色diff
テク:幅が小さいことに着目する(2^Wが小さい)
指数探索系問題
区間分割の仕方を走査する問題
制約条件:K個以下
制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…
