ABC214のA-D問題の解説。
A - New Generation ABC
解説
条件分岐の問題。
問題文のとおりにifを書いてあげるとAC。
コード
n = int(input())
if n <= 125:
print('4')
elif n <= 211:
print('6')
elif n <= 214:
print('8')
# 短縮コード
n = int(input())
print(4 if n <= 125 else 6 if n <= 211 else 8)
B - How many?
解説
$a+b+c \leq S$かつ$a \times b \times c \leq T$を満たす非負整数を求める問題。
$(a, b, c)$の組み合わせなので、条件分岐と三重ループで求めることができる。
コード
# 愚直
s, t = map(int, input().split())
cnt = 0
for i in range(s+1):
for j in range(s+1):
for k in range(s+1):
if i + j + k <= s and i * j * k <= t:
cnt += 1
print(cnt)
# ちょっと頭を使ったコード
s, t = map(int, input().split())
cnt = 0
for a in range(s+1):
for b in range(s+1-a):
for c in range(s+1-a-b):
if a*b*c <= t:
cnt+=1
print(cnt)
C - Distribution
解説
番号のついたそれぞれのすぬけくんが、宝石を受け取る最小の時間を求める問題。
解法としては、今までの累積の時刻と高橋くんが渡す時刻のどちらが小さいかを求めて、高橋くんが渡す時刻を書き換えていくという方法だ。
この問題で注意する点は、すぬけくんが円周上に並んでいるということだ。
直線状に並んでいたら、最初から順番にやっていけばよいが、円になっているので、1番目のすぬけくんは、N番目のすぬけくんから先に宝石を貰う可能性がある。
したがって、ループはnではなく、n \times 2回する必要がある。このとき2回目のループに関しては、インデックス番号をnで割ったあまりをインデックスとして指定することで、同じように高橋くんが宝石を渡す時刻の書き換えができる。
コード
n = int(input())
slist = list(map(int, input().split()))
tlist = list(map(int, input().split()))
for i in range(n*2):
tlist[(i+1)%n] = min(tlist[(i+1)%n], tlist[i%n]+slist[i%n])
for i in range(n):
print(tlist[i])
D - Sum of Maximum Weights
解説
N頂点の木から2つを選び、その全通りに対する重みの和を求める問題。
全通りと聞くと、全探索したくなるが、それだと制約上TLEしてしまう。
この問題はさまざまな解法があるが、ここでは一般的なUnion-Findで解説していく。
Union-Findとは、グラフの部分木を円滑に操作できる方法である。
詳しくはこちらの記事をご覧いただきたい。
これを用いることで、部分木のサイズの確認や合併ができるようになる。問題点は、どのようにして最短パスに含まれる辺の重みの最大値をとるかだ。
このとき最大値を取ろうとするのではなく、小さい値から順番に調べていくと良い。最大値を取る作業ではなく、小さい値から計算していくことで、常に辺の重みの最大の値をとりながら計算することができる。
コード
class UnionFind(): # Union-Find
def __init__(self, n):
self.n = n
self.parents = [-1] * n
def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]
def union(self, x, y): # 頂点をつなぎあわせるメソッド
x = self.find(x)
y = self.find(y)
if x == y:
return
if self.parents[x] > self.parents[y]:
x, y = y, x
self.parents[x] += self.parents[y]
self.parents[y] = x
def size(self, x): # 部分木の大きさを測定するメソッド
return -self.parents[self.find(x)]
if __name__ == '__main__':
n = int(input())
es = []
for i in range(n-1):
u, v, w = map(int, input().split())
u -= 1 # インデックス調整
v -= 1
es.append([w, (u, v)])
es.sort() # 重みの小さい順番にソート
uf = UnionFind(n)
ans = 0
for w, e in es:
a, b = e
ans += w * uf.size(a) * uf.size(b) # 計算
uf.union(a, b) # 頂点の接合
print(ans)
Union-Findについて
Union-Findについての解説記事を書いたので、こちらも合わせて確認すると、知識の定着が図れるはずだ。
編集後記
Union-Findについて記事を書いている最中なのでお楽しみに.