[PYTHON] AtCoder Judge System Update Test Contest 202004 Participation Report

AtCoder Judge System Update Test Contest 202004 Participation Report

It's the first complete completion, and the ranking is also the top 9%. Why isn't it rated! (Desk bang bang).

A - Walking Takahashi

Break through in 2 minutes. If the sun has already hit, the current position answers. If the current position is less than L, L answers, and if the current position exceeds R, R answers.

S, L, R = map(int, input().split())

if L <= S <= R:
    print(S)
elif S < L:
    print(L)
elif S > R:
    print(R)

B - Picking Balls

Break through in 6 minutes. Sort R and B, display R in ascending order, then display B in ascending order. Of course, sort in ascending order.

N = int(input())

R = []
B = []
for _ in range(N):
    X, C = input().split()
    if C == 'R':
        R.append(int(X))
    elif C == 'B':
        B.append(int(X))

R.sort()
B.sort()
if R:
    print('\n'.join(str(r) for r in R))
if B:
    print('\n'.join(str(b) for b in B))

C - Numbering Blocks

Break through in 12 minutes. N is 9 at most, so all you have to do is brute force. Itertools.permutations I love you.

from itertools import permutations

a1, a2, a3 = map(int, input().split())
a = [a1, a2, a3]

N = a1 + a2 + a3
result = 0
for p in permutations(range(1, N + 1)):
    X = [p[:a1], p[a1:a1 + a2], p[a1 + a2:]]
    flag = True
    for i in range(3):
        for j in range(1, a[i]):
            if X[i][j] <= X[i][j - 1]:
                flag = False
    for i in range(1, 3):
        for j in range(a[i]):
            if X[i][j] <= X[i - 1][j]:
                flag = False
    if flag:
        result += 1
print(result)

D - Calculating GCD

Break through in 23 and a half minutes. If you do naive, take TLE. X with * O * (10 ^{10 </ sup>) to take all A and GCD, take all A's GCD and X's GCD Same as. If X does not become 1, then it becomes * O * (10 5 </ sup>) and it is cleared up. The number of operations when X becomes 1, but the GCD of A is taken in order. Since only the changed parts are candidates, check only the changed parts. It is unknown how much the order will be lowered by this, but intuitively it should be greatly reduced, so if you submit it, it will be safe AC.}

from math import gcd

N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = list(map(int, input().split()))

gcd_a = A[0]
a = [(1, A[0])]
for i in range(1, N):
    t = gcd(gcd_a, A[i])
    if t != gcd_a:
        gcd_a = t
        a.append((i + 1, gcd_a))

for i in range(Q):
    X = S[i]
    t = gcd(gcd_a, X)
    if t != 1:
        print(t)
    else:
        for j, g in a:
            if gcd(X, g) != 1:
                continue
            print(j)
            break

Postscript: It seems that everyone is solving it, so I tried to solve it even with a pig.

from math import gcd

N, Q = map(int, input().split())
A = list(map(int, input().split()))
S = list(map(int, input().split()))

for i in range(N - 1):
    A[i + 1] = gcd(A[i + 1], A[i])

for i in range(Q):
    X = S[i]
    t = gcd(A[-1], X)
    if t != 1:
        print(t)
    else:
        ng = -1
        ok = N - 1
        while ok - ng > 1:
            m = (ok + ng) // 2
            if gcd(X, A[m]) == 1:
                ok = m
            else:
                ng = m
        print(ok + 1)