操作:区間
AtCoder
AtCoder300点
ABC-C
区間
操作:区間
操作
最小回数・最小個数を求める
ヒストグラム
0と1の問題
連結成分
主客転倒
ランレングス圧縮
茶色diff
for文
最適化問題
整理するのがちょっと大変系。でもとても教育的だと思う! 問題へのリンク 問題概要 次元の整数ベクトル () が与えられる。これを以下のようなベクトルの和として表したい。 () のように「」が連続していてそれ以外は になっているベクトル 例えば、(1, 3, 3…
AtCoder
AtCoder700点
unrated公式コン
数え上げ問題
DP
包除原理
ナップサックDP
二項係数
区間
操作
操作:区間
被覆する方法の数え上げ
ダブルカウントを防ぐ場合分け
操作:上書き
補集合を考える
被覆
区間の連結関係に関する問題
解空間:O(2^N)通りの選択肢
700 点は絶対落とさないようにしたい!!! 本番、DP と包除原理の二通りの方針が早期に見えて、「どちらかで詰まったらどちらかに立ち戻ろう」と思いながら DP に突き進んで見た。それでちゃんと通ってよかった。 問題へのリンク 問題概要 長さ の区間があ…
本番では回避したん。こういうのをサッサササッとバババババーンと解けるようになりたい。 問題へのリンク 問題概要 個の数列 が与えられる。以下の操作を好きな回数だけ行って得られる数列の総和を最大化せよ。 連続する 個の区間の数列を一斉に 0 にする …
区間
最小回数・最小個数を求める
コーナーケース
操作
ABC-C
AtCoder300点
AtCoder
操作:上書き
操作:区間
順列を題材とした問題
緑色diff
被覆
最適化テク:自明な上界が最適解
条件の言い換え
ARC-C
最適化問題
ARC 099 C - Minimization 問題概要 1〜N の順列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。 連続する K 個の区間を選んで、その区間のすべての数をその区間にある最小の数に置き換える 制約 1 <= K <= N <= 105 解法 間違いや…