Hard No.81 : C - Boxes and Candies
発想
隣り合う2つの箱のうち、どちらの箱からどれだけキャンディを取れば良いのか。左から箱を見ていって、$i$番目と$i+1$番目の箱うち、$i+1$番目から可能な限りキャンディを食べるのが良いです。なぜなら$i+1$番目からキャンディを食べることで$i+2$番目の箱から食べるキャンディの個数を少なくすることができるからです。
実装
N, X = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for i in range(N-1):
if A[i] + A[i+1] > X:
#食べるべきキャンディの個数
x = A[i+1] + A[i] - X
ans += x
A[i+1] -= x
#取りすぎた分のキャンディをi番目から取る
if A[i+1] < 0:
A[i] += A[i+1]
A[i+1] = 0
print(ans)
Hard No.82 : C - Different Strokes
発想
単に自分の幸福度だけ追求すると、相手の幸福度も高くなり、（自分の幸福度）ー（相手の幸福度）を最大化できない場合があります。自分の幸福度だけでなく、相手の幸福度も高い料理を選ぶことで、相手が幸福度を上げづらくすることができます。
実装
以下のようなリストを作成します。
[A_i+B_i, { \ }A_i, { \ }B_i]
$A_i+B_i$が大きい順にソートして、左から順に高橋、青木の順で料理を食べればよいです。
N = int(input())
arr = []
for i in range(N):
a, b = list(map(int, input().split()))
arr.append([a+b, a, b])
arr = sorted(arr, reverse=True)
ans = 0
for i in range(N):
c, a, b = arr[i]
#高橋が食べる
if i%2 == 0:
ans += a
#青木が食べる
else:
ans -= b
print(ans)
Hard No.83 : A - Darker and Darker
発想
黒を増やすか白を減らすか少し悩みます。最終的にはすべてのマスが黒になるので、黒マスから移動すると考えたほうが良さそうです。黒マスの距離はすべて0にしておいて、幅優先探索で白マスすべてに距離を与えれば良さそうです。答えは距離の最大値になります。
実装
from collections import deque
H, W = map(int, input().split())
A = []
for i in range(H):
A.append(list(input()))
Black = deque()
for i in range(H):
for j in range(W):
if A[i][j] == '#':
Black.append([i, j])
#距離を入れるリスト
dist = []
for i in range(H):
dist.append([-1]*W)
#黒マスの距離をすべて0にする
for i in range(H):
for j in range(W):
if A[i][j] == '#':
dist[i][j] = 0
#幅優先探索
while len(Black) > 0:
i, j = Black.popleft()
for di, dj in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
i2 = i+di
j2 = j+dj
#マスからはみ出ちゃダメ！
if not (0 <= i2 < H and 0 <= j2 < W):
continue
#黒マスに移動しちゃダメ！
if A[i2][j2] == '#':
continue
if dist[i2][j2] == -1:
dist[i2][j2] = dist[i][j] + 1
Black.append([i2, j2])
ans = 0
for i in range(H):
ans = max(ans, max(dist[i]))
print(ans)
Hard No.84 : C - Shopping Street
発想
読みづらいです。苛々です。
午前午後や曜日に深い意味はなく、単に10個の時間帯があると思えばよいです。10個の時間帯それぞれで店を開けるか閉めるかを全探索すれば良さそうです。
実装
店$i$とjoisinoお姉ちゃんの店が同時に空いている時間帯の個数を数えていきます。例えば店2とjoisinoお姉ちゃんの店が3つの時間帯で両方とも店を開けていたら答えに$P_{2,3}$を加えます。
N = int(input())
F = []
for i in range(N):
f = list(map(int, input().split()))
F.append(f)
P = []
for i in range(N):
p = list(map(int, input().split()))
P.append(p)
ans = -10**10-1
#10個の時間帯でjoisinoお姉ちゃんの店を開けるかどうか全探索
for i in range(1, 2**10):
#C[i]:店iとjoisinoお姉ちゃんの店が両方空いている時間帯の個数
C = [0]*N
for j in range(10):
if i >> j & 1 == 1:
for k in range(N):
if F[k][j] == 1:
C[k] += 1
tmp = 0
for i in range(N):
tmp += P[i][C[i]]
ans = max(ans, tmp)
print(ans)
Hard No.85 : C - Pyramid
発想
得られた情報の個数が3個以上であり、かつそれらの高さが0より大きいならば、確実にピラミッドの中心座標と高さが求められます。しかし、この問題設定はそのようになっていないです。
（１）情報→答えを求める
という方針がうまくいかないので、
（２）答えを決め打ち→情報に矛盾しない
という方針が良さそうです。
実装
ピラミッドの中心座標は101×101通りがあります。高さを決めるためには、高さ1以上の情報が1つ必要です。
N = int(input())
C = []
for i in range(N):
c = list(map(int, input().split()))
C.append(c)
#高さ1以上の情報を1つ用意する
for i in range(N):
if C[i][2] > 0:
xo = C[i][0]
yo = C[i][1]
ho = C[i][2]
break
#中心座標(cy, cx)を決める
for cy in range(101):
for cx in range(101):
#中心座標が(cy, cx)の時のピラミッドの高さを求める
Ho = abs(cx-xo) + abs(cy-yo) + ho
for i in range(N):
#計算結果と与えられた情報が違ったらbreak
if max(Ho - abs(C[i][0]-cx) - abs(C[i][1]-cy), 0) != C[i][2]:
break
else:
#すべての情報に矛盾しなければ、それが答え
print(cx, cy, Ho)
exit()
Hard No.86 : D - Coloring Dominoes
発想
ドミノを左から敷き詰めた時、次のドミノの色の場合の数は現在のドミノの色と置き方によって変わります。左から$i$番目の位置のドミノの色の場合の数を考えます。
(1)$i$番目の位置のドミノを横に置くとき
(1.1)$i-1$番目の位置のドミノが横に置いてあったとき
→3通り
(1.2)$i-1$番目の位置のドミノが縦に置いてあったとき
→2通り
(2)$i$番目の位置のドミノを縦に置くとき
(2.1)$i-1$番目の位置のドミノが横に置いてあったとき
→1通り
(2.2)$i-1$番目の位置のドミノが縦に置いてあったとき
→2通り
以上のように場合分けして考えます。
実装
$i$番目の位置のドミノを横に置くときは次のドミノは$i+2$番目の位置になることに注意が必要です。
N = int(input())
S1 = input()
S2 = input()
mod = 10**9 + 7
cur = 0
#初期値
if S1[0] != S2[0]:
ans = 6
cur = 2
else:
ans = 3
cur = 1
while cur < N:
#横に置くとき
if S1[cur] != S2[cur]:
#手前のドミノも横に置いてある
if S1[cur-1] != S2[cur-1]:
ans *= 3
ans %= mod
#手前のドミノは縦
else:
ans *= 2
ans %= mod
#位置を+2することに注意
cur += 2
#縦に置くとき
else:
#手前のドミノも縦に置いてある
if S1[cur-1] == S2[cur-1]:
ans *= 2
ans %= mod
cur += 1
print(ans)
Hard No.87 : D - Friend Suggestions
発想
友達とかいう言葉があると、「友達グループ」とか「友達関係」とか「あんたなんか友達じゃないんだからねっ！関係」とかあったりして、ああUnionとFindをするんだなって思います（病気）。
友達関係で結ばれている人たちを1つのグループにまとめたとします。このとき、人$i$に対して求める答え$ans[i]$は
\begin{align}
ans[i]&=(人iが所属するグループの人数)\\
&\quad -(人iが所属するグループの中で、人iと友達関係かブロック関係の人数)\\
&\quad -1
\end{align}
となります（最後の-1は自分自身）。以上のような計算はUnion-Findという根つき木のデータ構造を用いることで実装できます。
実装
今回のUnion-Findは3つの関数からなります。
（１）find(x)
頂点$x$の根を返します。$x$の1つ上の頂点（親）を見た時に、それが根でなかったら、親を根につなぎ直すことをします（経路圧縮）。こうすることで計算量を減らせます。
（２）union(x, y)
頂点$x,y$が別々のグループに所属していた場合に、頂点$x,y$それぞれが所属しているグループを1つのグループに併合します。
（３）same(x, y)
頂点$x,y$が同じグループに所属していればTrue、そうでなければFalseを返します。
N, M, K = map(int,input().split())
#par[i]:頂点iの根。par[i]==iの時、自分が木の根。
par = [i for i in range(N)]
#sz[i]:頂点iを部分木の根とみなしたときのその木の大きさ。
sz = [1]*N
ans = [0]*N
def find(x):
#根に到達したら、その頂点を返す
if par[x] == x:
return x
else:
#経路圧縮
par[x] = find(par[x])
return par[x]
def union(x, y):
rx, ry = find(x), find(y)
#同じグループなら何もしない
if rx == ry:
return
#どちらの部分木が大きいか判断して、大きいほうの木に小さい木を併合する
if sz[rx] < sz[ry]:
sz[ry] += sz[rx]
par[rx] = ry
else:
sz[rx] += sz[ry]
par[ry] = rx
def same(x, y):
return find(x) == find(y)
for _ in range(M):
a, b = map(int,input().split())
a -= 1
b -= 1
#友達関係は-1する
ans[a] -= 1
ans[b] -= 1
union(a, b)
for _ in range(K):
c,d = map(int,input().split())
c -= 1
d -= 1
if same(c, d):
#同じグループに所属しているブロック関係は-1する
ans[c] -= 1
ans[d] -= 1
for i in range(N):
ans[i] += sz[find(i)] - 1
print(ans[i], end=' ')
Hard NO.88 : D - XOR World
発想
制約に$10^{12}$があるので$O(1)$か$O(logN)$で解かなければならないです。排他的論理和の性質を考えます。任意の正整数$n$に対して$n⊕n=0$なので、
\begin{align}
f(A,B) &= A⊕(A+1)⊕(A+2)⊕...⊕B\\
&= (0⊕1⊕...(A-1))⊕(0⊕1⊕...⊕B)\\
&= f(0,A-1)⊕f(0,B)
\end{align}
となります。また、任意の偶数$n$に対して$n⊕(n+1)=1$なので
f(0,x) = \left\{
\begin{array}{ll}
x & (x \equiv0{ \ } mod { \ }4 )\\
1 & (x \equiv1{ \ } mod { \ }4 )\\
1⊕x & (x \equiv2{ \ } mod { \ }4 )\\
0 & (x \equiv3{ \ } mod { \ }4 )\\
\end{array}
\right.
となります。
実装
A, B = map(int, input().split())
def f(x):
M = [x, 1, 1^x, 0]
m = M[x % 4]
return m
print(f(A - 1) ^ f(B))
Hard No.89 : E - Colorful Hats 2
発想
例えば$i=1,2,3$のときにすべて0が続いたときの場合の数は$3×2×1$通りになります。さらにその後に0が来るような場合は実現しません。つまり$A$の中で同じ数字を使うことができるのは3回までということがわかります。また、同じ数字を使うごとに、場合の数は3,2,1と減っていくことがわかります。
次に$i=1,2,3$のときの$A_i$の並びが$[0,0,1]$となるような場合を考えます。$i=1,2$の時にそれぞれ赤、青を使ったとすると、$i=3$の帽子の色は赤、または青の2通りになります。つまり$A$の中で0を使うたびに1として考えられる場合の数が1増えることがわかります。
以上のように
（１）同じ数字を使えるのは3回まで
（２）ある数字$a$を使うごとに$a$として考えられる場合の数は1減り、$a+1$として考えられる場合の数が1増える
ということがわかりました。これらを実装します。
実装
N = int(input())
A = map(int, input().split())
mod = 10**9+7
ans = 1
cnt = [3] + [0]*N
for a in A:
ans = ans * cnt[a] % mod
if ans == 0:
break
cnt[a] -= 1
cnt[a+1] += 1
print(ans)
Hard No.90 : D - Even Relation
発想
2頂点間の距離が偶数です。頂点0から頂点$i,j$までの距離をそれぞれ$d_i,d_j$と置くと、$d_i,d_j$の組み合わせは
(d_i,d_j)=(偶,奇),(奇,偶),(偶,偶),(奇,奇),
が考えられます。このとき、
(1)$d_i,d_j$の偶奇が一致しない場合、2頂点間の距離は奇数
(2)$d_i,d_j$の偶奇が一致する場合、2頂点間の距離は偶数
が成り立ちます。例えば距離が偶数の頂点をすべて白に塗り、奇数の頂点を黒に塗ることで答えを得られます。
実装
辺の重み付き最短距離を計算するのでheapを使います。
import heapq
N = int(input())
G = []
for i in range(N):
G.append([])
for i in range(N-1):
u, v, w = map(int, input().split())
G[u-1].append((w, v-1))
G[v-1].append((w, u-1))
dist = [-1]*N
dist[0] = 0
done = [False]*N
Ans = [0]*N
Q = []
heapq.heappush(Q, (0, 0))
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(N):
if dist[i] % 2 == 0:
Ans[i] = 0
else:
Ans[i] = 1
for i in range(N):
print(Ans[i])