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

Les résultats de cette fois

Impressions de cette époque

Cette fois, il avait environ 10 minutes de retard. J'ai pensé qu'il irait jusqu'à la dernière minute et je l'ai soumis, mais c'était vraiment à la dernière minute. J'étais bon à la fois la dernière fois et cette fois, mais je n'ai pu participer que tardivement, donc je vais humilier le concours de la semaine prochaine.

F semblait pouvoir le résoudre rapidement, mais après que E l'ait résolu, je réfléchissais en retirant les os du poisson pour le dîner, donc je ne pouvais pas le faire. C'est mortifiant.

De plus, cette fois, la largeur du retrait est de 2 au lieu de 4 habituellement. Pour diverses raisons, la construction de l'environnement n'était pas à temps. Si vous en avez envie, changez la largeur en 4.

Problème A

Sortie comme dit. Faites simplement la soustraction.

A.py

a,b=map(int,input().split())
print(2*a+100-b)

Problème B

** Il n'y a que 2 à 1000 candidats pour le nombre maximum **, il suffit donc de rechercher tous. Cependant, il est nécessaire d'avoir une paire (nombre maximum, degré GCD) lors d'une recherche complète.

B.py

n=int(input())
a=list(map(int,input().split()))
ans=[2,sum(i%2==0 for i in a)]
for j in range(1000,2,-1):
  x=[j,sum(i%j==0 for i in a)]
  if x[1]>ans[1]:
    ans=[x[0],x[1]]
print(ans[0])

Problème C

Puisque le reste est 3, le total de ** chiffres doit être un multiple de 3 **. À ce stade, réfléchissez à la manière de sélectionner les chiffres que vous souhaitez supprimer en ** enregistrant uniquement le reste après avoir divisé chaque chiffre par 3. Donc, ici, $ check [i] $: = (le reste est le nombre de chiffres de $ i $).

Premièrement, si le nombre total de chiffres est égal à 0 depuis le début, 0 est émis. Dans d'autres cas, il suffit de ** classer soigneusement les cas comme indiqué ci-dessous **.

(1) Lorsque le reste du nombre total de chiffres est 1.

[1] $ check [1] \ geqq Quand 1 $, $ check [1] - = 1 $ fait que le reste du total des chiffres est égal à 0. Lorsque [2] $ check [1] \ <1 $, $ check [2] - = 2 $ fait que le reste du nombre total de chiffres est égal à 0. [3] Dans tous les cas, quand $ sum (check) = 0 $, n'importe quel chiffre est sélectionné et effacé, donc le sujet n'est pas satisfait. À ce moment, -1 est émis. On peut aussi montrer que sous cette condition ce sera $ check [2] \ <2 $.

(2) Lorsque le reste du nombre total de chiffres est de 2.

[1] $ check [2] \ geqq Quand 1 $, $ check [2] - = 1 $ fait que le reste du nombre total de chiffres est égal à 0. Quand [2] $ check [2] \ <1 $, $ check [1] - = 2 $ fait que le reste du nombre total de chiffres est égal à 0. [3] Dans tous les cas, quand $ sum (check) = 0 $, n'importe quel chiffre est sélectionné et effacé, donc le sujet n'est pas satisfait. À ce moment, -1 est émis. On peut également montrer que sous cette condition ce sera $ check [1] \ <2 $.

C.py

n=input()
l=len(n)
check=[0]*3
for i in range(l):
  check[int(n[i])%3]+=1
if int(n)%3==0:
  print(0)
elif int(n)%3==1:
  if check[1]>=1:
    check[1]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[2]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)
else:
  if check[2]>=1:
    check[2]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[1]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)

Problème D

Je l'ai mal lu ** et j'ai mal compris que chaque mouvement ne pouvait être fait que complètement **. Dans ce cas, vous n'avez pas besoin de concevoir quoi que ce soit juste pour penser à la valeur maximale après avoir pris la somme cumulée deux fois. Préparez également deux tableaux à utiliser dans la discussion suivante. $ b [i]: = $ ($ i $ ème distance parcourue complète) et $ c [i]: = $ ($ i $ ème distance parcourue complète cumulée).

Ici, il est bon de considérer ** séparément quand il ne bouge pas complètement **. En d'autres termes, si vous êtes complètement déplacé vers le $ i (0 \ <i \ <n-2) $ th, vous pouvez déplacer le ** $ i + 1 $ th au maximum car il peut être à mi-chemin * *est. En d'autres termes, s'il est exprimé dans une expression, $ (\ sum \ _ {j = 0} ^ {i} b [j]) + c [i] $ est la $ i $ ème solution. Vous pouvez considérer cela comme n'importe quel $ i $. Par conséquent, il peut être implémenté en augmentant $ i $ dans l'ordre tout en gérant la valeur de $ \ sum \ _ {j = 0} ^ {i} b [j] $. De plus, il peut être facilement implémenté en prenant la somme cumulée de $ b $. Ceci est le deuxième code.

De plus, puisque ce qui précède ne couvre pas le cas où il ne bouge pas même une fois et le cas où il bouge complètement avec tous les mouvements, ajoutez ces cas pour trouver la valeur maximale.

D.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
ans=[0,b[0]]
now=b[0]
for i in range(1,n):
  ans.append(now+c[i])
  now+=b[i]
ans.append(now)
print(max(ans))

D_better.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
d=list(accumulate(b))
ans=[0]+[d[i]+c[i] for i in range(n-1)]+[d[n-1]]
print(max(ans))

E problème

Il s'agit d'un sujet similaire à HHKB Programming Contest 2020-E Lamps. Tout d'abord, supposons que vous ayez un ** bloc ou une partie fermée par un bord ** d'une ligne. S'il y a même une ** lampe dans cette partie **, cette partie sera illuminée. Au contraire, dans ce cas, il ne sera pas éclairé par la lampe. Compte tenu de l'heure de la ligne, ** le nombre de carrés éclairés dans les deux cas est la réponse **. Dans le cas des lignes et des colonnes, il suffit d'inverser chacune d'elles, alors ne considérez d'abord que l'heure des lignes.

Tout d'abord, si vous souhaitez gérer ensemble ces ** pièces continues, vous pouvez effectuer une compression de longueur de tirage ** (typique). En d'autres termes, dans l'état initial, le carré où la lampe est placée est 1, le carré où le bloc est placé est 0 et le carré où rien n'est placé est -1. Pour le moment, je veux considérer la partie sans blocs, donc ** compresser ** selon qu'une certaine cellule est 0. Autrement dit, il ressemble à la figure ci-dessous.

Ensuite, après compression comme indiqué sur la figure ci-dessus, ** si la partie compressée contient au moins un 1, ** la partie en trait plein doit être définie sur 1 (carré éclairé). Vous pouvez également utiliser groupby et spécifier $ lambda \ x: x == 0 $ pour func pour effectuer la compression (Reference). ).

Personnellement, je pense que je dois m'habituer à l'idée de la compression de longueur d'exécution. Aussi, si j'en ai envie, je publierai un article de synthèse sur la question de la compression de longueur de tirage **.

E.py

from itertools import groupby
h,w,n,m=map(int,input().split())
check1=[[-1]*w for i in range(h)]
check2=[[-1]*h for i in range(w)]
for i in range(n):
  a,b=map(int,input().split())
  check1[a-1][b-1]=1
  check2[b-1][a-1]=1
for i in range(m):
  c,d=map(int,input().split())
  check1[c-1][d-1]=0
  check2[d-1][c-1]=0
#print(check1)
#print(check2)
for i in range(h):
  x=[(key,list(group)) for key,group in groupby(check1[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check1[i][now]=1
        now+=1
    else:
      now+=len(g)
for i in range(w):
  x=[(key,list(group)) for key,group in groupby(check2[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check2[i][now]=1
        now+=1
    else:
      now+=len(g)
ans=0
for i in range(h):
  for j in range(w):
    if check1[i][j]==1 or check2[j][i]==1:
      ans+=1
#print(check1)
#print(check2)
print(ans)

Problème F

Je n'ai pas envie de le résoudre. Je ne résoudrai pas cette fois.