AtCoder Beginner Contest 104 Revue des questions précédentes
Temps requis
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.
(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.).
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