#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に寄せる条件を考えて実装します。
##実装
(1)smallとmidの位置の性別が同じ場合
(mid - small)を2で割った時のあまりが0の時、smallからmidまで男女が交互に空席なく並んでいるので、smallをmidに寄せる
(2)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