yukicoder contest 267 Review

result

スクリーンショット 2020-09-26 13.00.35.png

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.

\frac{y}{60} \times 360 \div 60=\frac{x}{12} \times 360 + \frac{y}{60} \times 30 \div 60 \leftrightarrow y=60 \times 60 \times x \div 11

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.

Recommended Posts

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review