[PYTHON] AtCoder Judge System Update Testwettbewerb 202004 Teilnahmebericht

AtCoder Judge System Update Testwettbewerb 202004 Teilnahmebericht

Es ist die erste vollständige Fertigstellung, und das Ranking liegt auch bei den besten 9%. Warum wird es nicht bewertet? (Bang Bang Desk).

A - Walking Takahashi

Durchbruch in 2 Minuten. Wenn die Sonne bereits aufgegangen ist, antwortet die aktuelle Position. Wenn die aktuelle Position kleiner als L ist, antwortet L und wenn die aktuelle Position R überschreitet, antwortet R.

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

Brechen Sie in 6 Minuten durch. Sortieren Sie R und B, zeigen Sie R in aufsteigender Reihenfolge an und zeigen Sie B in aufsteigender Reihenfolge an. Natürlich sortieren Sie einfach in aufsteigender Reihenfolge.

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

Brechen Sie in 12 Minuten durch. N ist höchstens 9, also müssen Sie nur eine Runde machen. Itertools.permutations Ich liebe dich.

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

Brechen Sie in 23,5 Minuten durch. Wenn Sie Naive machen, nehmen Sie TLE. X mit * O * (10 </ sup> 10 </ sup>), um alle A und GCD zu nehmen, nehmen Sie alle GCDs von A und GCDs von X. Gleich wie. Wenn X nicht 1 wird, wird es * O * (10 5 </ sup>) und es wird gelöscht. Dies ist die Anzahl der Operationen, wenn X 1 wird, aber die GCD von A wird in der richtigen Reihenfolge genommen. Nur die geänderten Teile sind Kandidaten, überprüfen Sie also nur die geänderten Teile. Ich weiß nicht, wie stark die Bestellung sinken wird, aber intuitiv sollte sie stark sinken. Wenn Sie sie also einreichen, ist sie sicher.

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

Nachtrag: Es scheint, dass jeder es löst, also habe ich versucht, es sogar mit Nibutan w zu lösen

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)