2021-01-01から1年間の記事一覧
AtCoder
AtCoder400点
ABC-D
茶色diff
二値パラメータ問題
探索順序を工夫して解く
ソート
Greedy
変数変換して扱いやすい同型な問題を見出す
最小回数・最小個数を求める
非自明な比較関数でソートする
【問題集】ソート
ソート:比較関数を設計する
Greedy:条件を満たすまで大きい順に取っていく
最適化問題
最小コスト
ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…
AtCoder
AtCoder500点
ABC-E
木
グラフ
いもす法
クエリ(木上)
クエリ処理問題
木上で配っていくDP
累積和
木DP
DP
遅延評価
水色diff
補集合を考える
変数変換して扱いやすい同型な問題を見出す
【問題集】木の探索
【問題集】DFS・BFSのステップアップ
典型要素を詰め合わせた教育的問題
木上の累積和・いもす法
【問題集】累積和・いもす法
これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
AtCoder
AtCoder600点
ABC-F
DP
O(3^N)
bitDP
クリーク
グラフ
グルーピングの最適化
グルーピング(算数)
前処理
青色diff
補グラフを考える
彩色問題
【問題集】DPのステップアップ
グラフの頂点集合の部分集合を走査する
そのまま覚えたいシンプル設定の中堅以上の典型問題
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
JOI
JOI本選
JOI難易度7
AtCoder
AOJ
グラフ
DFS
トポロジカルソート
BFS
DAG
どれか1つ求める
決めてから整合性を確認する
必要条件を列挙したら十分条件になる
queue
後退解析
【問題集】DFS・BFSのステップアップ
トポロジカルソートせよ、という問題！ 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …
