[PYTHON] AtCoder Beginner Contest 089 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Dies ist eine frühere Frage, die ich bereits gelöst habe, aber ich habe den gleichen Fehler im D-Problem erneut gemacht. Die Details des Fehlers werden im Abschnitt D-Problem erwähnt.

Problem A

Es ist eine Gruppe von 3 Personen, also können Sie es durch 3 teilen.

answerA1.py

print(int(input())//3)

B-Problem

Alles, was Sie tun müssen, ist zu zählen, wie viele Farben es gibt, und set zu verwenden, um die Duplikate zu entfernen.

answerB.py

n=int(input())
s=input().split()
print("Three" if len(set(s))==3 else "Four")

C-Problem

Überprüfen Sie zunächst, wie viele Namen mit jedem Buchstaben beginnen. Wenn Sie drei Startzeichen auswählen, können Sie herausfinden, wie viele es gibt, wenn Sie diese drei Zeichen auswählen, indem Sie multiplizieren, wie viele Namen mit jedem Zeichen beginnen. Und da es $ _5C_3 $ Möglichkeiten gibt, den Startcharakter auszuwählen, können Sie überlegen, wie viele Möglichkeiten es gibt, die drei Personen im Betreff auszuwählen, indem Sie die Summe ermitteln.

answerC.py

import itertools
n=int(input())
s=dict()
for i in ["M","A","R","C","H"]:
    s[i]=0
for i in range(n):
    _s=input()
    if _s[0] in ["M","A","R","C","H"]:
        s[_s[0]]+=1
s=list(s.items())
ans=0
for i in range(5):
    for j in range(i+1,5):
        for k in range(j+1,5):
            ans+=(s[i][1]*s[j][1]*s[k][1])
print(ans)

D Problem

Da Sie mehrere Abfragen ** für das Intervall ** verarbeiten müssen, können Sie sehen, dass Sie wahrscheinlich ** kumulative Summe ** verwenden. Es ist auch notwendig, ** die kumulative Summe der magischen Kräfte ** zu berücksichtigen, aber da der Rest von $ R_i $ und $ L_i $ geteilt durch D gleich ist, ** was passiert mit der kumulierten Summe der magischen Kräfte mit dem Rest jeder Zahl * Erwägen *. Zuerst habe ich darüber nachgedacht, den Index jeder Zelle im Array (num) für jeden in die Zelle geschriebenen Rest separat zu speichern, aber ** es ist nicht notwendig, ihn separat zu speichern ** (der Rest in der kumulierten Summe) Ich habe nach der Implementierung festgestellt, dass [Writer-Lösung](siehe https://img.atcoder.jp/abc089/editorial.pdf) für Details. In dieser Implementierung werden auch diejenigen mit den Resten i = 1 bis d-1 im verschachtelten i-1-Array, diejenigen mit i = 0 im d-1 usw. gespeichert. ** Indexverarbeitung Es war sehr mühsam **. Hier werden die Informationen der Quadrate im Array geteilt durch den Rest der Zahlen gespeichert, sodass wir von hier aus die kumulative Summe der magischen Kraft in einem anderen Array (mp) speichern. Die Berechnung der magischen Kraft wird einfach aus der Entfernung von Manhattan berechnet. Wenn Sie diese kumulative Summe finden, können Sie die gesamte magische Kraft ausgeben, die der Abfrage entspricht. Außerdem ist die kumulative magische Kraft, die erforderlich ist, um von "num [g] [0]" zu "num [g] [k]" zu gelangen, "mp [g] [k]" Beachten Sie, dass es notwendig ist, `mp [g] [f] -mp [g] [e]` auszugeben, wenn `` e! = 0```, weil es `ist. ..

answerD.py

from math import ceil
h,w,d=map(int,input().split())
x=ceil((h*w)/d)
num=[[[-1,-1] for j in range(x)] for i in range(d)]#Fall von zu viel(1→0)
mp=[[0]*x for i in range(d)]
a=[list(map(int,input().split())) for i in range(h)]
for i in range(h):
    for j in range(w):
        k,l=a[i][j]%d,a[i][j]//d
        if k==0:
            num[d-1][l-1]=[i,j]
        else:
            num[k-1][l]=[i,j]
for i in range(d):
    for j in range(x):
        if j!=x-1:
            if num[i][j+1]!=[-1,-1]:
                mp[i][j+1]+=(mp[i][j]+abs(num[i][j+1][0]-num[i][j][0])+abs(num[i][j+1][1]-num[i][j][1]))
            else:
                break
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    if l%d!=0:
        e,f=l//d,r//d
    else:
        e,f=l//d-1,r//d-1
    g= d-1 if l%d==0 else l%d-1
    if e==0:
        print(mp[g][f])
    else:
        print(mp[g][f]-mp[g][e])