はじめに
- 競技プログラミングには、色々な高速化テクニックがあるけど、そのうちの一つにin-place化がある。
- in-placeは、「その場限りの」という意味であり、例えば、本来は問題を解くのに二次元のdp配列[i][k]を使うべきところ、遷移状態「i」の計算時に、「i-1」の時の結果のみ分かれば良いときは、「i-2」以前の状態の記録が不要になるので、配列を一次元のdp[k]のみにして、常に直前の状態のみ（その場限り）の記録だけ残すテクニックをin-place化と呼ぶ。
- なお、in-place化自体は、変数が減る（例えば、二次元配列 ⇒ 一次元配列）事により、使用メモリは減らせることが出来るけど、計算ロジックが変わらない（例えば、forループの数がfor-i、for-kループの二重のまま）なら、計算量は変わらず、高速化に繋がらない。
- とはいえ、例えば、dp配列を二次元から一次元に落とすことにより、forループを二重からfor-iの一つのみに減らせる場合は、高速化に繋がることになる。
- で、ここからが本題です。
- in-place化したとき、for-iループの遷移において、新しいdpの一部が古いdp[k]の「最大値や最小値」を元に作られる、と言うことであれば、dp[k]をセグ木にぶち込んで、簡単に求められる。
- でも、新しいdpの一部が、「古いdp[k] + k」とか「古いdp[k] + abs(X[i] - k)」の中の最大値や最小値を使うという場合、セグ木で求められるだろうか？
- まぁ、求められるから、今回紹介するのですが。
例題
- 下記コードを高速化したい。（きっかけとなった投稿）
extension Array {
init(_ cnt: Int, _ v: Element) {
self = [Element](repeating: v, count: cnt)
}
}
let (N,Q) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let X = readLine()!.split(separator:" ").map{Int($0)!}
// let inf = Int.max / 2 // -- 本来はコチラを使う
let inf = 99 // 表示するとき、infが大きすぎると見づらいため、99としている。
var dp = [Int](N,inf)
dp[0] = abs(X[0])
print(0,dp) // dp経過観察
for i in 1..<Q {
let kx = X[i-1]
var dpkx = inf
for k in 0..<N { // 計算量O(N) -- コイツをなんとかしたい！
dpkx = min( dp[k] + abs(X[i] - k) , dpkx )
}
dp[kx] = dpkx
print(i,dp) // dp経過観察
}
print(dp.min()!)
- 下記を読み込ませて実行すると...
/// 入力値
10 12 // dp[k]のkの範囲0..<NのN=10、クエリ実行数Q回のQ=12
3 4 7 9 3 0 2 0 9 4 9 9 // クエリQ=12回で使用する値を格納する配列X[i]。制約0≦X[i]≦N
/// 出力 i別のdp
0 [3, 99, 99, 99, 99, 99, 99, 99, 99, 99]
1 [3, 99, 99, 7, 99, 99, 99, 99, 99, 99]
2 [3, 99, 99, 7, 10, 99, 99, 99, 99, 99]
3 [3, 99, 99, 7, 10, 99, 99, 12, 99, 99]
4 [3, 99, 99, 7, 10, 99, 99, 12, 99, 6]
5 [3, 99, 99, 3, 10, 99, 99, 12, 99, 6]
6 [4, 99, 99, 3, 10, 99, 99, 12, 99, 6]
7 [4, 99, 4, 3, 10, 99, 99, 12, 99, 6]
8 [6, 99, 4, 3, 10, 99, 99, 12, 99, 6]
9 [6, 99, 4, 3, 10, 99, 99, 12, 99, 4]
10 [6, 99, 4, 3, 4, 99, 99, 12, 99, 4]
11 [6, 99, 4, 3, 4, 99, 99, 12, 99, 4]
/// 出力 最終のdpのmin値
3
- 上記コードの計算量は、for-iループとfor-kループの二重ループによりO(Q･N)だから、もし制約が$N,Q≦10^5$だったりすると、TLEになるね。相場的には、計算量が$10^8$程度でTLEになり始めるからね。
- for-kループが攻略対象で、minを使ってるから、セグ木を使えそうな気もするけど、余分な「+abs(X[i]-k)」があるせいでセグ木が使えないね。+abs(X[i])だけなら、dp[k]のmin値を出した後にabs(X[i])を足すだけだから楽勝だけどね。
例題の高速化テクニック（dplとdprに分けてセグ木利用！）
- ハッキリ言って、強引なやり口です。
-
dp[k] + abs(X[i] - k)の形のせいで、セグ木を使えないんなら、セグ木を使える形にすればいいじゃない！のマリーさん方式です。 - 具体的には新しい配列を2つ作ります。ここでやっと、表題の
dplとdprを回収したよ。- dpl[k]：dp[k] + N - k
- dpr[k]：dp[k] + k
- この新しい配列を使うと、
dp[k] + abs(X[i] - k)は以下のように表せます- k < X[i] のとき、dpl[k] + X[i] - N
- X[i] ≦ k のとき、dpr[k] - X[i]
- このdpl、dprであれば、セグ木で簡単にmin値を出せるね！
- これを使ってセグ木利用のコードを書くよ。セグ木の説明はしないから、分からない人は、過去の投稿を読んでね。
- 少しだけ説明すると、minクエリ用に、セグ木構造体の「base」は「Int.max」、「biOpe」は「min」に変えてます。
//前半は省略//
var dp = [Int](N,inf)
// セグ木準備
var dpl = dp
var dpr = dp
for k in 0..<N {
dpl[k] = dp[k] + N - k
dpr[k] = dp[k] + k
}
var stl = SegTree(dpl) // セグ木については別の投稿を読んでね。
var str = SegTree(dpr) // 「base：Int.max」「biOpe：min」にしてminクエリ対応版へ
//セグ木update関数
func stupdt(_ k:Int){
dpl[k] = dp[k] + N - k
dpr[k] = dp[k] + k
stl.update(k,dpl[k])
str.update(k,dpr[k])
}
dp[0] = abs(X[0])
stupdt(0) // セグ木アップデート！
print(0,dp)
for i in 1..<Q {
let kx = X[i-1]
// var dpkx = inf
// for k in 0..<N { // 計算量O(N)
// dpkx = min( dp[k] + abs(X[i] - k ) , dpkx )
let dpkx = min(stl.query(0,X[i]) + X[i] - N , str.query(X[i],N) - X[i]) // セグ木で代替
// }
dp[kx] = dpkx
stupdt(kx) // セグ木アップデート！
print(i,dp)
}
print(dp.min()!)
- 出来た！dpl,dprをセグ木にぶち込んで、for-kループを破壊したので、上記コードの計算量はO(Q･logN)になったね！
- セグ木準備が多少手間だけど、準備した後の利用は簡単だね。セグ木を自作しておかないとコンテストは戦えないってことが改めて良く分かる。
- 念のため、高速化前と、出力が同じか確認しておくね。よし、一致を確認!
0 [3, 99, 99, 99, 99, 99, 99, 99, 99, 99]
1 [3, 99, 99, 7, 99, 99, 99, 99, 99, 99]
2 [3, 99, 99, 7, 10, 99, 99, 99, 99, 99]
3 [3, 99, 99, 7, 10, 99, 99, 12, 99, 99]
4 [3, 99, 99, 7, 10, 99, 99, 12, 99, 6]
5 [3, 99, 99, 3, 10, 99, 99, 12, 99, 6]
6 [4, 99, 99, 3, 10, 99, 99, 12, 99, 6]
7 [4, 99, 4, 3, 10, 99, 99, 12, 99, 6]
8 [6, 99, 4, 3, 10, 99, 99, 12, 99, 6]
9 [6, 99, 4, 3, 10, 99, 99, 12, 99, 4]
10 [6, 99, 4, 3, 4, 99, 99, 12, 99, 4]
11 [6, 99, 4, 3, 4, 99, 99, 12, 99, 4]
3
- 最初、「セグ木で代替」のとこで、
dpkx = min(stl.query(0,X[i]) , str.query(X[i],N))と書いてしまって出力結果がズレたのは内緒です。dpl,dprをdpに戻すのを忘れてminしちゃ駄目だよね。
おわりに
- ちょっと、特殊なケースのテクニックだけど、自分でも忘れちゃいそうだから、投稿にしてまとめました。
- セグ木を利用するためには、多少強引な手口も使うべき、ということだね。