I was so sleepy that I took a nap for 20 minutes just before and did my best.
aising2020A - Number of Multiples
Break through in one and a half minutes. Just write according to the conditions of the problem. It takes time, so I do not think about solving it with * O * (1).
L, R, d = map(int, input().split())
result = 0
for i in range(L, R + 1):
if i % d == 0:
result += 1
print(result)
Postscript: * O * (1)
L, R, d = map(int, input().split())
print(R // d - (L - 1) // d)
Break through in 2 minutes. Just write according to the conditions of the problem.
N = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(N):
if (i + 1) % 2 == 1 and a[i] % 2 == 1:
result += 1
print(result)
Postscript: I should have skipped even-numbered slices ...
N, *a = map(int, open(0).read().split())
print(sum(1 for e in a[::2] if e % 2 == 1))
It broke through in 6 and a half minutes. N ≤ 10 4 </ sup> So I thought it would pass even in a triple loop. In fact, it passed.
N = int(input())
result = [0] * (N + 1)
for x in range(1, 101):
for y in range(1, 101):
for z in range(1, 101):
n = x * x + y * y + z * z + x * y + y * z + z * x
if n > N:
break
result[n] += 1
print(*result[1:], sep='\n')
aising2020D - Anything Goes to Zero
I couldn't break through. When A = B * C, I thought that I could get a large number of remainders using A% m = (B% m) * (C% m)% m, so I built it using it, but TLE I'm not sure because I get the RE and the RE. The first process can be * O * (1) by pre-calculation, but what should I do after the second?
Addendum: The maximum value returned by * f * (* n ) is log 2 </ sub> ( n *), so 2 2 × 10 5 </ sup> </ sup > → 2 × 10 5 </ sup> → 17.6 → 4.1 → 2.0 → 1 → 0 and it converges in a blink of an eye. So I should have managed it only the first time. Look at TLE * f * ( It was stupid to run to speed up * n *).
RE was originally issued when only one bit was set, and when the only set bit was inverted, * popcount * was not noticed to be 0, and it was divided by 0. TLE Was displayed in log 2 </ sub> (* X *) without being aware that it was 2 × 10 5 </ sup> * O * ( N </ i> > log X </ i>) because it was written.
Although the idea was correct, I felt that I could not solve it due to some omissions.
def popcount(n):
return bin(n).count("1")
def f(n):
if n == 0:
return 0
return 1 + f(n % popcount(n))
N = int(input())
X = input()
c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
if X[i] == '0':
continue
x1 += t1[N - 1 - i]
if c - 1 != 0:
t2 = [0] * N
t2[0] = 1 % (c - 1)
for i in range(1, N):
t2[i] = (t2[i - 1] << 1) % (c - 1)
x2 = 0
for i in range(N):
if X[i] == '0':
continue
x2 += t2[N - 1 - i]
result = []
for i in range(N):
if X[i] == '0':
n = (x1 + t1[N - 1 - i]) % (c + 1)
elif X[i] == '1':
if c - 1 == 0:
result.append(0)
continue
n = (x2 - t2[N - 1 - i]) % (c - 1)
result.append(1 + f(n))
print(*result, sep='\n')
Recommended Posts