最適化の考察：最適化する対象を入れ替える
AtCoder
AtCoder525点
ABC-F
青色diff
NoviSteps2D
bitDP
前処理
データ構造テク:「次の要素」へのポインタを求める
データ構造テク：indexベースで考える
DP
【問題集】最短路問題
最短路問題
最適化の考察：最適化する対象を入れ替える
最適化問題
最大回数・最大個数を求める
考察：ある数量が小さいことを活用する
部分列
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
AtCoder
有志コン
木
木DP
グラフ
最適化の考察：最適化する対象を入れ替える
二乗の木DP
DP
木DPのノード更新にDP
操作
操作:区間
操作後の結果の最適化問題
【問題集】木DPのステップアップ
N個の点などを一律に動かす設定の問題
操作:一斉に±aする
二乗の木 DP のいい練習問題！！！！！ ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…
0と1の問題
AtCoder
AtCoder1000点
考察：操作・条件・目的関数を言い換える
最適化の考察：最適化する対象を入れ替える
AGC-D
行列
DP
区間
区間DP
しゃくとり法
再帰的構造に着目する
複雑度がlogオーダー
添字のとりうる範囲がlogオーダー
フラクタル構造
赤色diff
これを解けなかったのが強い敗北感。 DP 配列が巨大になりそうなときに、最適化する対象を入れ替えるテクは今までなんども見ているのにそれが思いつかない思考の硬さを思い知らされた。 問題へのリンク 問題概要 0 と 1 のみからなる行列の複雑度を すべて同…
