AtCoder Problems Hard No.91~100解説

Hard No.91 : D - Coloring Edges on Tree

D - Coloring Edges on Tree

発想

使用する色の数$K$はグラフの中で1つの頂点を端点とする辺の数の最大値になります。1つの頂点に接続している辺を順番に1,2,3...と色分けしていけば良いです。

実装

幅優先探索をしていきます。

from collections import deque

N = int(input())
G = []
for _ in range(N):
    G.append([])
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

k = 0
for i in range(len(G)):
    k = max(k, len(G[i]))

col = [0]*(N-1)
Q = deque([(0, 0)])
visited = [False]*N

while Q:
    #xは頂点、cは色
    x, c = Q.popleft()
    visited[x] = True
    tmp_c = 1
    #yは頂点、eは辺の番号
    for y, e in G[x]:
        if visited[y]:
            continue
        if tmp_c == c:
            tmp_c += 1
        col[e] = tmp_c
        Q.append((y, tmp_c))
        tmp_c += 1

print(k)
for c in col:
    print(c)

Hard No.92 : B - Unplanned Queries

B - Unplanned Queries

発想

木の辺は頂点間にあるので、すべての頂点の登場回数が偶数になればよいです。奇数が1個でもあれば、条件を満たす木はありません。

実装

N, M = map(int, input().split())
ver = [0]*N

for i in range(M):
    a, b = map(int, input().split())
    ver[a-1] += 1
    ver[b-1] += 1

for i in range(N):
    if ver[i] % 2 == 1:
        print('NO')
        exit()

print('YES')

Hard No.93 : D - Transit Tree Path

D - Transit Tree Path

発想

頂点$x$から頂点$y$まで頂点$K$を経由した最短距離は$d_{xK}+d_{Ky}$と表せます。結局は頂点$K$からすべて頂点までの距離が分かればよいので、heapを使って最短距離をすべて求めればよいです。

実装

import heapq

N = int(input())
G = []
for i in range(N):
    G.append([])
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((c, b-1))
    G[b-1].append((c, a-1))
Q, K = map(int, input().split())
XY = []
for i in range(Q):
    x, y = map(int, input().split())
    XY.append((x-1, y-1))

dist = [-1]*N
dist[K-1] = 0
done = [False]*N
q = []
#頂点Kからの距離をheapを使って求める
heapq.heappush(q, (0, K-1))

while len(q) > 0:

    d, i = heapq.heappop(q)

    if done[i]:
        continue

    done[i] = True

    for (c, j) in G[i]:
        if dist[j] == -1 or dist[j] > dist[i] + c:
            dist[j] = dist[i] + c
            heapq.heappush(q, (dist[j], j))

for i in range(Q):
    x, y = XY[i][0], XY[i][1]
    ans = dist[x] + dist[y]
    print(ans)

Hard No.94 : D - Blue and Red Balls

D - Blue and Red Balls

発想

操作回数$i$のとき、青いボールを置く場所の選び方は$_{N-K+1}C_i$になります。
操作回数$i$のとき、$K$個の青いボールを$i$箇所に分ける分け方（それぞれ少なくとも1個以上の青いボールがある）は、$_{K-1}C_{i-1}$通りあります。

実装

N,K = map(int,input().split())
Bp = 1
Rp = N-K+1

for k in range(K):
  print(Bp*Rp%(10**9+7))
  Bp = Bp*(K-k-1)//(k+1)
  Rp = Rp*(N-K-k)//(k+2)

Hard No.95 : D - Xor Sum 4

D - Xor Sum 4

発想

$_NC_2$通りを試すとTLEします。xorの演算では各桁ごとに独立してできます。xorの演算をすると、

1{ \ } ⊕{ \ } 1 = 0\\
0{ \ } ⊕{ \ } 0 = 0\\
1{ \ } ⊕{ \ } 0 = 1

となります。演算結果が1になるのは3番目のパターンのみなので、1の個数と0の個数をそれぞれ数えてその積を取ればよいです。

実装

N = int(input())
A = list(map(int, input().split()))
ans = 0
mod = 10**9+7

#i桁目の数字をそれぞれ独立に考える
for i in range(60):
    S = 0
    #i桁目の1の個数S、0の個数N-S
    for j in range(N):
        S += A[j]>>i&1
    ans += S*(N-S)<<i%mod
    ans %= mod

print(ans)

Hard No.96 : D - Make Them Even

D - Make Them Even

発想

コインの枚数が奇数のマスを見つけたら、下のマスに1枚移動させることを繰り返します。1番下の行の時に奇数枚のマスを見つけたら、右のマスに1枚コインを移動させます。最終的に$(H,W)$のマスのみが奇数枚のままになる可能性があります。

実装

H, W = map(int, input().split())
A = []
for i in range(H):
    a = list(map(int, input().split(' ')))
    A.append(a)

ans = []
for i in range(H-1):
    for j in range(W):
        if A[i][j] % 2 == 1:
            ans.append((i+1, j+1, i+2, j+1))
            A[i+1][j] += 1

for j in range(W-1):
    if A[-1][j] % 2 == 1:
        ans.append((H, j+1, H, j+2))
        A[-1][j+1] += 1

print(len(ans))
for i in range(len(ans)):
    print(*ans[i])

Hard No.97 : C - Base -2 Number

C - Base -2 Number

発想

2で割ることを繰り返せばよいです。ただし今回の問題は2進数でなく、-2進数ですので、計算するたびに$N$の符号を変えます。

実装

N = int(input())
ans = ''

if N == 0:
    ans = 0
while N:
    ans = str(N%2) + ans
    N = -(N//2)

print(ans)

Hard No.98 : C - Palindromic Matrix

C - Palindromic Matrix

発想

例えば$H,W$ともに偶数の場合、全ての文字は4の倍数個なければならないです。
一方で$H,W$ともに奇数の場合、行列の中心に文字を1つだけ置くことができます（奇数個の文字を1個置ける）。さらに行列の中心を通る1行と1列には偶数個の文字を置くことができます（4の倍数でない）。
逆にいえば、奇数個の文字種が多すぎたり、偶数個の文字種（4の倍数でない）が多すぎれば、その行列は回文にすることができません。
以上のような考え方で実装をしていきます。

実装

import collections

H, W = map(int, input().split())
A = ''
for i in range(H):
    a = input()
    A += a
A = list(A)

even = 0
odd = 0
C = collections.Counter(A)
for c in C:
    #4で割ったあまりが2または3の場合にevenは+1される
    #あまりが3の時は、それを1と2に分けるから、oddもevenも+1される
    even += C[c] % 4 // 2
    odd += C[c] % 2
#H,W両方奇数のときに奇数個の文字が2つ以上
#または、H,Wのうち少なくとも1方が偶数のときに、奇数個の文字が2つ以上のとき'No'
if (H % 2) * (W % 2) < odd:
    print("No")
#偶数個の文字を置ける個数よりも偶数個の文字が多ければ'No'
elif (H % 2) * (W // 2) + (H // 2) * (W % 2) < even:
    print("No")
else:
    print("Yes")

Hard No.99 : B - Simplified mahjong

B - Simplified mahjong

発想

各$i$に対して$[A_i/2]$個のペアを作ることができる。$A_i=0$なる$i$が一つも存在せず、$i$のカードが1枚だけ余った場合は、その1枚と$i+1$のカードでペアを作ることができる。よってペアの数は$[sum(A)/2]$になる。
$A_i=0$なる$i$が登場したら、$i-1$までで同じように計算し、$i$を飛ばして$i+1$から計算を再開すればよい。

実装

N = int(input())

ans = 0
tmp = 0
for i in range(N):
    a = int(input())
    if a == 0:
        ans += tmp//2
        tmp = 0
    tmp += a
else:
    ans += tmp//2

print(ans)

Hard No.100 : C - Vacant Seat

C - Vacant Seat

発想

空席の場所を20回程度で見つけ出します。$O(N)$では間に合いませんので、二分探索で見つけます。smallをmidに寄せる条件を考えて実装します。

実装

（１）smallとmidの位置の性別が同じ場合
(mid - small)を2で割った時のあまりが0の時、smallからmidまで男女が交互に空席なく並んでいるので、smallをmidに寄せる
（２）smallとmidの位置の性別が異なる場合
(mid - small)を2で割った時のあまりが1の時、smallからmidまで男女が交互に空席なく並んでいるので、smallをmidに寄せる
以上2つの場合以外ではlargeをmidに寄せれば良いです。

N = int(input())
print(0)
s = input()
if s == "Vacant":
    exit()
fm = s
small = 0
large = N
while True:
    mid = (small + large) // 2
    print(mid)
    s = input()
    if s == "Vacant":
        exit()
    if (s == fm) ^ ((mid - small) % 2 == 1):
        small = mid
        fm = s
    else:
        large = mid