2019-03-03から1日間の記事一覧
AtCoder
AtCoder400点
ABC-D
Union-Find
クエリ処理問題
クエリ先読み
後ろから解く
操作を逆順に見る
グラフ問題
クエリ(グラフ上)
連結成分
差分更新
各kに対して
クエリ:削除
水色diff
これまたすごく教育的な問題！！！！！！！！！ UnionFind 木の基本的な使い方 (連結成分のサイズ獲得含む) クエリを先読みしておいて逆順に処理 (多くのクエリ先読み問題ではもっと変な順番で処理したりする) 差分のみ更新する考え方 といったあたりを学ぶ…
AtCoder
AtCoder300点
ABC-C
stack
カッコ列
データ構造
0と1の問題
操作
自明な上界が最適解
条件の言い換え
解を変形していく(最適性を失わずに)
最適解の形を考える
操作を最大何回行えるか
操作:2つのものを1つにマージ
灰色diff
入れ子構造
久しぶりのカッコ列の整合判定問題！！！ カッコが binary になっただけ。ただし通常のカッコ列問題は )( みたいなやつはダメだけど、今回はこういうのも消せる (解法 1 へ)。 あるいは今回はカッコ列問題だと思わなくても、自然な考察で回答を導くこともで…
AtCoder
AtCoder400点
AGC-B
操作
条件の言い換え
操作:上書き
操作を逆順に見る
操作:区間
区間
必要条件を列挙したら十分条件になる
累積和
数列
前処理
操作によって出来上がるものの最適化問題
最大スコア
青色diff
操作を逆順に見るとよいという、すごく良い例題！大好き！！！ 問題へのリンク 問題概要 要素からなる数列 が与えられる。今、以下の操作を好きな回数だけ行う。 長さが の区間を選んで、区間全体を白く塗るか、黒く塗る 操作を行った後に黒く塗られたマスの…
整理するのがちょっと大変系。でもとても教育的だと思う！ 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…
