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

Quand utiliser

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

image.png

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

Recommended Posts

[Pour les professionnels de la concurrence] Résumé du doublement
Résumé de la recherche Bisection pour les professionnels de la concurrence
[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage
[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
[Pour les professionnels de la concurrence] Union Find tree summary
Résumé des méthodes pour déterminer automatiquement les seuils
Résumé de diverses instructions for en Python
Organiser la bibliothèque des professionnels du concours ~ Liste des numéros environ ~
Résumé des petites techniques pour les commandes Linux
Résumé des techniques utiles de Scrapy en Python
Confirmation des bases du concours professionnel ~ pgcd et lcm ~
Résumé des tableaux Python fréquemment utilisés (pour moi-même)
Résumé de Tensorflow / Keras
Résumé des conseils utiles pour le terminal Linux ☆ Mis à jour quotidiennement
Disposition de la bibliothèque professionnelle de concours ~ Équation indéfinie linéaire bidimensionnelle ~
Résumé de l'utilisation de pyenv
Récapitulatif des paramètres d'environnement Python pour moi-même [mac] [ubuntu]
Récapitulatif des outils d'exploitation de l'interface graphique Windows avec Python
Résumé des méthodes de prétraitement pour les débutants en Python (trame de données Pandas)
Un bref résumé du logiciel antivirus pour Linux personnel
Résumé des arguments Python
Résumé de l'apprentissage RAPIDS
Résumé de la méthode d'essai
[Pour les débutants] Résumé de l'entrée standard en Python (avec explication)
Résumé des points d'achoppement à Django pour la première fois
Résumé de la prise en charge des opérations de hachage (dictionnaire) pour Ruby et Python
Récapitulatif des packages yum requis pour l'installation de pip avec EC2
[Pour les débutants] Un résumé en mots des langages de programmation populaires (version 2018)
résumé lié à l'opération de fichier python
Résumé des opérations de liste Python3
2017.3.6 ~ 3.12 Résumé de ce que nous avons fait
Résumé d'utilisation pratique de Flask
Résumé des types de distribution Linux
Pourcentage de LIKE pour pymysql
Vue d'ensemble de Docker (pour les débutants)
Résumé de l'utilisation de Pipenv (pour moi-même)
Résumé de l'utilisation de base de Pandas
Un bref résumé de Linux
Résumé des paramètres de connexion proxy
Implémentation de Scale-Space pour SIFT
Un bref résumé de Graphviz en python (expliqué uniquement pour mac)
Résumé des API recommandées pour l'intelligence artificielle, l'apprentissage automatique et l'IA
Résumé des pages utiles pour étudier le framework d'apprentissage profond Chainer
[Pour les débutants] Résumé de la souffrance de l'AED de Kaggle et de sa lutte