N個の点などを一律に動かす設定の問題
Codeforces
DP
制約:数値が10^6以下
二値パラメータ問題
二次元平面上のN点の問題
ある量を固定して考える
最小回数・最小個数を求める
前処理
累積和
集計処理
累積max
バケット
CodeforcesOthers
CodeforcesR2000
点が移動していく問題
N個の点などを一律に動かす設定の問題
累積和テク:累積和や累積結果を前処理しておく
累積和の亜種
最適化問題
すごいよくある感じ 問題へのリンク 問題概要 二次元平面上に 個の点 () と、 個の点光源 () がある。今、 個の点に対して以下の操作を行う 個の点を一律に右に動かす 個の点を一律に上に動かす この操作によって、すべての点について「どの点光源の右下側に…
AtCoder
AtCoder900点
ARC-F
in-place DP
DP
ナップサックDP
BIT
データ構造
DP高速化
DP高速化:セグメント木
区間
区間ソート
探索順序を工夫して解く
条件の言い換え
必要条件を列挙したら十分条件になる
制約条件:2-SAT
座標圧縮
数え上げ問題
コーナーケース
穴や盤外に落とす問題
一直線上のN点の問題
赤色diff
ロボット
操作:一斉に±aする
解空間:O(2^N)通りの選択肢
最適化テク:端点のみを考える
N個の点などを一律に動かす設定の問題
DP高速化:セグメント木上のin-placeDP
またしても、in-place DP のいい練習になった！！！ 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…
AtCoder
有志コン
木
木DP
グラフ
最適化テク:最適化する対象を入れ替える
二乗の木DP
DP
木DPのノード更新にDP
操作
操作:区間
操作後の結果の最適化問題
【問題集】木DPのステップアップ
N個の点などを一律に動かす設定の問題
操作:一斉に±aする
二乗の木 DP のいい練習問題！！！！！ ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…
AtCoder
AtCoder500点
二分探索
操作
操作を逆順に見る
非自明な線形時間
連結性に着目する
区間
単調性に着目する
操作列が文字列で与えられる
後ろから解く
テク:移動可能区間を遷移していく
穴や盤外に落とす問題
ロボット
青色diff
ARC-C
操作後の結果を求める問題
N個の点などを一律に動かす設定の問題
頭の整理が大変！！！ 問題へのリンク 問題概要 左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 si が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。 すぬけ君は Q …
