AtCoder Beginner Contest 104 Revue des questions précédentes

Temps requis

スクリーンショット 2020-05-20 22.58.36.png

Impressions

Ce n'est pas bon que vous ne puissiez pas résoudre le problème dans la bande de niveau D. ** Je n'ai pas pu presser mon intelligence pour trouver des indices ** du tout. J'essaierai d'être ferme pendant le concours.

Problème A

Vous pouvez le diviser par moins de 1200 ou moins de 2800. Il est facile d'écrire à l'aide de l'opérateur ternaire.

answerA.py


r=int(input())
print("ABC" if r<1200 else "ARC" if r<2800 else "AGC")

Problème B

Même si c'était un problème B, c'était assez gênant. La deuxième condition peut être facilement traitée, mais la dernière condition est d'extraire uniquement la partie pertinente de la chaîne de caractères et de juger si elles sont toutes en minuscules. Vous pouvez utiliser la fonction islower () pour déterminer s'il est inférieur.

answerB.py


s=input()

if s[0]=="A" and s[2:-1].count("C")==1:
    if (s[1]+s[2:2+s[2:-1].index("C")]+s[s[2:-1].index("C")+3:]).islower():
        print("AC")
    else:
        print("WA")
else:
    print("WA")

Problème C

Ce problème a été résolu rapidement, mais j'ai fait une erreur stupide (** l'instruction break a été oubliée ** et ** la variable a été mal écrite **).

Tout d'abord, si vous y réfléchissez normalement, vous devez choisir parmi ceux avec le score de base le plus élevé, mais en fonction du score complet, le point de problème que vous devez résoudre changera **.

Ici, je me suis concentré sur le fait qu'il n'y a que D ($ \ leqq $ 10) types de problèmes, et j'ai pensé que ** je devrais décider quel problème devrait être résolu pour chacun **. En d'autres termes, vous pouvez rechercher tous les ensembles de problèmes qui doivent être complétés par une recherche complète de bits.

Une fois que vous avez décidé des questions à répondre, vous pouvez choisir celles avec le score le plus élevé (✳︎) parmi les questions que vous ne choisissez pas. De plus, puisque le problème à résoudre est résolu, (✳︎) ne peut pas être complété, et ** si vous n'obtenez pas de point G ou plus sans terminer, vous devez considérer le modèle suivant **.

answerC.py


import math
d,g=map(int,input().split())
pc=[list(map(int,input().split())) for i in range(d)]
ans=10000000000000000000
for i in range(1<<d):
    s=0
    ans_=0
    for j in range(d):
        if (i>>j)&1:
            s+=(pc[j][1]+pc[j][0]*100*(j+1))
            ans_+=pc[j][0]
    if s>=g:
        ans=min(ans,ans_)
    else:
        for j in range(d-1,-1,-1):
            if not((i>>j)&1):
                if s+(pc[j][0]*100*(j+1))>=g:
                    h=-((s-g)//(100*(j+1)))
                    s+=(h*100*(j+1))
                    ans_+=h
                    ans=min(ans,ans_)
                    break
                else:
                    break
print(ans)

Problème D

Au début, je pensais que je n'étais pas douée pour les chaînes de caractères (peut-être parce qu'il y a beaucoup de modèles DP), mais j'ai fini avec une queue ... ** Vous devez vous débarrasser de vos faiblesses et vous attaquer au problème **….

Puisque le nombre d'ABC peut être déterminé ** dans l'ordre (progressivement) de l'avant à A, B, C **, on peut soupçonner que DP peut être utilisé. Faire). De plus, comme il est difficile de penser à A → B → C à la fois, vous pouvez penser que vous devriez décider séparément pour A → B et B → C (✳︎).

Par conséquent, vous pouvez utiliser (✳︎) tout en utilisant ** DP si vous le divisez en l'état où ** A est décidé, l'état où AB est décidé et l'état où ABC est décidé. Jusqu'à présent, la discussion a été plutôt bonne, mais je ne pouvais pas pleinement envisager le traitement d'un personnage.

En fait,? Peut être simplement ** A, B, C en essayant les trois modèles et en les ajoutant ensemble **. De plus, en fait, ** un état où rien n'a été décidé ** est également nécessaire en tant qu'état, alors ajoutez ceci.

À partir de la considération ci-dessus, nous pouvons voir que le dp suivant doit être défini.

IMG_0382.PNG

(Quand j'ai défini DP, j'ai senti qu'il était important de verbaliser ce qu'était chaque état.)

Si vous décidez jusqu'à présent **, vous pouvez penser à la transition **. Il existe de nombreux modèles dans lesquels la transition est $ dp [i] [j] = dp [i-1] [j] $, mais le modèle augmente selon que le caractère $ i $ ème est $ A, B ou C $. Je vais. Autrement dit, lorsque le i-ème caractère est A, il est nécessaire d'ajouter le motif de $ dp [i-1] [3] $ à $ dp [i] [0] $, et lorsque le i-ème caractère est B, il est nécessaire d'ajouter le motif. Il est nécessaire d'ajouter le motif de $ dp [i-1] [0] $ à $ dp [i] [1] $, et lorsque le i-ième caractère est C, $ dp [i] [2] $ à $ Vous devez ajouter le modèle de dp [i-1] [1] $. De plus, si le i-ème caractère est ?, Il existe des motifs de A, B et C, donc en les ajoutant tous, $ dp [i] = [3 * dp [i-1] [0] + dp [i-1] [3], 3 * dp [i-1] [1] + dp [i-1] [0], 3 * dp [i-1] [2] + dp [i-1] [ Il devient 1], 3 * dp [i-1] [3]] $.

Cela ne suffit pas, mais la figure suivante peut expliquer l'exemple du premier échantillon (trois sont disposés verticalement quand? Est-ce que A et B sont. Si c'était C.).

IMG_0383.JPG

Ce qui précède est mis en œuvre et devient comme suit. Il est facile de se tromper dans ce qui arrive à dp [0], vous devez donc faire attention.

✳︎ ** Étant donné que les problèmes gourmands et les problèmes de sous-chaînes ont une forte probabilité de DP ** d'avant, ** Je veux calmement faire une politique ** et ** Réfléchissez bien à la transition réelle ** Je voudrais être prudent.

answerD.py


mod=10**9+7
s=input()
l=len(s)
dp=[[0]*4 for i in range(l)]
for i in range(l):
    if i==0:
        dp[i][3]=1
        if s[i]=="A":
            dp[i][0]=1
        elif s[i]=="?":
            dp[i][0]=1
            dp[i][3]=3
    else:
        if s[i]=="A":
            dp[i]=[(dp[i-1][0]+dp[i-1][3])%mod,dp[i-1][1],dp[i-1][2],dp[i-1][3]]
        elif s[i]=="B":
            dp[i]=[dp[i-1][0],(dp[i-1][0]+dp[i-1][1])%mod,dp[i-1][2],dp[i-1][3]]
        elif s[i]=="C":
            dp[i]=[dp[i-1][0],dp[i-1][1],(dp[i-1][1]+dp[i-1][2])%mod,dp[i-1][3]]
        else:
            dp[i]=[(3*dp[i-1][0]+dp[i-1][3])%mod,(3*dp[i-1][1]+dp[i-1][0])%mod,(3*dp[i-1][2]+dp[i-1][1])%mod,(3*dp[i-1][3])%mod]
print(dp[-1][2])

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes