【競技プログラミング】ダブリングまとめ
競技プログラミングにおける典型アルゴリズムの1つ「ダブリング」の概要と類題を自分用にまとめる。
ダブリング
アルゴリズムの概要
全体の要素数が
このとき、「
このような問題を愚直に求めようとすると
アルゴリズムの詳細
一般的なダブリングでは、動的計画法で用いるDPテーブルに似た以下のようなテーブルを事前に計算する。
このテーブルの初期条件は以下のようになる。ここで、集合
初期条件と漸化式について補足
初期条件
漸化式の方については、以下のように導出すればよい。
全ての
これを求めるには、
「
事前計算によってこのテーブルを計算できれば、
すなわち、
計算量は、事前計算で
類題
ダブリングを使って解くことのできる類題をいくつか挙げる。
AtCoder Beginner Contest 167 D - Teleporter
問題
AtCoderのページより引用する。
問題文
高橋王国には
個の町があります。町は N から 1 まで番号が振られています。 N それぞれの町にはテレポーターが
台ずつ設置されています。町 1 のテレポーターの転送先は町 i (1 \leq i \leq N) です。 A_i 高橋王は正の整数
が好きです。わがままな高橋王は、町 K から出発してテレポーターをちょうど 1 回使うと、どの町に到着するかが知りたいです。 K 高橋王のために、これを求めるプログラムを作成してください。
制約
2 \leq N \leq 2 \times 10^5 1 \leq A_i \leq N 1 \leq K \leq 10^{18}
解答例
ダブリングを使って簡単に解くことができる。
テーブルを以下のように定義する。
初期条件と漸化式は以下のようになる。
Pythonによるコード例を以下に示す。尚、PyPy3で提出しないとTLEになるので注意。
from typing import List
def main():
# 入力受け取り
N, K = map(int, input().split())
# 0-indexedで受け取っておく
A: List[int] = list(map(lambda x: int(x) - 1, input().split()))
# ダブリングのテーブル
dp: List[List[int]] = [[0 for j in range(N)] for i in range(61)]
# 初期条件
for j in range(N):
dp[0][j] = A[j]
# 遷移
for i in range(1, 61):
for j in range(N):
dp[i][j] = dp[i - 1][dp[i - 1][j]]
# 解を求める
answer: int = 0
# 現在見ているビットの下位からの桁
i: int = 0
# Kを2進数とみなして計算する
while K:
# Kの下位からi桁目が1なら遷移する
if K & 1:
answer = dp[i][answer]
# 1つビットシフトする
K >>= 1
# iを進める
i += 1
# 解の出力(1-indexedに戻す)
print(answer + 1)
if __name__ == "__main__":
main()
実際の提出はこちら。
競プロ典型90問 058 - Original Calculator (★4)
問題
AtCoderのページより引用する。
問題文
あなたは奇妙な電卓を持っています。この電卓は
以上 0 以下の整数を 10^5-1 つ表示できます。この電卓にはボタンAと呼ばれるボタンがあります。整数 1 が表示されているときに ボタンA を x 回押すと、次の処理が順番に行われます。 1
を十進法で表したときの各桁の和を計算し、 x とする。 y を x+y で割ったあまりを計算し、 10^5 とする。 z - 表示されている整数を
に変更する。 z 例えば、
が表示されているときに ボタンA を 99999 回押すと、 1 なので、表示される整数は 99999+(9+9+9+9+9)=100044 に変更されます。 44 今、この電卓に
が表示されています。 ボタンA を N 回押した後に表示されている整数を求めて下さい。 K 制約
0 \leq N \leq 10^5-1 1 \leq K \leq 10^{18} - 入力はすべて整数
解答例
ダブリングテーブルを以下のように定義する。
整数
このとき、初期条件と漸化式は以下のようになる。
Pythonによる実装例を以下に示す。こちらはPyPy3でなくてもTLEにはならない様子。
from typing import List
import math
def f(x: int) -> int:
# 整数xを文字列として解釈して計算する
y: int = sum(map(lambda s: ord(s) - ord("0"), str(x)))
return (x + y) % 100000
def main():
# 入力受け取り
N, K = map(int, input().split())
# log_2 KをMとおく。
M: int = math.ceil(math.log2(K))
# ダブリングテーブル
dp: List[List[int]] = [[0 for j in range(100000)] for i in range(M + 1)]
# 初期条件
for j in range(100000):
dp[0][j] = f(j)
# 遷移
for i in range(1, M + 1):
for j in range(100000):
dp[i][j] = dp[i - 1][dp[i - 1][j]]
# 解を求める
answer: int = N
i: int = 0
while K:
if K & 1:
answer = dp[i][answer]
K >>= 1
i += 1
print(answer)
if __name__ == "__main__":
main()
実際の提出はこちら。
AtCoder Beginner Contest 241 E - Putting Candies
問題
問題文をAtCoderのページより引用する。
問題文
長さ
の数列 N が与えられます。 A=(A_0,A_1,\ldots,A_{N-1})
最初の時点では空の皿があり、高橋君は次の操作を回繰り返します。 K
- 皿の中のアメの個数を
とする。皿に X 個のアメを追加する。 A_{(X\bmod N)}
ただし、で X\bmod N を X で割った余りを表す。 N
回の操作の後で、皿の中には何個のアメがあるか求めてください。 K 制約
2 \leq N \leq 2\times 10^5 1 \leq K \leq 10^{12} 1 \leq A_i\leq 10^6 - 入力はすべて整数である。
解答例
ダブリングテーブルを以下のように定義する。
アメの数が
後者の項の解釈：皿の上には元々
従って、初期条件と漸化式は以下のようになる。
Pythonによる実装例を以下に示す。この問題も
from typing import List
def main():
# 入力受け取り
N, K = map(int, input().split())
A: List[int] = list(map(int, input().split()))
# ダブリングテーブル
dp: List[List[int]] = [[0 for j in range(N)] for i in range(41)]
# 初期条件
for j in range(N):
dp[0][j] = A[j]
# 遷移
for i in range(1, 41):
for j in range(N):
dp[i][j] = dp[i - 1][j] + dp[i - 1][(j + dp[i - 1][j]) % N]
# 答えを格納する変数
answer: int = 0
i: int = 0
while K:
if K & 1:
# dp[i][j]は「操作によって追加されるアメの数」であるので、
# 答えの数に加算していく。
answer += dp[i][answer % N]
K >>= 1
i += 1
# 回答出力
print(answer)
if __name__ == "__main__":
main()
実際の提出はこちら。
AtCoder Beginner Contest 258 E - Packing Potatoes
問題
問題文をAtCoderのページより引用する。
問題文
ベルトコンベアに載って
個のじゃがいもが 10^{100} 個ずつ流れてきます。流れてくるじゃがいもの重さは長さ 1 の数列 N で表され、 W = (W_0, \dots, W_{N-1}) 番目に流れてくるじゃがいもの重さは i \, (1 \leq i \leq 10^{100}) です。ここで、 W_{(i-1) \bmod N} は (i-1) \bmod N を i - 1 で割った余りを表します。 N 高橋君は、まず空の箱を用意し、次のルールに従ってじゃがいもを順番に箱に詰めていきます。
- じゃがいもを箱に入れる。箱に入っているじゃがいもの重さの総和が
以上になったら、その箱には蓋をし、新たに空の箱を用意する。 X
個のクエリが与えられます。 Q 番目のクエリでは、正整数 i \, (1 \leq i \leq Q) が与えられるので、 K_i 番目に蓋をされた箱に入っているじゃがいもの個数を求めてください。問題の制約下で、蓋をされた箱が K_i 個以上存在することが証明できます。 K_i 制約
1 \leq N, Q \leq 2 \times 10^5 1 \leq X \leq 10^9 1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1) 1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q) - 入力は全て整数
解答例
公式解説に倣い、各
また、配列
ダブリングテーブルを以下のように定義する。
配列
配列C
まずは配列
愚直に求めるならば、各
このときの添字を
しかし、この計算だと例えば
そこで、次のように考える。
これを考えると、種類
これを踏まえると、配列
-
C \lfloor \frac{X}{S} \rfloor \times N -
W V j l -
V_l \geq X + V_j l -
C_j (l - j)
-
これで配列
ダブリングテーブルの初期条件と漸化式
ダブリングテーブルの初期条件と漸化式は以下のようになる。
あとは
Pythonによる実装例を以下に示す。
from typing import List
import sys
import itertools
import bisect
input = sys.stdin.readline
def main():
# 入力受け取り
N, Q, X = map(int, input().split())
W: List[int] = list(map(int, input().split()))
K: List[int] = [int(input()) for i in range(Q)]
# Wの総和
S: int = sum(W)
# 配列C
# 各要素は「何周するか×1周の個数」で初期化しておく
C: List[int] = [(X // S) * N] * N
# ダブリングテーブル
dp: List[List[int]] = [[0 for j in range(N)] for i in range(41)]
# 周回分はすでに加算しているので残った余りについて計算する
X %= S
# Wを2周分繋げて累積和を取った配列V
V: List[int] = [0] + list(itertools.accumulate(W * 2))
# 二分探索で配列Cの各要素の値を求める
for j in range(N):
l: int = bisect.bisect_left(V, X + V[j])
C[j] += l - j
# aダブリングテーブルの初期条件
for j in range(N):
dp[0][j] = (j + C[j]) % N
# 遷移
for i in range(1, 41):
for j in range(N):
dp[i][j] = dp[i - 1][dp[i - 1][j]]
# 各クエリの解を求める
for k in K:
# K - 1番目の箱の蓋を締め終わったとき、
# 次に入れるじゃがいもの種類が知りたい
k -= 1
index: int = 0
i: int = 0
while k:
if k & 1:
index = dp[i][index]
k >>= 1
i += 1
# 解の出力
print(C[index])
if __name__ == "__main__":
main()
実際の提出はこちら。
Discussion