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. ABC161D.jpg 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.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié