[PYTHON] yukicoder contest 248 Participation record

yukicoder contest 248 Participation record

A 1052 Electronic Equipment X

Break through in 29 minutes. I finally found out about N = 10,11 by hand from K = 1 to 8 (laughs). When N is even, K is even when K is odd, and when K is even Since only odd numbers are available, the maximum is N / 2. When N is odd, both even and odd numbers are available, so the maximum is N.

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

if N % 2 == 0:
    print(min(K + 1, N // 2))
else:
    print(min(K + 1, N))

B 1053 Gaming Stick

I couldn't break through. After ACing up to 2 WAs, I was wondering if there was another pattern that could meet the conditions, while I wasn't able to do it if there was even one of the three. (Laughs). There are two patterns that can meet the conditions.

1. The colors are not separated from the beginning (0 times)
2. There is only one that is divided into two, which is the beginning and the end (once)

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

d = {}
prev = -1
for a in A:
    if prev != a:
        d.setdefault(a, 0)
        d[a] += 1
    prev = a

if all(v == 1 for v in d.values()):
    print(0)
    exit()

if any(v >= 3 for v in d.values()):
    print(-1)
    exit()

if len([v for v in d.values() if v == 2]) == 1 and A[0] == A[-1]:
    print(1)
else:
    print(-1)

C 1054 Union add query

I couldn't break through. I thought it would be possible to add them all together like ABC138D --Ki, but it is impossible to implement in the remaining time. so…….

Addendum: I modified and implemented the Union Find tree as explained. When unite, it was said that the value of the parent was subtracted from the value of the parent that joins the company. The number for the new parent I was worried about how to increase the number, and I was too stupid. The explanation said that it is okay to remove the route compression, but Python is slow and I did not think that it was too difficult to leave the route compression, so I left it and implemented it. I did AC, but it was a short time, so I think it was the correct answer.

It's a modification, but now it passes not only the parent information but also the total value information to find. And find returns not only the parent number but also the total value of the parent on the way to the parent. When compressing the route, it is necessary to add the total in the middle to your own total. At the time of unite, as mentioned above, subtract the total of the parent values from the total of the parent values under the umbrella to offset each. The value of a node is the sum of the values of that node and the value of its parent (due to the effect of path compression).

from sys import setrecursionlimit
from sys import stdin


def find(parent, amount, i):
    t = parent[i]
    if t < 0:
        return i, 0
    t, a = find(parent, amount, t)
    parent[i] = t
    amount[i] += a
    return t, amount[i]


def unite(parent, amount, i, j):
    i, _ = find(parent, amount, i)
    j, _ = find(parent, amount, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j
    amount[i] -= amount[j]


setrecursionlimit(10 ** 6)
readline = stdin.readline

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

parent = [-1] * (N + 1)
amount = [0] * (N + 1)

result = []
for _ in range(Q):
    T, A, B = map(int, readline().split())
    if T == 1:
        unite(parent, amount, A, B)
    elif T == 2:
        j, _ = find(parent, amount, A)
        amount[j] += B
    elif T == 3:
        j, a = find(parent, amount, A)
        result.append(amount[j] + a)
print('\n'.join(str(v) for v in result))