[PYTHON] Critique du concours AtCoder pour débutant 166

Les résultats de cette fois

Impressions de cette époque

Dans l'ensemble, j'étais impatient, et cette fois aussi, le résultat n'était pas bon. Cependant, je suis heureux de penser que j'étais collant comme ça. De plus, je ne peux me concentrer que sur les 20 premières minutes et les 20 dernières minutes, alors je voudrais améliorer cela. Je voulais résoudre le problème F ...

Personnellement, je pense que résoudre le problème F est plus naturel que éditorial, alors veuillez vous y référer.

Problème A

Sorties ABC ou ARC.

A.py

s=input()
print("ABC" if s=="ARC" else "ARC")

Problème B

Vous n'avez besoin que de l'un des bonbons, donc si vous regardez k bonbons dans l'ordre et que vous avez ces bonbons, changez l'élément de l'arrangement correspondant à chaque personne en 1 ( Si vous ne l'avez pas, laissez-le à 0). Sous cela, il suffit de compter les éléments du tableau qui ne sont pas 1, donc cela devient comme suit.

B.py

n,k=map(int,input().split())
ans=[0]*n
for i in range(k):
    d=int(input())
    a=list(map(int,input().split()))
    for j in a:
        ans[j-1]=1
print(n-sum(ans))

Problème C

Aussi, je l'ai fait avec le problème C. Je pensais que ce ne serait pas beaucoup, mais je résolvais à nouveau le problème sur la base d'un algorithme ... Au moment où je l'ai vu, c'était Union Find !!!. Je pensais que c'était Union Find et je l'ai implémenté sans m'en apercevoir jusqu'à ce que j'aie essayé l'exemple de cas. ** Lisez attentivement l'énoncé du problème **.

Si vous lisez correctement l'énoncé du problème, ce ne sera pas du tout difficile. Quand il y a une route j reliant $ A_j et B_j $, quand $ A_j \ leqq B_j $, $ A_j $ n'est pas un bon observatoire. De plus, lorsque $ B_j \ leqq A_j $, $ B_j $ n'est pas un bon observatoire. Par conséquent, pour chaque observatoire, supposez un bon observatoire (1) au début, et si l'information routière montre que ce n'est pas un bon observatoire, réglez-le sur (0), et finalement seul le bon observatoire est 1 Par conséquent, il suffit de considérer le total.

C.py

n,m=map(int,input().split())
h=list(map(int,input().split()))
x=[1]*n
for i in range(m):
    a,b=map(int,input().split())
    if h[a-1]>=h[b-1]:
        x[b-1]=0
    if h[a-1]<=h[b-1]:
        x[a-1]=0
print(sum(x))

Problème D

Je pensais que ** A et B n'auraient pas un tel modèle **, alors j'ai essayé de restreindre les candidats pour ** A et B **, mais le désir de O (1) est sorti et j'ai commencé à factoriser. (Je suis revenu à moi-même lorsque j'ai commencé à réfléchir et à réfléchir à ce à quoi ressemblaient les citations.)

Ici, quand A est négatif et B est positif, $ A ^ 5-B ^ 5 <0 $ n'est pas égal à X (> 0), donc quand A est négatif, B est toujours négatif. .. De plus, si A et B sont tous deux négatifs et $ A ^ 5-B ^ 5 = X $, A et B sont positifs si A et B sont échangés et que les signes de A et B sont opposés (positifs). ** A est un bon nombre positif ** car il existe sous la forme d'un ensemble de nombres. Vous pouvez également supposer $ A> B $ à ce moment.

Ici, si A est déterminé à partir de $ B ^ 5 = A ^ 5-X $, B peut être obtenu par O (1), j'ai donc essayé de trouver la plage de A.

Premièrement, lorsque A est fixe, la valeur minimale de $ A ^ 5-B ^ 5 $ est $ B = A-1 et $ sous $ A> B $ (si $ \ car $ B devient le maximum). bien). De plus, $ A ^ 5- (A-1) ^ 5 $ est une augmentation monotone pour A. Ici, par exemple, si $ A = 10 ^ 3 $, alors $ B = 10 ^ 3-1 $ et $ A ^ 5-B ^ 5 = 4,999009990001 \ times 10 ^ {12} $. Par conséquent, lorsque $ A = 10 ^ 3 $, $ A ^ 5-B ^ 5> 10 ^ {12}> X $, donc A doit être ** inférieur à 10 $ ^ 3 $ **. Par conséquent, il est garanti qu'il y a au moins une paire de $ (A, B) $ qui remplit les conditions, donc la plage de A est ** suffisante ** en considérant de 1 à 10 $ ^ 3 $.

Sous ceci, si $ B = (A ^ 5-X) ^ {\ frac {1} {5}} $, alors $ B ^ 5 = A ^ 5-X $, donc chaque $ A ^ 5 Prenez la 5ème racine de -X $ pour trouver B et voir si le nombre est un entier. De plus, pour éviter une erreur à ce stade, $ (A ^ 5-X) ^ {\ frac {1} {5}} $ converti en entier par la fonction int est élevé à la 5e puissance et l'original $ A ^ J'ai vérifié si cela correspond à 5-X $. En répétant cette opération et en interrompant lorsqu'une paire correspondante (A, B) apparaît, vous pouvez trouver la paire (A, B).

answerD.py

x=int(input())
for A in range(10**3):
    k=A**5-x
    if k>=0:
        l=int(k**0.2)
        if l**5==k:
            print(A,l)
            break
    else:
        k=-k
        l=int(k**0.2)
        if l**5==k:
            print(A,-l)
            break

E problème

Et si j'en décide un? En menant l'expérience avec la politique (cette expérience a pris environ 15 minutes), j'ai eu l'idée de ** formulons-le une fois **, donc l'expression relationnelle qui existe entre les deux personnes de la paire Était réglé.

En d'autres termes, $ A_K + A_L = L-K $ est valable lorsque les participants du nombre K et du nombre L ($ K <L $ est bon parce qu'ils considèrent la combinaison) sont appariés. Cette formule peut être encore ** transformée ** en $ A_K + K = L- A_L $.

A ce moment, la hauteur est positive, donc quand $ K \ geqq L $, $ A_K + K \ geqq A_K + L> -A_L + L = L-A_L $, et $ A_K + K = L- A_L $ Ne tient pas. Par conséquent, $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) sont calculés et les valeurs correspondent à $ ($ ( i, j) $ sera accepté comme une ** paire qui remplit les conditions sans duplication **. Par conséquent, $ A_i + i $ ($ i = 1,2,…, N $), $ j- A_j $ ($ j = 1,2,…, N $) sont gérés dans le dictionnaire et inclus dans les deux. Il vous suffit de calculer combien il y en a pour le nombre.

answerE.py

n=int(input())
a=list(map(int,input().split()))
c,d=dict(),dict()
for i in range(n):
    if i+1-a[i] in c:
        c[i+1-a[i]]+=1
    else:
        c[i+1-a[i]]=1
    if i+1+a[i] in d:
        d[i+1+a[i]]+=1
    else:
        d[i+1+a[i]]=1
ans=0
for i in c:
    if i in d:
        ans+=(c[i]*d[i])
print(ans)

F problem

Il était censé être fait avec un montant de calcul qui n'était clairement pas à temps, comme DP et DFS. Je sens que ** pouvoir se calmer une fois ** est le vrai pouvoir ici ...

En repensant à ce problème, nous pouvons voir que A + B + C est constant. De plus, c'est un problème de jouer au jeu, il est donc bon de ** faire attention à l'état **. De plus, puisque ** toutes les bases sont la méthode gourmande **, nous allons mener des expériences avec ce qui précède à l'esprit.

Ensuite, vous pouvez décider goulûment (intuitivement) de chaque choix (ici je me suis retrouvé avec l'idée illogique qu'il n'y a pas de raison gourmande **). En d'autres termes, l'idée est que ** les petits nombres ne sont pas soustraits et les grands nombres sont soustraits ** autant que possible. De cette façon, vous pouvez ** éviter 0 dans chaque sélection **.

Si vous pouvez réfléchir jusqu'à présent, la réponse sera un pas de plus, mais il convient de noter qu'il existe des modèles ** qui ne peuvent pas éviter ** 0. Autrement dit, un modèle ** où les deux nombres sélectionnables sont 0. Par conséquent, nous voulons non seulement éviter les 0, mais également éviter ce modèle dans la sélection suivante. En supposant que la sélection actuelle est la Xème fois, "le nombre qui ne peut pas être sélectionné dans la Xème sélection de temps est 0 (①)" et "la chaîne de caractères utilisée pour la X + 1ème sélection de temps est le caractère utilisé pour la Xème sélection de temps". Le modèle de "différent de la colonne (②)" et "le nombre sélectionné à la fois dans la Xème sélection et dans la X + 1ème sélection est 1 (③) et la Xème opération est -1 pour ce nombre" est ** Étant donné que les deux nombres qui peuvent être sélectionnés à la fois X + 1 sont des motifs 0 **, dans le cas de ①, ② et ③, la Xème fois est comparée au nombre sélectionné à la fois par la Xème sélection de temps et la X + 1ème sélection de temps. Tout ce que vous avez à faire est d'exploiter +1.

answerF.py

n,a,b,c=map(int,input().split())
s_=input().split()
ans=""
for i in range(n):
    s1,s2=s_[i]
    if s2=="B":
        if i!=n-1:
            if s_[i+1]=="AC" and c==0 and a==1:
                a,b,ans=(a+1,b-1,ans+"A")
            elif s_[i+1]=="BC" and c==0 and b==1:
                a,b,ans=(a-1,b+1,ans+"B")
            else:
                a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        else:
            a,b,ans=(a-1,b+1,ans+"B") if a>b else (a+1,b-1,ans+"A")
        if min(a,b)==-1:
            print("No")
            break
    elif s1=="A":
        if i!=n-1:
            if s_[i+1]=="AB" and b==0 and a==1:
                a,c,ans=(a+1,c-1,ans+"A")
            elif s_[i+1]=="BC" and b==0 and c==1:
                a,c,ans=(a-1,c+1,ans+"C")
            else:
                a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        else:
            a,c,ans=(a-1,c+1,ans+"C") if a>c else (a+1,c-1,ans+"A")
        if min(a,c)==-1:
            print("No")
            break
    else:
        if i!=n-1:
            if s_[i+1]=="AB" and a==0 and b==1:
                b,c,ans=(b+1,c-1,ans+"B")
            elif s_[i+1]=="AC" and a==0 and c==1:
                b,c,ans=(b-1,c+1,ans+"C")
            else:
                b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        else:
            b,c,ans=(b-1,c+1,ans+"C") if b>c else (b+1,c-1,ans+"B")
        if min(b,c)==-1:
            print("No")
            break
else:
    print("Yes")
    for j in range(n):
        print(ans[j])