[PYTHON] concours yukicoder 267 avis

résultat

Impressions

B Le problème a été ** mal lu par inadvertance **…. Puisque le problème C est une sous-chaîne, j'ai essayé d'utiliser DP, mais je ne pouvais pas penser avec précision à cause de l'impatience du problème B.

Problème A

Si la main longue et la main courte se chevauchent à $ x $ heure $ y $ seconde, l'équation suivante est valable.

De plus, puisque $ x $ peut être considéré comme un reste de 12, $ x = 0 $ à 11, et selon la formule ci-dessus, ** $ y $ est calculé comme une valeur tronquée, donc le $ x donné Déterminez si la valeur de $ y $ donnée pour $ est antérieure à l'heure qui chevauche la plage de temps $ x $.

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))

Problème B

C'est un problème qui peut être résolu en lisant attentivement l'énoncé du problème. Je pensais avoir été formé avec Kodofo, mais je suis trop prudent ...

Si vous le lisez attentivement, vous trouverez le reste de ** 10 $ ^ 9 + 7 $ divisé par la réponse **, donc quand $ A \ _k \ geqq 4 $, $ A \ _k ^ {A \ _k!}> 10 ^ 9 + 7 Puisqu'il s'agit de $, le reste sera de 10 $ ^ 9 + 7 $. De plus, si ** $ A \ _k = 0 $ lors de la multiplication, les autres nombres sont arbitraires et la réponse est 0 **. Par conséquent, lorsque $ A \ _ {min} = 0 $, -1 est affiché (lorsque $ A \ _ {min} \ neq 0 $, la réponse n'est pas 0 et la division est possible.) ..

D'après ce qui précède, -1 est généré lorsque $ A \ _ {min} = 0 $, 10 $ ^ 9 + 7 $ est généré lorsque $ A_ {max}> 3 $, et le calcul est simple dans les autres cas. En faisant chacun, la réponse sera la suivante.

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)

Problème C

Puisqu'il s'agit d'une sous-colonne, il est typique que ** $ dp [i]: = $ (quelque chose pour le sous-ensemble du set jusqu'à $ i $) et il y a deux façons d'inclure ou de ne pas inclure la transition **. Modèle. Cette fois, la moyenne est de $ k $ ou plus et la moyenne dépend du nombre de personnes, il semble donc nécessaire d'avoir DP tout en ayant des informations sur le score et le nombre de personnes. Cependant, compte tenu de la quantité de calcul, il est difficile d'avoir les deux, et nous envisagerons ici de ** supprimer les informations sur le nombre de personnes **. En d'autres termes, ** en fixant le score de chaque personne à $ -k $ à l'avance **, nous vérifierons si le score total des étudiants inclus dans le sous-ensemble est égal ou supérieur à 0 **. Par conséquent, nous pourrions avoir des informations comme condition ** que le score du sous-ensemble ne dépend pas du nombre d'éléments de l'ensemble **, donc tout ce que nous avons à faire est de mettre le DP comme suit.

$ dp [i] [j]: = $ (nombre lorsque le score total des sous-ensembles de l'ensemble jusqu'à $ i $ est $ j $)

De plus, $ -k $ peut rendre $ j $ négatif, donc si vous mettez des sabots jusqu'à 10000, ce qui peut être la valeur minimale, vous obtiendrez le DP suivant.

$ dp [i] [j]: = $ (nombre lorsque le score total des sous-ensembles de l'ensemble jusqu'à $ i $ est $ j-10000 $)

Et la transition est la suivante.

(1) Lorsque l'élément $ i $ th n'est pas sélectionné dp[i][j]+=dp[i-1][j]

(2) Lors de la sélection de l'élément $ i $ th dp[i][j+a[i]]+=dp[i-1][j] Cependant, $ 0 \ leqq j + a [i] \ leqq 20000 $ De plus, il y a des cas où seul l'élément $ i $ th est défini, et $ dp [i] [a [i] + 10000] + = 1 $

Après avoir effectué les transitions ci-dessus, nous voulons enfin trouver le nombre lorsque le total est égal ou supérieur à 0, donc ce sera $ sum (dp [n-1] [10000:]) $. Notez également que ** vous voulez le reste ** divisé par 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]
#somme(Indice négatif)
print(sum(dp[-1][10000:])%mod)

Problème après D

Je ne résoudrai pas cette fois.