Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@atilol(atilol _)

AtCoderダブリング問題総まとめ（中３女子しらべ）

Last updated at Posted at 2024-08-23

こんにちわ！中３女子です！！！

ABC367 Eのダブリング問題が解けなかったのが悔しくて過去問を12問解きました☆
AtCoder上で解けるダブリング問題12問と実装時のポイントやパターンをまとめたのでごさしゅうください！

ダブリング問題が解けるようになると自然と内から自信が満ち溢れてくるはずですし、気になるひとにダブリングの解説をした日にはそれはもういちころのはずです！ダブリングを上手に使えるようになって恋人をゲットです!?（ぐるぐる目）

対象読者

緑コーダー周辺のひとにぶっさされです！

おすすめの精進管理ツール

お兄ちゃんたち、もしかして精進もしてないのに結果がでないとかゆってないよね？？？
あっとーてき精進でライバルに差をつけるです！

AtCoder精進チャート
shojin-chart2.gif

つくったのでつかって☆

ダブリング問題一覧

問題を解く方はこちらをどうぞ！
ダブリング解法で個人的に解きやすかった順（てきとー）です

ダブリング問題の頻出パターン（中３女子しらべ）

パターンを抑えて得点力あっぷです！

  • そのままダブリングすればよいパターン
    • やるです！
  • 最初の遷移を工夫して解くパターン
    • 問題文をもとに遷移を作るです！
  • DPする値を工夫するパターン（和、積など）
    • 遷移のDPと和のDPの２つをつくるなどするです！
  • 繰り返し2乗法部分で工夫して解くパターン
    • 考察してつじつまを合わせるです！

周期性を考えた方が簡単な場合はそっちで解くのもありです！

ダブリングかんたん解説

基本的な問題設定

長さ$N$の数列 $A_1~A_2~\dots~A_N$ が与えられる。数列$A$の位置$i$にいるとき、遷移先を位置$A_i$とする。はじめ位置$1$にいるとして、$K$回遷移を繰り返した後の位置を求めよ →実際の問題例

多くの場合Kが非常に大きいため($K≦10^{18}$など)、愚直にシミュレーションすると間に合いません。プロセッサさんもっとがんばって！

ダブリングのアルゴリズム

  1. DPにより2の累乗回遷移したときの位置をあらかじめ求めます

    $dp[i][j]$を位置$j$から$2^i$回遷移したときの位置とすると、$2^{i+1}$回遷移したときの位置は以下の漸化式で求められます

    $$dp[i+1][j] = dp[i][dp[i][j]]$$

    上手くいくことの説明
    $dp[i][j]$が位置$j$から$2^i$回遷移したときの位置であるため、その位置からさらに$2^i$回遷移した位置が $2^i + 2^i$ で $2^{i+1}$回遷移した位置になります

  2. 任意の整数$K$は$2$の累乗の和で表せるため、$K$回遷移した後の位置は繰り返し2乗法を用いて求めることができます

求める遷移を$2$の累乗回の場合に絞ることができるため、$K$回の遷移の導出に必要な計算量を $O(NlogK)$ に落とすことができます！すごいね！！

「$2$の累乗回の遷移先が高速で求まる」と、「任意の整数が$2$の累乗の和に高速に分解できる」の2つがかみ合ってて良き！

Pythonによる実装例

同じ問題設定の問題 D - Teleporter

import math

N, K = list(map(int, input().split()))
M = int(math.log2(K)) + 1
A = list(map(int, input().split()))
A = [e - 1 for e in A]  # 0-indexedにする

# 2^i回目の遷移先をiの小さいほうから求める
dp = [[0] * N for _ in range(M)]
dp[0] = A
for i in range(M - 1):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

# 繰り返し2乗法によりK回目の遷移先を求める
ans = 0  # 初期位置0で初期化
i = 0
while K > 0:
    if K % 2:
        ans = dp[i][ans]
    i += 1
    K >>= 1
print(ans + 1)  # 0-indexedにした場合は忘れずに+1

ひとこと解説 & 実装例

わたしが最初に思いついた解法を紹介しています
他の解法については公式解説をみて！

D - Teleporter Diff 754

ダブリング解法

そのままダブリングすればよいパターンです！

制約がK≦10^18でlog2(K)<60なので2^60までDPで求めればいいですね

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 60
N, K = rints()
A = [e - 1 for e in rints()]

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = 0
p = 0
while K > 0:
    if K & 1:
        ans = dp[p][ans]
    p += 1
    K >>= 1
print(ans + 1)
定数倍高速化のポイント

位置jから2^i回遷移したときの位置をdp[i][j]で管理していますが、インデックスを逆にしてdp[j][i]のように管理すると配列アクセスでキャッシュミスが起こりやすくなり遅くなるので気をつけましょう
問題によってはTLEするかもです

dp[i][j]の場合 244ms
dp[j][i]の場合 731ms

この問題では3倍くらい差が出ます

周期性を利用した解法

遷移をグラフにすると、各頂点はある1つの頂点への有向辺を持つグラフ（Functional Graph）となります
Functional Graphは遷移を繰り返すと最終的にサイクルに入るのでその周期性を利用することでも解くことができます
O(N)で解けるので計算量的にはこちらの方が良いです

ダブリングが上手く書けない場合は周期性で解くのもありです！
問題や自分との相性で使い分けると良さめです

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

N, K = rints()
A = [e - 1 for e in rints()]

# サイクルの始まりを探索
T = [0]
ind = {0: 0}
cycle_start = -1
for i in range(N):
    nxt = A[T[-1]]
    if nxt in ind:
        cycle_start = ind[nxt]
        break
    T.append(nxt)
    ind[nxt] = i + 1

if len(T) > K:
    # サイクルに入る前に終わる場合
    print(T[K] + 1)
else:
    # サイクルに入る場合
    print(T[cycle_start + (K - cycle_start) % len(T[cycle_start:])] + 1)

A57 - Doubling

ダブリング解法

そのままダブリングすればよいパターンです！

ダブリングしてクエリに順に答えればOK

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

M = 30
N, Q = rints()
A = rdecints()

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

for _ in range(Q):
    x, y = rints()
    x -= 1
    p = 0
    while y > 0:
        if y & 1:
            x = dp[p][x]
        p += 1
        y >>= 1
    print(x + 1)

D - Gathering Children Diff 794

ダブリング解法

最初の遷移を工夫して解くパターンです！

LRで場合分けして最初の遷移を求めてダブリングです

import sys

M = 17
s = input()
N = len(s)

A = [0] * N
for i in range(N):
    if s[i] == "R":
        A[i] = i + 1
    else:
        A[i] = i - 1

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = [0] * N
for i in range(N):
    ans[dp[M][i]] += 1
print(*ans)

058 - Original Calculator（★4） Diff 1199

ダブリング解法

最初の遷移を工夫して解くパターンです！

MOD10^5より遷移先の値は0～10^5-1なので、問題文中の１～３の処理を0～10^5-1に対して行い1回目の遷移行列を求めます
あとはダブリングして終わりです！

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 60
L = int(1e5)
N, K = rints()

A = list(range(L))  # 最初の遷移を入れる配列
for i in range(L):
    j = i
    y = 0
    while j > 0:
        y += j % 10
        j //= 10
    A[i] = (i + y) % L

dp = [[0] * L for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(L):
        dp[i + 1][j] = dp[i][dp[i][j]]

ans = N
p = 0
while K > 0:
    if K & 1:
        ans = dp[p][ans]
    p += 1
    K >>= 1
print(ans)

E - Permute K times Diff 1370

ダブリング解法

そのままダブリングすればよいパターン＋微考察です！

問題文の通りAへの操作を考えるとむずかしいですが、Xの遷移を考えればよいことに気づけばダブリングして終わりです

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

M = 60
N, K = rints()
X = rdecints()
A = rints()

dp = [[0] * N for _ in range(M)]
dp[0] = X
for i in range(M - 1):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

ind = list(range(N))
p = 0
while K > 0:
    if K & 1:
        for i in range(N):
            ind[i] = dp[p][ind[i]]
    p += 1
    K >>= 1

print(*[A[i] for i in ind])

D - 阿弥陀 Diff 1730

ダブリング解法

最初の遷移を工夫して解くパターンです！

問題が長いですが要は1つのあみだくじが1つの遷移を表すので、１つのあみだくじから最初の遷移を作成してダブリングです！

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

P = 30
N, M, D = rints()
A = rdecints()

X = list(range(N))
for a in reversed(A):
    X[a], X[a + 1] = X[a + 1], X[a]

dp = [[0] * N for _ in range(P + 1)]
dp[0] = X
for i in range(P):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

p = 0
ans = list(range(N))
while D > 0:
    if D & 1:
        for i in range(N):
            ans[i] = dp[p][ans[i]]
    p += 1
    D >>= 1

for e in ans:
    print(e + 1)

E - Putting Candies Diff 1248

ダブリング解法

DPする値を工夫するパターンです！

遷移先はX%Nなので、dp[i][j]=アメj個所持時に2^i回遷移したときに得られるアメの個数とすれば
dp[i + 1][j] = dp[i][j] + dp[i][(j + dp[i][j]) % N] とできます！

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 40
N, K = rints()
A = rints()

dp = [[0] * N for i in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][j] + dp[i][(j + dp[i][j]) % N]

ans = 0
i = 0
while K > 0:
    if K & 1:
        ans += dp[i][ans % N]
    i += 1
    K >>= 1
print(ans)

E - Packing Potatoes Diff 1545

ダブリング解法

最初の遷移を工夫して解くパターンです！

重さWiのi番目のじゃがいもから箱に詰め始めたとき、次の箱に入れる最初のじゃがいもが何番目になるかの遷移を考えればよいです。
その際にi番目からはじめたときに箱に入るじゃがいもの個数も同時に数えておきます。以下の実装では累積和＋にぶたんで求めています

import sys
rint = lambda: int(sys.stdin.readline())
rints = lambda: list(map(int, sys.stdin.readline().split()))

M = 40
N, Q, X = rints()
W = rints()

cumW = [0] * (N + 1)    # ジャガイモの重さの累積和
for i in range(N):
    cumW[i + 1] += cumW[i] + W[i]

cnt = [0] * N   # i番目から始めたときに箱に入るじゃがいもの数
A = [0] * N     # i番目から始めたときに次の箱に最初に入るじゃがいもの番号
for i in range(N):
    L, r = 1, int(2e9) + 1
    while L < r:
        m = (L + r) // 2
        s = (i + m) // N * cumW[-1] - cumW[i] + cumW[(i + m) % N]
        if s >= X:
            r = m
        else:
            L = m + 1
    A[i] = (i + L) % N
    cnt[i] = L

dp = [[0] * N for _ in range(M + 1)]
dp[0] = A
for i in range(M):
    for j in range(N):
        dp[i + 1][j] = dp[i][dp[i][j]]

for _ in range(Q):
    K = rint() - 1
    j = 0
    i = 0
    while K > 0:
        if K & 1:
            j = dp[i][j]
        i += 1
        K >>= 1
    print(cnt[j])

E - Sequence Sum Diff 1175

ダブリング解法

最初の遷移を工夫して解くパターン + DPする値を工夫するパターンです！

mod MなのでM未満の整数aに対してf(a^2, M)を計算し最初の遷移を求めます
あとはダブリング、と言いたいところですが答えが和なので工夫が必要です
遷移先のDPに加え、dp_sum[i][j] = jから2^i回遷移したときの和、として管理することで解くことができます

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

P = 34
N, X, M = rints()

dp_a = [[0] * M for _ in range(P + 1)]
dp_sum = [[0] * M for _ in range(P + 1)]
for i in range(M):
    dp_a[0][i] = i * i % M
    dp_sum[0][i] = i

for i in range(P):
    for j in range(M):
        dp_a[i + 1][j] = dp_a[i][dp_a[i][j]]
        dp_sum[i + 1][j] = dp_sum[i][j] + dp_sum[i][dp_a[i][j]]

ans = 0
p = 0
while N > 0:
    if N & 1:
        ans += dp_sum[p][X]
        X = dp_a[p][X]
    p += 1
    N >>= 1
print(ans)

周期性を利用した解法

ダブリング解法の和のDPが思いつかない場合（わたしのこと）は周期性を利用して解くことができます

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

N, X, M = rints()
A = [X]
d = {X: 0}
cycle_start = -1
for i in range(1, N):
    X = X * X % M
    if X in d:
        cycle_start = d[X]
        break
    A.append(X)
    d[X] = i

ans = 0
if cycle_start == -1:
    ans = sum(A)
else:
    cycle_sum = sum(A[cycle_start:])
    cycle_len = len(A[cycle_start:])
    ans = sum(A[:cycle_start])
    N -= cycle_start
    A = A[cycle_start:]
    ans += N // cycle_len * cycle_sum + sum(A[: N % cycle_len])
print(ans)

E - Geometric Progression Diff 1453

ダブリング解法

DPする値を工夫するパターン ＋ 繰り返し2乗法部分で工夫して解くパターンです！

dp[i] = A^(2^i)までの和とすると、Kが2の累乗の場合について解けます
Kが2の累乗以外の場合は困りますが、繰り返し2乗法部分を工夫することで解けます

例えばK=6のとき、6 = 2^1 + 2^2です。素直にdp[1] + dp[2]を考えると、
dp[1] + dp[2] = (A^0 + A^1) + (A^0 + A^1 + A^2 + A^3) となり答えが合いません

これを見ると、A^2 * dp[2]とすると以下のようになり答えが合いそうです
dp[1] + A^2 * dp[2] = (A^0 + A^1) + A^2 * (A^0 + A^1 + A^2 + A^3)

あとは実装あるのみです！

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

P = 40
A, X, M = rints()

dp = [0] * (P + 1)
dp[0] = 1
An = A
for i in range(P):
    dp[i + 1] = (dp[i] + An * dp[i]) % M
    An = An * An % M

ans = 0
pad = 0
p = 0
while X > 0:
    if X & 1:
        ans += pow(A, pad, M) * dp[p]
        ans %= M
        pad += 1 << p
    p += 1
    X >>= 1
print(ans)

等比級数の和を計算する解法

個人的にはkyopro_friendsさんの解法がシンプルで好きでした

mod Mにおいてaの逆元が存在しない場合はmod M*aで計算しておいてaで割る、は覚えておきたいテクニックでした

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))

A, X, M = rints()
if A == 1:
    print(X % M)
    exit()

K = M * (A - 1)
a = A
Ax = 1
while X > 0:
    if X & 1:
        Ax = Ax * a % K
    a = a * a % K
    X >>= 1
print((Ax - 1) // (A - 1) % M)

D - Moving Piece Diff 1491

ダブリング解法

ごめんにゃさい。。解説をみてもよく分かりませんでした。

賢明なみなさんは分かると思うのでけんちょんさんの解説の解法(2)をご覧ください

周期性を用いた解法

全ての開始位置を試して最大値を出力します
Pが順列という制約を読み飛ばしてしまったのでごちゃごちゃなコードになっていますが一応ACです（ひどい）

Pが順列だとどこから始めてもしっぽの無いサイクルになるのでもう少し楽に解けます

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

INF = int(1e18 + 1)
N, K = rints()
P = rdecints()
C = rints()

ans = -INF
for x in range(N):
    A = [P[x]]
    d = {P[x]: 0}
    cycle_start = -1
    for i in range(K - 1):
        na = P[A[i]]
        if na in d:
            cycle_start = d[na]
            break
        A.append(na)
        d[na] = i + 1

    t = 0
    for a in A:
        t += C[a]
        ans = max(ans, t)

    if cycle_start == -1:
        continue

    cycle_sum = sum(C[e] for e in A[cycle_start:])
    if cycle_sum <= 0:
        continue

    t = sum(C[e] for e in A[:cycle_start])
    A = A[cycle_start:]
    k = K - cycle_start
    cycle_len = len(A)
    t += k // cycle_len * cycle_sum
    ans = max(ans, t)

    tt = t
    for i in range(k % cycle_len):
        tt += C[A[i]]
        ans = max(ans, tt)

    if k // cycle_len == 0:
        continue

    for i in range(cycle_len):
        t -= C[A[-i]]
        ans = max(ans, t)

print(ans)

D - へんてこ辞書 Diff 1586

遷移回数が10^100000なのでさすがのダブリングさんでもTLEですね。log2(10^100000)を計算する気にもなりません。調べた結果332192くらいでした。O(Nlogk)なのでやっぱり無理ですね

周期性を利用した解法

サイクルの周期Tが求まればk%Tなどして解けそうです
ただし、kが大きくて数値として扱えないので一桁ずつ処理する工夫が必要です

import sys
rints = lambda: list(map(int, sys.stdin.readline().split()))
rdecints = lambda: [e - 1 for e in rints()]

N, a = rints()
k = input()
b = rdecints()
a -= 1

mem = [a]
d = {a: 0}
cycle_start = -1
for i in range(1, N + 1):
    nx = b[mem[-1]]
    if nx in d:
        cycle_start = d[nx]
        break
    mem.append(nx)
    d[nx] = i

# サイクルに入る前にk回になる場合
if len(str(cycle_start)) > len(k) or (
    len(str(cycle_start)) == len(k) and cycle_start >= int(k)
):
    print(mem[int(k)] + 1)
    exit()

# kを一桁ずつ処理して(k-cycle_start)%cycle_lenを求める
cycle_len = len(mem[cycle_start:])
L = 0
for ki in k:
    L = (L * 10 + int(ki)) % cycle_len
L = (L - cycle_start) % cycle_len
print(mem[cycle_start + L] + 1)

おわりに

中３女子に不慣れなので語尾が安定しにゃい

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?