This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
The string T is the question of answering whether the string S has a single character at the end.
We compared by slicing T with T [: -1].
S = input()
T = input()
if S == T[:-1]:
print('Yes')
else:
print('No')
There are $ A $ for cards labeled 1, $ B $ for cards labeled 0, and $ C $ for cards labeled -1. The maximum value when choosing $ K $ from this is a question to answer.
Priority should be given to counting in the order of 1, 0, -1. However, since it is $ A, B, C \ leq2 \ times10 ^ 9 $, it will hurt if you try to put it in an array or turn it with for. (One loss)
A, B, C, K = map(int, input().split())
out = min(A, K) - max(0, K-A-B)
print(out)
The problem is to find the lowest price in a combination where all the elements summed for each number exceed $ X $.
The limit of $ N, M \ leq 12 $ allows for full coverage. Parallel computing was done by using ʻitertools.product ()and thennumpy` for the full search.
import itertools
import numpy as np
N, M, X = map(int, input().split())
items = np.array([list(map(int, input().split())) for _ in range(N)], dtype=np.int32)
out = 10**18
for c in itertools.product([False, True], repeat=N):
tmp = np.sum(items[np.where(c)], axis=0)
if M == np.count_nonzero(tmp[1:] >= X):
out = min(out, tmp[0])
if out == 10**18:
print(-1)
else:
print(out)
Each town has one warp destination. The question is to teleport K times from the first town and answer the town to arrive.
If you search properly from the limit of $ K \ leq10 ^ {18} $, it is TLE. I gave up. See other people's answers.
It should be noted that the range of K is $ K \ leq 10 ^ {18} $, but the range of N is $ N \ leq 2 \ times 10 ^ {5} $. In other words, this search always loops.
First, search normally. Save the time t_zero that first arrived at each town as an array, and calculate the time for one lap when you reach the same town a second time. Take the remainder term of the time of one lap from K. Reuse the previously done calculations without having to search again for the remaining time k. I passed with the following code.
N, K = map(int, input().split())
A = list(map(int, input().split()))
t_zero = [-1] * N
t = 0
a = 1
while t_zero[a-1] == -1:
if t == K:
break
t_zero[a-1] = t
t += 1
a = A[a-1]
else:
k = (K - t_zero[a-1]) % (t - t_zero[a-1])
a = t_zero.index(t_zero[a-1] + k) + 1
print(a)
It is a problem to color-code the blocks arranged in a horizontal row. However, the same color can be allowed to be next to each other up to K, and how many combinations are there?
There are $ M \ times (M-1) ^ {N-1} $ combinations in which N colors are arranged so that the M colors are not next to each other.
When K group blocks can be next to each other, it can be said that $ N-K $ blocks are arranged so that the colors do not line up. Also, how to select the combination of adjacent blocks is $ _ {N-1} C _ {K} $ pieces.
In other words, you can calculate the following formula.
The implementation is as follows. However, during the production, I could not speed up the calculation well and could not solve it in time.
N, M, K = map(int, input().split())
out = 0
mod = 998244353
c = 1
for k in range(K+1):
out += M * pow(M-1, N-k-1, mod) * c
out %= mod
c *= (N-k-1) * pow(k+1, mod-2, mod)
c %= mod
print(out)
here
That's all for this article.
Recommended Posts