AtCoderBeginnerContest161 Review & Summary (second semestre)

AtCoder ABC161 Ceci est un résumé des problèmes du concours AtCoder pour débutants 161 qui a eu lieu le 04/04/2020 (samedi), en commençant par le problème A et en tenant compte des considérations. La seconde moitié traite du problème DEF. Cliquez ici pour la première moitié. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF

Problème D Numéro Lunlun

Énoncé du problème Lorsque l'entier positif $ X $ remplit les conditions suivantes, $ X $ est considéré comme un nombre d'exécution. ・ Lorsque $ X $ est exprimé en notation décimale (sans zéro non significatif), la valeur absolue de la différence est de 1 ou moins pour les valeurs de deux chiffres adjacents quelconques. Par exemple, 1234, 1, 334 sont des numéros d'exécution, mais 31415, 119, 13579 ne sont pas des numéros d'exécution. Compte tenu de l'entier positif $ K $. Trouvez le K-ème numéro d'exécution à partir du plus petit.

C'était $ 1 \ leq K \ leq 10 ^ 5 $, donc j'ai pensé qu'il suffirait de compter les nombres d'exécution à partir du plus petit avec une fonction récursive, et j'ai été très heureux de le résoudre quand j'ai écrit le programme. Quand je l'ai résolu, c'était run-run, mais quand j'ai vu le problème, il ne fonctionnait pas du tout. Je publierai le code soumis tel quel.

abc161d.py

def check(mae, keta, count, k):
    if keta == 0:
        count += 1
        if count == k:
            ans = mae
        else:
            ans = -1
        return count, ans
    if mae == 0:
        count, ans = check(0, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(1, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    elif mae == 9:
        count, ans = check(8, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(9, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    else:
        for i in [-1, 0, 1]:
            count, ans = check(mae + i, keta - 1, count, k)
            if ans >= 0:
                ans += mae * 10 ** keta
                return count, ans
    return count, ans

k = int(input())
if k < 10:
    print(k)
else:
    count = 9
    flag = 0
    for keta in range(2, 1000):
        for sento in range(1, 10):
            count, ans = check(sento, keta - 1, count, k)
            if ans >= 0:
                print(ans)
                flag = 1
                break
        if flag == 1:
            break

Quand j'ai écrit le programme, j'ai proposé une fonction récursive, pensant que lors de la création d'un numéro d'exécution avec des chiffres $ m $, je pouvais le créer en décidant le nombre de la position la plus élevée sur le dendrogramme. Par exemple, le numéro d'exécution à 3 chiffres 1 ** à partir de 1 peut être obtenu comme indiqué dans la figure ci-dessous. Il convient de noter qu'il existe deux types de branches quand il est 0 et quand il est 9, et si vous pouvez y prêter attention, après cela, entrez la variable de comptage et les informations sur le chiffre auquel vous pensez actuellement dans la fonction. Si vous recherchez avidement, vous pouvez trouver la réponse à temps.

E problème Yutori

Énoncé du problème Takahashi a décidé de travailler sur $ K $ des jours $ N $ à partir de demain. Compte tenu de l'entier $ C $ et de la chaîne $ S $, choisissez un jour ouvrable qui remplit les deux conditions suivantes. ・ Si vous travaillez un jour, vous ne travaillerez pas pour le jour $ C $ immédiatement après. ・ Lorsque le caractère $ i $ de $ S $ est $ x $, il ne fonctionnera pas après $ i $ jours à compter d'aujourd'hui. Veuillez vous assurer de demander tous les jours où Takahashi travaille.

J'étais pressé au moment du concours, donc je ne pouvais pas lire correctement la signification de "Lorsque le caractère $ i $ de $ S $ est $ x $, cela ne fonctionnera pas dans $ i $ jours à partir d'aujourd'hui", et je suis immédiatement passé au problème suivant. .. Après avoir lu le commentaire, j'ai remarqué une erreur de lecture, mais même si je n'ai pas fait d'erreur de lecture, je pense que je n'ai pas pu la résoudre, j'ai donc pu apprendre une chose de plus. Je me suis demandé si j'avais eu l'expérience de constater que c'était déjà écrit dans le commentaire. Code de Kiri8128 qui a réussi AC à un stade précoce dans le code soumis 11525396) a été utilisé comme référence. @ kiri8128

abc161e.py

n, k, c = map(int, input().split())
S = [1 if a == "o" else 0 for a in input()]
count = 0
X = [0] * n
Y = [0] * n
i = 0
while i < n:
    if S[i]:
        count += 1
        X[i] = 1
        # print(i+1)
        i += c + 1
    else:
        i += 1
if count > k:
    exit()
i = n - 1
while i >= 0:
    if S[i]:
        Y[i] = 1
        # print(i+1)
        i -= c + 1
    else:
        i -= 1
for i in range(0, n):
    if X[i] and Y[i]:
        print(i + 1)

Cela a été utile pour savoir comment recevoir S. Après cela, je ne sais pas comment trouver une solution quand je vois ce problème, mais je pense qu'il est important de résoudre de nombreux problèmes de toute façon, alors je vais m'y consacrer. J'ai commenté print (i + 1) pour ceux qui n'ont pas compris même après avoir lu l'explication, donc si vous le décommentez et résolvez l'exemple, vous verrez diverses choses. L'exemple d'entrée 1 présenté ci-dessous est pris comme exemple.

11 3 2 
ooxxxoxxxoo

La sortie d'impression dans la première instruction for est 1, 6, 10 et la sortie d'impression dans la seconde instruction for est 11, 6, 2. Par conséquent, la réponse est 6. Si vous essayez ces derniers de la même manière pour d'autres exemples, il sera plus facile de comprendre pourquoi la réponse sort. (Je n'ai pas pu trouver une bonne explication dans le texte (sueur))

F problème Division ou soustraction

Énoncé du problème Étant donné un entier positif $ N $. Déterminez un entier $ K $ supérieur ou égal à 2 et inférieur ou égal à $ N $, et répétez l'opération suivante jusqu'à ce que $ N $ soit inférieur à $ K $. ・ Opération: Lorsque $ N $ est divisible par $ K $, remplacez $ N $ par $ N / K $. Sinon, remplacez $ N $ par $ N − K $. De combien de façons existe-t-il pour déterminer $ K $ pour que $ N $ devienne finalement 1?

Au moment du concours, j'ai rapidement arrondi le problème E et contesté le problème F. La raison en est que l'exemple d'entrée 2 est 3141, et $ K $ remarque que 3141 et 3140 sont inclus dans la réponse en premier, et que 3140 est la réponse est d'environ $ N- autour de 1570, 785 ... Il s'avère que toutes les fractions de 1 $ sont incluses dans la réponse. 「2, 4, 5, 10, 20, 157, 314, 628, 785, 1570」 À partir de là, je ne sais pas comment compter que $ K = 2 $ est inclus dans 6 de l'exemple d'entrée 1, et le temps écoulé (transpiration). Avec un peu de réflexion, je viens de vérifier si la fraction $ N $ remplissait la condition. Puisque le candidat $ K $ est une fraction, il peut être divisé jusqu'à ce qu'il se casse, et s'il ne casse pas, vérifiez le reste et s'il est 1, il sera 1 si $ K $ est soustrait plusieurs fois, donc on peut voir que la condition est remplie.

abc161f.py

def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    check_list = make_divisors(n)
    for k in check_list:
        temp_n = n // k
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            elif temp_n % k == 1:
                count += 1
                break
            else:
                break
    print(count)

Puisqu'il s'agit d'un poulet, lorsque n est petit, il est divisé en cas, mais il devrait être possible de résoudre sans lui. La répartition de count = 2 est $ N $ et $ N-1 $. Je veux pouvoir résoudre ce problème F à temps, alors je ferai de mon mieux pour continuer.

Merci d'avoir lu la seconde moitié jusqu'à la fin.