Break through in 1 minute. Just write
S, T = input().split()
print(T + S)
Break through in 6 minutes. Just write. At first I didn't understand the meaning of the sentence, so I thought I would reduce K sheets in both cases, but I tried the input / output example and realized the correct meaning.
A, B, K = map(int, input().split())
a = max(A - K, 0)
K -= A - a
b = max(B - K, 0)
print(*[a, b])
Break through in 7 minutes. Just bring the Eratosthenes sieve written in ABC084D --2017-like Number and write it.
from math import sqrt
N = 10 ** 6
p = [True] * (N + 1)
p[0] = False
p[1] = False
n = int(sqrt(N) + 1)
for j in range(4, N + 1, 2):
p[j] = False
for i in range(3, n + 1, 2):
if p[i]:
for j in range(i + i, N + 1, i):
p[j] = False
X = int(input())
for i in range(X, N + 1):
if p[i]:
print(i)
break
ABC149D - Prediction and Restriction
Break through in 44 minutes. WA1. Let's proceed on the premise that we will win the game for the time being, and if we implement it so that if we get the same hand as the previous K hand, WA will come out and we will have to DP. But isn't it the number of people who break through (rotten reasoning)? ”I was worried for a long time and realized that it might be better to lose. AC. Because of that, the ranking was in the 1400s. I felt that I was saved because I was unrated.
N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()
d = {'r': P, 's': R, 'p': S}
result = 0
wins = [False] * K
for i in range(len(T)):
if not wins[i % K] or T[i] != T[i - K]:
result += d[T[i]]
wins[i % K] = True
else:
wins[i % K] = False
print(result)
I couldn't break through. I couldn't think of a way to devalue the order and ended with the TLE full.
Addendum: It is impossible to generate all combinations because the amount of calculation is * O * (10 10 </ sup>), so even if you try to keep the generated combinations to M, M is also stuck at 10 10 </ sup>. So, reverse the idea and find the threshold of happiness that occurs once the number of combinations exceeds M by binary search. This is the cumulative sum. It can be calculated with * O * ( N </ i> log N </ i>).
Once this is found, turn the loop based on the left hand, know how far the right hand can be lowered from the cumulative sum created earlier, and create another cumulative sum of the power of the right hand * O * (* N *) However, since the number of combinations is not exactly M, it is necessary to subtract the threshold value of happiness that occurs at one time as much as it exceeds M. ..
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
LB = A[-1] * 2 #The lower limit of happiness that can be raised by one handshake is when you hold the person with the lowest power in both your left and right hands.
UB = A[0] * 2 #The upper limit of happiness that can be raised by one handshake is when you hold the person with the highest power in both your left and right hands.
# cgs[i]Is the number of guests with power i or greater
cgs = [0] * (UB + 1)
for a in A:
cgs[a] += 1
for i in range(UB, 0, -1):
cgs[i - 1] += cgs[i]
#Binary search for the threshold of happiness that occurs once the number of combinations is M or more
def is_ok(n):
m = 0
for a in A:
m += cgs[max(n - a, 0)]
return m >= M
ok = LB
ng = UB + 1
while ng - ok > 1:
m = (ok + ng) // 2
if is_ok(m):
ok = m
else:
ng = m
# cps[i]Is A[0]～A[i]Cumulative sum of
cps = A[:]
for i in range(1, N):
cps[i] += cps[i - 1]
result = 0
for a in A:
t = cgs[max(ok - a, 0)]
if t != 0:
result += a * t + cps[t - 1]
M -= t
result += ok * M
print(result)
Recommended Posts