[PYTHON] HHKB Programmierwettbewerb 2020 Rückblick
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Es war der zweitbeste Darsteller, aber ich bin enttäuscht, weil ich hier nicht ziele. Es ist gut, das D-Problem zu überspringen und zum E-Problem überzugehen, aber ** Ich bin enttäuscht, weil das D-Problem hätte gelöst werden müssen, wenn ich sorgfältig überlegt habe **.
Problem A
Wenn es gleich Y ist, konvertieren Sie es mit der oberen Methode.
A.py
s,t=input(),input()
if s=="Y":
print(t.upper())
else:
print(t)
B-Problem
Ich war ungeduldig, weil ich den Fragentext nicht lesen konnte. Zusammenfassend besteht das Problem darin, die Anzahl der Quadrate zu ermitteln, die nicht überladen sind, wenn Sie 2 vertikale oder 2 horizontale Quadrate auswählen.
Wählen Sie 2 vertikale oder 2 horizontale Quadrate. Wenn Sie zu diesem Zeitpunkt invertiert denken, können Sie sich die vertikalen 2 Quadrate als die horizontalen 2 Quadrate vorstellen. Bestimmen Sie also die horizontalen 2 Quadrate der ursprünglichen Matrix und die horizontalen 2 Quadrate der invertierten Matrix, um die Summe zu erhalten.
B.py
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
for j in range(w):
t[j][i]=s[i][j]
ans=0
for i in range(h):
for j in range(w-1):
if s[i][j]=="." and s[i][j+1]==".":
ans+=1
for i in range(w):
for j in range(h-1):
if t[i][j]=="." and t[i][j+1]==".":
ans+=1
print(ans)
C-Problem
Es ist ein Problem, $ mex $ zu finden, das häufig in Kodofo vorkommt. Das Array $ check $, das die Zahl speichert, die bis zum $ i $ th erscheint, und die Lösung am $ i $ th-Punkt (der Mindestwert unter den Zahlen, die nicht erscheinen), werden in $ mi $ gespeichert.
Zu diesem Zeitpunkt steigt ** $ mi $ monoton ** an. Wenn also $ check [mi]! = 0 $ ist, erhöhen Sie, bis $ mi $ gefunden wird, dh $ check [mi] = 0 $, und dann $ check. Wenn [mi] = 0 $ ist, sollte $ mi $ ausgegeben werden.
(Ich denke nicht, dass es so einfach ist, aber ich bin überrascht, dass viele Leute es durchmachen.)
C.py
n=int(input())
p=list(map(int,input().split()))
check=[0]*200001
mi=0
for i in range(n):
check[p[i]]+=1
while True:
if check[mi]>0:
mi+=1
else:
break
print(mi)
D Problem
Zunächst habe ich es falsch verstanden als **, um mehrere rote und blaue Quadrate ** zu setzen. Da es ein rotes und ein blaues Quadrat gibt, sollten Sie herausfinden, wie Sie das andere anordnen können, wenn eines fest ist, und es mit $ O (1) $ finden, indem Sie die Formel transformieren. Betrachten Sie nun ** das rote Quadrat zu fixieren und das blaue Quadrat ** als (eine Seite des roten Quadrats: A) $ \ geqq $ (eine Seite des blauen Quadrats: B) zu verschieben. Zu diesem Zeitpunkt wird angenommen, dass die untere linke Ecke des roten Quadrats bei $ (i, j) \ (0 \ leqq i \ <N-A, 0 \ leqq i \ <N-A) $ liegt.
Betrachten Sie dann die Anzahl der Fälle, in denen ein blaues Quadrat in den obigen roten, grünen, gelben und blauen Rechtecken enthalten ist. Wenn jeder der vier ** überlappenden Teile ein blaues Quadrat ** enthält, müssen Sie es subtrahieren. Hier sind der rechteckige Teil und der überlappende Teil jeweils ** gleich der Summe der Symmetrie **, so dass die Antwort durch Vervierfachen des folgenden roten Rechtecks minus des blauen Rechtecks erhalten werden kann.
(1) Über das rote Rechteck In Anbetracht der Breite des blauen Quadrats und des blauen Quadrats gilt $ B \ leqq i \ leqq N-A $. Zu diesem Zeitpunkt ist die Anzahl der enthaltenen blauen Quadrate
\begin{align}
&\sum_{i,j}(N-B-1)(i-B+1)\\
&=(N-B-1)\sum_{i,j}(i-B+1)\\
&=(N-B-1)\sum_{j}(\sum_{i}(i-B+1))\\
&=(N-B-1)\sum_{j}(1,2,…,N-A-B+1)\\
&=(N-B-1)\sum_{j}\frac{(N-A-B+1)(N-A-B+2)}{2}\\
&=(N-B-1)(N-A+1)\frac{(N-A-B+1)(N-A-B+2)}{2}\\
\end{align}
(2) Über das blaue Rechteck Zusätzlich zu $ B \ leqq i \ leqq N-A $ gilt auch $ B \ leqq j \ leqq N-A $. Zu diesem Zeitpunkt ist die Anzahl der enthaltenen blauen Quadrate
\begin{align}
&\sum_{i,j}(j-B-1)(i-B+1)\\
&=\sum_{i}(i-B+1)\times \sum_{j}(j-B+1)\\
&=(\frac{(N-A-B+1)(N-A-B+2)}{2})^2\\
\end{align}
Die obige Berechnung hängt von $ (j-B-1), (i-B + 1) $ und ** $ i, j $ ** ab, daher verwenden wir die Trennung als Summe. Beachten Sie, dass einer der Begriffe, der $ i, j $ enthält, nicht getrennt werden kann.
Sie können es finden, indem Sie das obige (1) minus (2) vervierfachen. Wenn Sie Python verwenden, müssen Sie sich keine Gedanken über einen Überlauf machen, da es sich um eine Ganzzahl mit mehreren Längen handelt, und schließlich den Rest geteilt durch $ 10 ^ 9 + 7 $ finden.
D.py
mod=10**9+7
for _ in range(int(input())):
n,a,b=map(int,input().split())
if a<b:
a,b=b,a
x=(n-a-b+1)*(n-a-b+2)//2*(n-a+1)*(n-b+1)*4
y=((n-a-b+1)*(n-a-b+2)//2)**2*4
if a+b>n:
print(0)
continue
print((x-y)%mod)
E Problem
Ich bin froh, dass ich in der eigentlichen Produktion sofort von D wechseln konnte. Ich bin froh, dass die Implementierung unkompliziert war, ohne zu viele Fehler zu verursachen.
Da es sich um die Summe handelt, überlegen Sie zunächst, wie oft das beleuchtete Quadrat in der Straße $ 2 ^ k $ erscheint ** (** achten Sie auf die Anzahl der Elemente! **). Wenn hier ein bestimmtes Quadrat beleuchtet wird, wird das beleuchtete Quadrat von diesem Quadrat zu einem durchgehenden und übersichtlichen Quadrat. Wenn mehrere Quadrate beleuchtet werden, ist es hier möglich, ein Quadrat mit mehreren Lichtern zu beleuchten. Zu diesem Zeitpunkt ist es notwendig, diese Zelle einmal zur Lösung hinzuzufügen, daher nahm ich an, dass ** diese Zelle von $ x $ Lichtern beleuchtet wurde ** und überlegte, wie oft diese Zelle als beleuchtete Zelle erscheinen würde .. Wenn eines der ** $ x $ -Lichter leuchtet, leuchtet dieses Quadrat **. Daher gibt es $ 2 ^ k $ Möglichkeiten, die Zellen für den Beweis auszuwählen, und $ 2 ^ {kx} $ Möglichkeiten, keine der $ x $ -Zellen auszuwählen, sodass mindestens eine $ 2 ^ k-2 ^ ist {kx} $ street ($ \ weil $ Wrapping-Prinzip).
Daher kann die Summe durch $ O (HW) $ berechnet werden, indem die Anzahl der von jeder Zelle beleuchteten Zellen berechnet und die Vorquadratberechnung durchgeführt wird. Hier ** teilen sich die Zellen, die eine bestimmte Zelle beleuchten, eine Zeile oder Spalte **, und das Gleiche gilt, wenn die Matrix transponiert wird. Wie viele Zellen **, die eine Zeile teilen **, werden beleuchtet? Denken wir zuerst nach.
Wenn sich in einer Reihe $ y $ aufeinanderfolgende übersichtliche Zellen befinden, ** beträgt die Anzahl der Zellen, die für eine darin enthaltene Zelle gemeinsam genutzt und beleuchtet werden, $ y $ **. .. Verwenden Sie daher die Groupby-Funktion itertools (Referenz), um eine kontinuierliche, übersichtliche Masse zu erstellen. Zusammenfassend kann $ O (HW) $ verwendet werden, um $ y $ in jeder Zelle zu finden. Finden Sie auf ähnliche Weise heraus, wie viele der Quadrate, die sich die Spalte teilen, beleuchtet sind, und subtrahieren Sie 1 von der Wertschöpfung zu $ y $ ($ , weil $ ** dieses Quadrat zweimal zählt **). Ja) Sie können $ x $ in jeder Zelle finden.
E.py
mod=10**9+7
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
k=0
for i in range(h):
for j in range(w):
if s[i][j]==".":
k+=1
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
for j in range(w):
t[j][i]=s[i][j]
po=[0]*(k+1)
po[0]=1
for i in range(1,k+1):
po[i]=po[i-1]*2
po[i]%=mod
#Der Teil, der durch eine Linie verbunden ist
from itertools import groupby
check=[[0]*w for i in range(h)]
for i in range(h):
now=0
for key,group in groupby(s[i]):
l=len(list(group))
if key=="#":
now+=l
else:
for j in range(now,now+l):
check[i][j]+=l
now+=l
for i in range(w):
now=0
for key,group in groupby(t[i]):
l=len(list(group))
if key=="#":
now+=l
else:
for j in range(now,now+l):
check[j][i]+=l
now+=l
ans=0
for i in range(h):
for j in range(w):
#print(k,k-check[i][j])
if check[i][j]!=0:
ans+=(po[k]-po[k-check[i][j]+1])
ans%=mod
print(ans)
F Problem
Ich werde diesmal überspringen.
Recommended Posts