AtCoder 1st Algorithm Practical Test Virtual Participation Report

AtCoder 1st Algorithm Practical Test Virtual Participation Report

I finally got some time, so I tried virtual participation in PAST. The result was 64 points, so it was intermediate (60-79 points). There were a lot of subtly annoying problems, and I felt that the coat color was a little different.

past201912A-Double check

Break through in 3 and a half minutes. Check if it is only a number, and if it is OK, convert it to int and output it at double.

S = input()

for i in range(3):
    if S[i] not in '0123456789':
        print('error')
        exit()
print(int(S) * 2)

past201912B --Increase / decrease management

Break through in 7 minutes. Just compare with the previous value and output.

N = int(input())
A = [int(input()) for _ in range(N)]

prev = A[0]
for i in range(1, N):
    if A[i] == prev:
        print('stay')
    elif A[i] < prev:
        print('down %d' % (prev - A[i]))
    elif A[i] > prev:
        print('up %d' % (A[i] - prev))
    prev = A[i]

past201912C --Third

Break through in 2 minutes. Just sort in descending order and output the third value from the front.

ABCDEF = list(map(int, input().split()))

ABCDEF.sort(reverse=True)
print(ABCDEF[2])

past201912D --Duplicate inspection

Break through in 11 minutes. Just count the number of appearances in the dictionary, identify 0 and 2 things, and output.

N = int(input())
A = [int(input()) for _ in range(N)]

t = set(A)
if len(t) == N:
    print('Correct')
    exit()

d = {}
for i in range(N):
    if A[i] in d:
        d[A[i]] += 1
    else:
        d[A[i]] = 1

for i in range(1, N + 1):
    if i not in d:
        x = i
    elif d[i] == 2:
        y = i

print(y, x)

past201912E --SNS log

Breakthrough in 24 minutes. The implementation of follow follow has also added the users who are following the follow that increased during processing, and it took time for input example 1 to not pass. Input example 1 caught it. I think it would have taken longer if they didn't.

N, Q = map(int, input().split())

t = [['N'] * N for _ in range(N)]
for _ in range(Q):
    S = input()
    if S[0] == '1':
        _, a, b = map(int, S.split())
        t[a - 1][b - 1] = 'Y'
    elif S[0] == '2':
        _, a = map(int, S.split())
        for i in range(N):
            if t[i][a - 1] == 'Y':
                t[a - 1][i] = 'Y'
    elif S[0] == '3':
        _, a = map(int, S.split())
        for i in [i for i in range(N) if t[a - 1][i] == 'Y']:
            for j in range(N):
                if t[i][j] == 'Y' and j != a - 1:
                    t[a - 1][j] = 'Y'

for i in range(N):
    print(''.join(t[i]))

past201912F - DoubleCamelCase Sort

Break through in 7 minutes. There is nothing particularly difficult, just cut out the words, sort them in case, and combine them.

S = input()

t = []
start = -1
for i in range(len(S)):
    if S[i].isupper():
        if start == -1:
            start = i
        else:
            t.append(S[start:i+1])
            start = -1
t.sort(key=str.lower)
print(''.join(t))

past201912G --Grouping

It broke through in 20 minutes. I thought I didn't know at first, but when I looked closely, I could go brute force because N ≤ 10. Since there are 3 groups, I couldn't search all bits, and I implemented an int array to carry forward. It wasn't particularly difficult.

N = int(input())
a = [list(map(int, input().split())) for _ in range(N - 1)]

result = -float('inf')
t = [0] * N
for _ in range(3 ** N):
    s = 0
    for i in range(N):
        for j in range(i + 1, N):
            if t[i] == t[j]:
                s += a[i][j - i - 1]
    result = max(result, s)
    for i in range(N):
        if t[i] < 2:
            t[i] += 1
            break
        t[i] = 0
print(result)

past201912H --Bulk sale

Break through in 44 minutes and a half. Since it is inevitable that TLE will be reflected in the array both set sales and all types sales because of the restrictions, I made a cumulative variable for each and passed it with a policy of matching Tsuji. It took me a long time to notice that ʻodd_min-= a` leaked out.

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

all_min = min(C)
odd_min = min(C[::2])
all_sale = 0
odd_sale = 0
ind_sale = 0
for _ in range(Q):
    S = input()
    if S[0] == '1':
        _, x, a = map(int, S.split())
        t = C[x - 1] - all_sale - a
        if x % 2 == 1:
            t -= odd_sale
        if t >= 0:
            ind_sale += a
            C[x - 1] -= a
            all_min = min(all_min, t)
            if x % 2 == 1:
                odd_min = min(odd_min, t)
    elif S[0] == '2':
        _, a = map(int, S.split())
        if odd_min >= a:
            odd_sale += a
            odd_min -= a
            all_min = min(odd_min, all_min)
    elif S[0] == '3':
        _, a = map(int, S.split())
        if all_min >= a:
            all_sale += a
            all_min -= a
            odd_min -= a
print(all_sale * N + odd_sale * ((N + 1) // 2) + ind_sale)

past201912I --Parts Procurement

It breaks through in 14 minutes. It's DP, so it's not particularly difficult. Just convert Y to 1 and N to 0, which is regarded as a bit of each digit, and then DP.

N, M = map(int, input().split())


def conv(S):
    result = 0
    for c in S:
        result *= 2
        if c == 'Y':
            result += 1
    return result


dp = [-1] * 2001
dp[0] = 0
for _ in range(M):
    S, C = input().split()
    S = conv(S)
    C = int(C)
    for i in range(2000, -1, -1):
        if dp[i] == -1:
            continue
        if dp[i | S] == -1 or dp[i | S] > dp[i] + C:
            dp[i | S] = dp[i] + C
print(dp[(1 << N) - 1])

past201912J --Ground Leveling

I couldn't break through. Find the cheapest route from the lower left to the lower right with DP, rewrite the backtracked place to cost 0, find the cheapest route from lower right to upper right with DP, and the cost for each I tried to make an implementation that sums up, but about half WA.

Postscript: Solved as explained.

from heapq import heappop, heappush

INF = float('inf')


def cost_from(H, W, A, y0, x0):
    dp = [[INF] * W for _ in range(H)]
    dp[y0][x0] = 0
    q = [(0, y0, x0)]
    while q:
        c, y, x = heappop(q)
        t = dp[y][x]
        if t != c:
            continue
        if y - 1 >= 0:
            u = t + A[y - 1][x]
            if dp[y - 1][x] > u:
                dp[y - 1][x] = u
                heappush(q, (u, y - 1, x))
        if y + 1 < H:
            u = t + A[y + 1][x]
            if dp[y + 1][x] > u:
                dp[y + 1][x] = t + A[y + 1][x]
                heappush(q, (u, y + 1, x))
        if x - 1 >= 0:
            u = t + A[y][x - 1]
            if dp[y][x - 1] > u:
                dp[y][x - 1] = u
                heappush(q, (u, y, x - 1))
        if x + 1 < W:
            u = t + A[y][x + 1]
            if dp[y][x + 1] > u:
                dp[y][x + 1] = u
                heappush(q, (u, y, x + 1))
    return dp


H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

result = INF
cost1 = cost_from(H, W, A, H - 1, 0)
cost2 = cost_from(H, W, A, H - 1, W - 1)
cost3 = cost_from(H, W, A, 0, W - 1)
for i in range(H):
    for j in range(W):
        t = cost1[i][j] + cost2[i][j] + cost3[i][j] - 2 * A[i][j]
        if t < result:
            result = t
print(result)

past201912K-Megacorporation

I can't break through. Of course I can write a naive implementation, but I can't think of any way to reduce the amount of calculation.

Postscript: I learned Euler tour and AC.

N = int(input())

root = -1
children = [[] for _ in range(N + 1)]
left = [0] * (N + 1)
right = [0] * (N + 1)

for i in range(1, N + 1):
    p = int(input())
    if p == -1:
        root = i
    else:
        children[p].append(i)

i = 0
s = [root]
while s:
    n = s.pop()
    if n > 0:
        left[n] = i
        i += 1
        s.append(-n)
        for c in children[n]:
            s.append(c)
    else:
        right[-n] = i

Q = int(input())
result = []
for _ in range(Q):
    a, b = map(int, input().split())
    if left[b] < left[a] < right[b]:
        result.append('Yes')
    else:
        result.append('No')
print('\n'.join(result))

I also tried to solve it by doubling.

from math import log
from collections import deque
from sys import stdin

readline = stdin.readline

N = int(readline())

root = -1
children = [[] for _ in range(N + 1)]
parent = [[-1] * (N + 1) for _ in range(18)]

for i in range(1, N + 1):
    p = int(readline())
    parent[0][i] = p
    if p == -1:
        root = i
    else:
        children[p].append(i)

for i in range(1, 18):
    parenti1 = parent[i - 1]
    parenti = parent[i]
    for j in range(1, N + 1):
        t = parenti1[j]
        if t == -1:
            parenti[j] = -1
        else:
            parenti[j] = parenti1[t]

depth = [-1] * (N + 1)
q = deque([(root, 0)])
while q:
    n, d = q.pop()
    depth[n] = d
    for c in children[n]:
        q.append((c, d + 1))

Q = int(input())
result = []
for _ in range(Q):
    a, b = map(int, readline().split())
    if depth[a] <= depth[b]:
        result.append('No')
        continue
    while depth[a] != depth[b]:
        t = int(log(depth[a] - depth[b], 2))
        a = parent[t][a]
    if a == b:
        result.append('Yes')
    else:
        result.append('No')
print('\n'.join(result))

Recommended Posts

AtCoder 1st Algorithm Practical Test Virtual Participation Report
AtCoder 2nd Algorithm Practical Test Virtual Participation Report
AtCoder 3rd Algorithm Practical Test Participation Report
AtCoder Judge System Update Test Contest 202004 Participation Report
1st Algorithm Practical Test Solve past questions with python
AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 151 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 040 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 165 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Regular Contest 104 Participation Report
AtCoder Beginner Contest 156 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 171 Participation Report
AtCoder Beginner Contest 149 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Chokudai Contest 005 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Panasonic Programming Contest 2020 Participation Report
AtCoder Library Practice Contest Participation Report (Python)
AtCoder Introduction to Heuristics Contest Participation Report
The 3rd Algorithm Practical Test (PAST) Explanation (Python)
abc154 participation report
abc155 participation report
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Participation Report