ニバイ、ニバ～イ
はじめに
- 先日、累乗計算(a^n)を効率的に計算できる繰り返し二乗法を紹介した。
- この手法では、計算量を大きく削減できる。具体的には、シンプルな計算方法での計算量O(n) ⇒ 繰り返し二乗法での計算量O(log n) となる。
- 今回は、同じような考え方で計算量を削減するダブリングを紹介したいと思う。
- なお、コードはswiftで書きます。
ダブリングとは
- まず、要素数nの配列を考え、配列には0...(n-1)の範囲の数値が入っているものとします。n=5なら、[3,4,3,1,0]が例となります。
- このような配列[3,4,3,1,0]に対して、例えば、スタート地点をi=2とし、その要素3を次の地点、さらにi=3の要素1を次の地点、i=1の要素4を次の地点、.....と繰り返していくとき、スタート地点からk番目の地点を求める計算量はO(k)となります。
- 上記のような、シンプルな解法に対して、あらかじめ、地点iから、$2^0,2^1,2^2,2^3,..$番目の地点を記憶しておけば、ショートカットできるため、計算量を削減できます。この考え方により、計算量を削減する手法をダブリングと呼びます。
- よって、まず、事前準備として全ての地点iについて、$2^0,2^1,2^2,2^3,..$番目の地点を記憶する必要があります。
ダブリングのコード化
- 上記で説明したダブリングをコードにしようと思うけど、例題として、AtCoderのABC167のd問題を利用しようと思う。
- 入力例は以下の通り
6 727202214173249351 // n=6、k=727202214173249351
6 5 2 5 3 2 // 最小値を1とする前提だから、取り込むときは-1として配列のindexにあわせ、あとで出力するとき+1する。
- これを解くコードは、以下の感じ。なお、地点iから、$2^j$先の地点を配列mem[j][i]に記憶することとする。
import Foundation
let (n,k) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)! - 1} //配列のindexに合わせるため-1している。
let lgk = Int(log(Float(k)) / log(Float(2))) + 1 //kの対数は2を底としたときlg(k)で表記されるため
var mem = [[Int]](repeating:[Int](repeating:-1,count:n),count:lgk) // 初期化。どうせ全部塗り替えられるので、0でも1でも何でも良いけど、答えに絶対ならない数字にした方が気持ちよい。オプショナル値にしてnilにするのも良いけど、コードが複雑になるのでやめた。
// 一周目
for i in 0..<n {
mem[0][i] = vs[i]
}
// 二周目以降
for j in 1..<lgk {
for i in 0..<n {
mem[j][i] = mem[ j-1 ][ mem[j-1][i] ] // -- ※この式の意味は下記の解説を参照
}
}
var ans = 0 // 開始位置は0
var j = 0
var temp = k
while temp > 0 {
if temp & 1 == 1 {ans = mem[j][ans]}
temp >>= 1
j += 1
}
print(ans + 1) // 出力用に+1とした。
- 上記コードのキモは、※マークの式となる。※以外の部分は、前回解説した繰り返し二乗法を見てほしい。
- ※式の左辺は、地点iから$2^j$先地点を意味する
- ※式の右辺は、地点iから$2^{(j-1)}$先地点のさらに$2^{(j-1)}$先という意味だが、$2^{(j-1)}$先の$2^{(j-1)}$先とはつまり、$2×2^{(j-1)} = 2^j$先と言うこと。
- よって、左辺と右辺は等しいことが分かる。このとき、左辺の「j」に対して、右辺は「j-1」のため、配列memのjについての漸化式となっている。
- 上記コードを実行すると、出力は2となり、ABC167のd問題での回答例と一致した。
- 上記コードをABC167のd問題に提出すると、200ms程度でACとなった。
終わりに
- うーむ。ABC167のd問題以外に、どんな場面で役立つのかいまいち分かってないけど、ダブリングはアルゴリズム的には基礎知識っぽいので、そのうち、利用場面も出てくるでしょう。
- そのときは、また、ここにリンクを張って、お知らせするね。