[PYTHON] yukicoder contest 267 Review

result

Impressions

B Problem was ** inadvertently misread **…. Since the C problem is a subsequence, I tried to use DP, but I couldn't think accurately because of the impatience of the B problem.

Problem A

If the long hand and the short hand overlap at $ x $ hour $ y $ second, the following equation holds.

Also, $ x $ can be thought of as a remainder of 12, so $ x = $ 0 to 11, and according to the above formula, ** $ y $ is calculated as the truncated value, so the given $ x Consider whether the value of $ y $ given for $ is before the time that overlaps the $ x $ time range.

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

It is a problem that can be solved by reading the problem statement carefully. I thought I was trained with Kodofo, but I'm too careful ...

If you read it carefully, you will find the remainder of ** $ 10 ^ 9 + 7 $ divided by the answer **, so when $ A \ _k \ geqq 4 $, $ A \ _k ^ {A \ _k!}> 10 ^ 9 + 7 Since it is $, the remainder will be $ 10 ^ 9 + 7 $. Also, if ** $ A \ _k = 0 $ when multiplying, the other numbers are arbitrary and the answer is 0 **. Therefore, when $ A \ _ {min} = 0 $, -1 is output (when $ A \ _ {min} \ neq 0 $, the answer is not 0 and division is possible.) ..

From the above, -1 is output when $ A \ _ {min} = 0 $, $ 10 ^ 9 + 7 $ is output when $ A_ {max}> 3 $, and the calculation is straightforward in other cases. By doing each, the answer will be as follows.

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

Since it is a subsequence, it is typical that ** $ dp [i]: = $ (something for the subset of the set up to $ i $) is included or not included **. Pattern. This time, the average is $ k $ or more and the average depends on the number of people, so it seems necessary to have DP while having information on both the score and the number of people. However, considering the amount of calculation, it is difficult to have both, and here we consider ** deleting the information on the number of people **. In other words, ** by setting each person's score to $ -k $ in advance **, we will check whether the total score of the students included in the subset is 0 or more **. Therefore, we could have information as a condition ** that the score of the subset does not depend on the number of elements of the set **, so all we have to do is put the DP as follows.

$ dp [i] [j]: = $ (number when the total score of the subsets of the set up to the $ i $ th is $ j $)

Also, $ -k $ can make $ j $ negative, so if you put on clogs as much as 10000, which can be the minimum value, you will get the following DP.

$ dp [i] [j]: = $ (number when the total score of the subsets of the set up to the $ i $ th is $ j-10000 $)

And the transition is as follows.

(1) When the $ i $ th element is not selected dp[i][j]+=dp[i-1][j]

(2) When selecting the $ i $ th element dp[i][j+a[i]]+=dp[i-1][j] However, $ 0 \ leqq j + a [i] \ leqq 20000 $ Also, there are cases where only the $ i $ th element is set, and $ dp [i] [a [i] + 10000] += 1 $

After performing the above transitions, we want to finally find the number when the total is 0 or more, so it will be $ sum (dp [n-1] [10000:]) $. Also note that ** you are looking for the remainder ** divided by $ 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]
#sum(Negative index)
print(sum(dp[-1][10000:])%mod)

After D problem

I will not solve this time.