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