最適化テク:最適化する対象を入れ替える
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 のみからなる行列の複雑度を すべて同…