DP高速化:stackの活用
AtCoder
AtCoder500点
ABC-E
水色diff
NoviSteps1D
DP高速化:stackの活用
stack
シミュレーション:stackの活用
DP
シミュレーション
所要時間を求める問題
各kに対して
いかにも stack が登場しそうな問題！ 問題へのリンク 問題概要 下の図のように、高さが の仕切りが等間隔に並んでいて、その間と両端の カ所のスペースを表す番号を とする。これらは幅が等しい。 今、スペース 0 に水を入れていく。1 個分のスペースについ…
AtCoder
有志コン
そのまま覚えたいシンプル設定の中堅以上の典型問題
最大値の最大化
最適化テク:「最大値の最大化」に基づく緩和
DP
シーケンシャルDP
DP状態:on/off
DP状態:state
DP高速化:直前との比較のみでよい
区間分割型シーケンシャルDP
DP高速化
f(i,j)をiとjとに分離する
数列
Monge性
DP高速化:Monge性の活用(LARSCH)
最適化の考察：緩和して解く
最大スコア
区間分割の仕方を走査する問題
区間
操作をstackを用いて高速化する
DP高速化:stackの活用
stack
最適化問題
これは学びの深い DP 問題！ 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…
AtCoder
AtCoder700点
ARC-E
黄色diff
DP
包除原理
包除原理:DP
stack
非自明な線形時間
DP高速化
DP高速化:セグメント木
数列
区間分割型シーケンシャルDP
考察：補集合を考える
数え上げ問題
グラフ・盤面・数列の個数の数え上げ
座標圧縮
データ構造テク：全体に反映させる値を別にもつ(遅延評価)
DP高速化:stackの活用
区間分割の仕方を走査する問題
操作をstackを用いて高速化する
NoviSteps3D
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
AtCoder
AtCoder800点
累積和テク:左右両端からの累積和や累積結果を前処理
考察：一部の変数を固定して考える
Greedy:ある量を決めると残りが決まっていく
Greedy
DP
添字のとりうる範囲がlogオーダー
見積り大事
操作
最小回数・最小個数を求める
データ構造テク：前処理
stack
データ構造
応用的な探索
数列
最適化の考察：最適解の形を考える
ARC-E
ARC-like
黄色diff
累積和テク:累積和や累積結果を前処理しておく
DP高速化:stackの活用
操作をstackを用いて高速化する
最適化問題
NoviSteps3D
こういうのを確実に... 問題へのリンク 問題概要 1 以上の整数からなる長さ の数列 が与えられる。この数列に対して、以下の操作を好きな回数だけ好きな順序で行うことで広義単調増加となるようにしたい。最小回数を求めよ。 個の整数から 1 つ選んで -2 倍…
