[PYTHON] Yukicoder-Wettbewerb 267 Bewertung

Ergebnis

Impressionen

B Problem wurde ** versehentlich falsch verstanden **…. Da das C-Problem ein Teilstring ist, habe ich versucht, DP zu verwenden, konnte aber aufgrund der Ungeduld des B-Problems nicht genau denken.

Problem A

Wenn sich die lange und die kurze Hand bei $ x $ Stunde $ y $ Sekunde überlappen, gilt die folgende Gleichung.

Da $ x $ als Rest von 12 betrachtet werden kann, ist $ x = $ 0 bis 11, und gemäß der obigen Formel wird ** $ y $ als abgeschnittener Wert berechnet, also das gegebene $ x Überlegen Sie, ob der für $ angegebene Wert von $ y $ vor der Zeit liegt, die den Zeitbereich von $ x $ überlappt.

A.py

cand=[60*i*60//11 for i in range(12)]
a,b=map(int,input().split())
a%=12
b*=60
if cand[a]>=b:
    print(int(cand[a]-b))
else:
    a=(a+1)%12
    print(int(cand[a]+3600-b))

B-Problem

Es ist ein Problem, das durch sorgfältiges Lesen der Problemstellung gelöst werden kann. Ich dachte, ich wäre mit Kodofo trainiert worden, aber ich bin zu vorsichtig ...

Wenn Sie es sorgfältig lesen, finden Sie den Rest von ** $ 10 ^ 9 + 7 $ geteilt durch die Antwort **. Wenn also $ A \ _k \ geqq 4 $, $ A \ _k ^ {A \ _k!}> 10 ^ 9 + 7 Da es $ ist, beträgt der Rest $ 10 ^ 9 + 7 $. Wenn beim Multiplizieren ** $ A \ _k = 0 $ ist, sind die anderen Zahlen beliebig und die Antwort lautet 0 **. Wenn also $ A \ _ {min} = 0 $ ist, wird -1 ausgegeben (wenn $ A \ _ {min} \ neq 0 $ ist, ist die Antwort nicht 0 und eine Division ist möglich.) ..

Aus dem Obigen wird -1 ausgegeben, wenn $ A \ _ {min} = 0 $, $ 10 ^ 9 + 7 $ ausgegeben, wenn $ A_ {max}> 3 $, und die Berechnung ist in anderen Fällen einfach. In jedem Fall lautet die Antwort wie folgt.

B.py

n=int(input())
a=list(map(int,input().split()))
#Gag
mod=10**9+7
if min(a)==0:
    print(-1)
    exit()
if max(a)>3:
    print(mod)
    exit()
ans=1
for i in a:
    sub=1
    for j in range(i):
        sub*=(j+1)
    ans*=(i**sub)
    if ans>10**9+7:
        print(mod)
        exit()
print(mod%ans)

C-Problem

Da es sich um eine Unterspalte handelt, ist es typisch, dass ** $ dp [i]: = $ (etwas für die Teilmenge der Menge bis zu $ i $) und es gibt zwei Möglichkeiten, den Übergang einzuschließen oder nicht einzuschließen **. Muster. Diesmal beträgt der Durchschnitt $ k $ oder mehr und der Durchschnitt hängt von der Anzahl der Personen ab. Daher scheint es notwendig zu sein, DP zu haben, während Informationen sowohl über die Punktzahl als auch über die Anzahl der Personen vorliegen. In Anbetracht des Rechenaufwands ist es jedoch schwierig, beides zu haben, und hier werden wir in Betracht ziehen, ** die Informationen über die Anzahl der Personen zu löschen **. Mit anderen Worten, ** indem wir die Punktzahl jeder Person im Voraus auf $ -k $ setzen **, prüfen wir, ob die Gesamtpunktzahl der in der Teilmenge enthaltenen Schüler 0 oder mehr beträgt **. Daher könnten wir Informationen als Bedingung ** haben, dass die Punktzahl der Teilmenge nicht von der Anzahl der Elemente der Menge ** abhängt. Wir müssen also nur den DP wie folgt setzen.

$ dp [i] [j]: = $ (Zahl, wenn die Gesamtpunktzahl der Teilmengen des Satzes bis $ i $ $ j $ beträgt)

Außerdem kann $ -k $ $ j $ negativ machen. Wenn Sie also bis zu 10000 eingeben, was der Mindestwert sein kann, erhalten Sie den folgenden DP.

$ dp [i] [j]: = $ (Zahl, wenn die Gesamtpunktzahl der Teilmengen des Satzes bis zu $ i $ $ j-10000 $ beträgt)

Und der Übergang ist wie folgt.

(1) Wenn das $ i $ -te Element nicht ausgewählt ist dp[i][j]+=dp[i-1][j]

(2) Bei Auswahl des $ i $ -ten Elements dp[i][j+a[i]]+=dp[i-1][j] $ 0 \ leqq j + a [i] \ leqq 20000 $ Es gibt auch Fälle, in denen nur das $ i $ -te Element gesetzt ist und $ dp [i] [a [i] + 10000] + = 1 $

Nachdem wir die obigen Übergänge vorgenommen haben, möchten wir endlich die Zahl finden, wenn die Summe 0 oder mehr ist, also ist es $ sum (dp [n-1] [10000:]) $. Beachten Sie auch, dass ** Sie nach dem Rest suchen ** geteilt durch $ 10 ^ 9 + 7 $.

C.py

mod=10**9+7
n,k=map(int,input().split())
a=[i-k for i in list(map(int,input().split()))]
dp=[[0]*20001 for i in range(n)]
dp[0][a[0]+10000]=1
for i in range(1,n):
    for j in range(20001):
        dp[i][j]=dp[i-1][j]
    dp[i][a[i]+10000]+=1
    for j in range(20001):
        dp[i][j]%=mod
        if 0<=j+a[i]<=20000:
            dp[i][j+a[i]]+=dp[i-1][j]
#Summe(Negativer Index)
print(sum(dp[-1][10000:])%mod)

Nach D Problem

Ich werde diesmal nicht lösen.