ABC347をPythonで（A～E）

AtCoder Beginner Contest 347の解答等のまとめです

A問題

問題文のことをそのままする。
なおAtcoderでは、空白区切りは改行区切りで提出しても正解になる

A

n, k = map(int, input().split())

for a_i in map(int, input().split()):
    if a_i % k == 0:
        print(a_i // k)

B問題

全通り試す

B

s = input()

a = set()

for j in range(len(s) + 1):
    for i in range(j):
        a.add(s[i:j])

print(len(a))

C問題

どれかが休日初日のときに全部休みか調べる

1. 全部を$a+b$で割ったあまりにしてソートする
2. 一番大きいのと小さいのとの差が$a$未満ならOK
3. 一番小さいのに$a+b$を足して一番大きくする

コードは少しややこしいことをしているが$i-1$を見ればいい

C

n, a, b = map(int, input().split())
d = list(map(int, input().split()))

x = [d_i % (a + b) for d_i in d]
x.sort()

ans = "No"
for i in range(n):
    j = (i + n - 1) % n
    if x[j] - x[i] < a:
        ans = "Yes"
    x[i] += a + b

print(ans)

D問題

$C$で立っているビットは片方でしか立たない
→$C$で立っていないところは$X,Y$両方立つか立たない
上の条件で成立する数があるか調べる

D

a, b, C = map(int, input().split())
c = C
z = [0] * 60
for i in range(59, -1, -1):
    z[i] = c % 2
    c //= 2

count = z.count(1)
if (a + b - count) % 2 == 1:
    exit(print(-1))

d = (a + b - count) // 2
x_count = a - d
y_count = b - d

if x_count < 0 or y_count < 0:
    exit(print(-1))

w = [0] * 60
for i in range(60):
    if z[i] == 0 and d > 0:
        w[i] = 1
        d -= 1

x, y = ["0"] * 60, ["0"] * 60
for i in range(60):
    if w[i] == 1:
        x[i] = "1"
        y[i] = "1"
    elif z[i] == 1:
        if x_count > 0:
            x[i] = "1"
            x_count -= 1
        else:
            y[i] = "1"

X, Y = int("".join(x), 2), int("".join(y), 2)

if X ^ Y == C and x.count("1") == a and y.count("1") == b:
    print(X, Y)
else:
    print(-1)

E問題

まず$i$番目の種類数を調べておく
種類数の累積和$S$を利用して
$S[i$が偶数回目に出たところ$] - S[i$が奇数回目に出たところ]
の総和を求めればいい

E

n, q = map(int, input().split())
x = list(map(int, input().split()))

a = [0] * q
d = dict()
s = set()
for i, x_i in enumerate(x):
    if x_i not in d:
        d[x_i] = []
    d[x_i].append(i)

    if x_i in s:
        s.discard(x_i)
    else:
        s.add(x_i)
    a[i] = len(s)

b = [0]
for a_i in a:
    b.append(b[-1] + a_i)

ans = [0] * n
for key in d.keys():
    if len(d[key]) % 2 == 1:
        d[key].append(len(b) - 1)
    for i, j in zip(d[key][::2], d[key][1::2]):
        ans[key - 1] += b[j] - b[i]

print(*ans)