[PYTHON] [Pour les professionnels de la concurrence] Résumé du doublement

Quand utiliser

• Lors de la recherche du Nième état dans lequel la même opération est répétée. (Surtout quand il y a plusieurs éléments dans un aspect et qu'ils passent l'un à l'autre)

Ce qui est bon

Normalement, il est possible de raccourcir l'endroit où l'ordre de O (N) est pris de la fin à O (log N). La méthode des carrés itératifs en est également un exemple. Il est formidable que O (XlogN) puisse être supprimé lorsque tous les résultats de N opérations sur plusieurs éléments X comme décrit ci-dessus sont obtenus.

Que faire

L'idée est la même que la méthode des carrés itératifs. Le deuxième résultat du premier résultat, le quatrième résultat du deuxième résultat, et ainsi de suite. Notez l'état après chaque opération dans un tableau (il devient bidimensionnel lors de l'utilisation de plusieurs éléments en même temps) (quelque chose comme dp?).

image

En pensant

Si le Nième temps peut être exprimé par exactement 2 ^ k, la liste peut être référencée directement, mais si elle devient une fraction, le Nième temps est donné en se référant à plusieurs reprises au tableau construit. ex.) Le 5ème temps peut être émis en se référant au résultat du 1er temps après avoir fait référence au résultat de la 4ème fois. L'arithmétique des bits est influente dans ce processus.

Combien de bits ressortent lorsqu'ils sont convertis en bits

a = []
for i in range(int(math.log2(K)) + 1):
    if K>>i & 1:
        a.append(i)

modèle

Créez une table pour rechercher après N opérations de X éléments.

#Création de tableaux bidimensionnels
dv = []
for _ in range(int(math.log2(K)) + 1):
    l = [0] * X
    dv.append(l)

# dv[0][0:X]Initialiser

#Construire une table en doublant
for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]

Exemple d'utilisation

Méthode du carré répété

Méthode du carré répété

MOD = 10 ** 9 + 7

def mod_pow(x: int, n: int):
    bi = str(format(n, "b"))
    res = 1
    a = x
    for i in range(len(bi)):
        if n >> i & 1:
            res = (res * a) % MOD
        a = (a * a) % MOD
    return res

ABC167 D - Teleporter

À peu près à ce moment, 10 ^ 18 ≒ 2 ^ 60, vous pouvez donc voir jusqu'à 60. Vous pouvez également calculer «log2 (K) + 1» à chaque fois.

def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]

    dv = []
    for _ in range(60):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, 60):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(60):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in a:
        now = dv[i][now]
    print(now + 1)

J'ai fait TLE avec Python, donc avec PyPy.

ABC136 D - Gathering Children

10 ** 100 (googol) O (XlogN) pour la deuxième fois est également serré. En fin de compte, il ne fait que répéter l'état des allers-retours entre les RL, vous n'avez donc qu'à vous soucier des cotes et des cotes du nombre d'opérations. De plus, même si tous les cas sauf l'extrémité droite de S sont comme R, on peut voir que la phase finale peut être atteinte en tournant le nombre maximum de caractères 10 ** 5 fois.

# log2(10 ** 5) ≒ 16.6 → Enfin ans[17][]Devrait être obtenu.
LOG = 18

def main():
    S = input()
    N = len(S)
    to = []
    for _ in range(LOG):
        l = [0] * N
        to.append(l)
    
    for i in range(N):
        to[0][i] = i + 1 if S[i] == "R" else i - 1
    
    for i in range(1, LOG):
        for j in range(N):
            to[i][j] = to[i - 1][to[i - 1][j]]

    ans = [0] * N
    for j in range(N):
        ans[to[LOG - 1][j]] += 1

    L = [str(i) for i in ans]
    print(" ".join(L))
    return

référence

• https://www.akiradeveloper.com/post/algorithm-doubling/#%E3%83%80%E3%83%96%E3%83%AA%E3%83%B3%E3%82%B0
• https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0804_abc136
• https://www.hamayanhamayan.com/entry/2019/08/07/204315