ABC218のA-E問題の解説。
目次
A - Weather Forecast
B - qwerty
C - Shapes
D - Rectangles
E - Destruction
A - Weather Forecast
解説
$N$日後の天気予報が晴れ、つまり、oかどうかを判定する問題。
$S$の$N-1$文字目がoだったらYes。
コード
def main():
n = int(input())
s = input()
if s[n-1] == 'o':
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
B - qwerty
解説
Pの入力に対して、対応する英小文字をつなげていくという問題。
数字を文字列に変換するときは、chr()を用いる。chr(97)がaにあたるので、$+96$して文字を連結してあげれば良い。
コード
def main():
plist = list(map(int, input().split()))
s = ''
for p in plist:
s += chr(p+96)
print(s)
if __name__ == '__main__':
main()
C - Shapes
解説
$S$のグリッドの中で、$T$の#でつくられた形があるかどうかを判定する問題。
まずは、SとTの#の数が等しいかをみる。そもそも#の数が等しくなければ、この2つを一致させることができない。
一致していれば、ループに入る。
記録したsの#の座標をもとに、tの座標をひとつずつみていく。
一致しなかった場合は、ただちにループを抜けることで計算量を削減できる。
また、一致しなかった場合は、sの座標自体を90度回転させ、同じように#の位置を見ていく。
コード
def main():
n = int(input())
s = list(list(input()) for _ in range(n))
t = list(list(input()) for _ in range(n))
# sの'#'の座標を記録
slist = list((i, j) for i in range(n) for j in range(n) if s[i][j] == '#')
# tの'#'の数を記録
tcnt = sum(1 for i in range(n) for j in range(n) if t[i][j] == '#')
# '#'の数が合うかを確認し、あっていなければ'No'
if len(slist) != tcnt:
print("No")
exit()
# 90度x3回分回す
for _ in range(4):
for i in range(-n+1, n):
for j in range(-n+1, n):
flag = True
for x, y in slist:
if not (0 <= x+i < n and 0 <= y+j < n and t[x+i][y+j] == '#'):
flag = False
break
if flag:
print("Yes")
exit()
# 90度回転
slist = [(y, n-1-x) for x, y in slist]
print("No")
if __name__ == '__main__':
main()
D - Rectangles
解説
$2$次元平面上にある$N$個の点のうちから4つを選んで、何個の長方形が作れるかという問題。
まずxを固定して、それに対応するyを配列に保存する。つまり、各xがもつyを配列として保存する。
それらxを2つずつみていき、そのx_i, x_jがもつyの個数が2以上の場合は、x_i, x_jの共通するyを見つける。それらから2つをとった組み合わせの個数を数えてあげると、x_i, x_jとの長方形の数がわかるので、これを足していったものが答え。
コード
def main():
from itertools import combinations
n = int(input())
d = dict()
for _ in range(n):
x, y = map(int, input().split())
if x not in d:
d[x] = [y]
else:
d[x].append(y)
# xの座標
xaxis = [k for k in d.keys()]
cnt = 0
for i in range(len(xaxis)-1):
for j in range(i+1, len(xaxis)):
# そのx_i, x_jがもつyの個数が2以上の場合
if len(d[xaxis[i]]) >= 2 and len(d[xaxis[j]]) >= 2:
# x_i, x_jの共通するyを見つける
test = set(d[xaxis[i]]) & set(d[xaxis[j]])
# それらの組み合わせの個数を数える
cnt += len(list(combinations(test, 2)))
print(cnt)
if __name__ == '__main__':
main()
E - Destruction
解説
N頂点とM辺の連結無向グラフが存在するとき、重みのついた辺を取り除くと、その値に応じて報酬がもらえる。また、重みが負の値であれば、その値の絶対値分の罰金を支払う。
このとき、$0$本以上の辺を取り除き、すべての頂点がつながっている場合に得られる、最大の報酬を求める問題。
先に結論をいってしまうと、これは最小全域木を求めるアルゴリズムを用いると解くことができる。
このアルゴリズムには、プリム法とクラスカル法がある。こちらの仕組みついては解説記事をご覧いただきたい。どちらのアルゴリズムでも最小全域木を求めることにはかわりはない。
そもそも最小全域木というのは、存在するすべての頂点がつながっていて、辺の重みの総和が最小になるデータ構造のことをいう。
この問題で、なぜ最小全域木を求める必要があるのか。それは、罰金があるすべての辺、または、報酬が小さい辺はできるだけ残しておいた全域木を作成する必要があるためである。
ここからはコードを使って説明していく。
まず、重み（報酬）が正の値を取るとき、costに値を足し、先にすべての報酬を受けとっておく。これが辺をすべて取り除いた場合の報酬の最大値である。しかし、これではグラフが連結であるという条件を満たしていない。つまり、ここから最小全域木を作成する必要がある。
最小全域木をつくるにあたって、最小全域木の辺の値が負（罰金）の場合、辺を取り除く必要がない、つまり、罰金は取る必要がないため、そのままにしておく。
最小全域木の辺の値が正の場合、先程の操作でcostが報酬の最大値なので、報酬を受け取れない分、costから報酬分を引く。
これをすべての辺に対して行うことで、今回の問題の報酬の最大値を求めることができる。
コード1（プリム法）
プリム法ではheapq（優先度付きキュー）を用いているが、より詳しく知りたい方はこちらを参考にしていただきたい。
def main():
from heapq import heappush, heappop
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
cost = 0
for _ in range(m):
u, v, c = map(int, input().split())
u, v = u-1, v-1
graph[u].append((v, c)) # u->vの辺
graph[v].append((u, c)) # v->uの辺
if c >= 0:
cost += c
# プリム法
# 頂点がマークされているか確認する配列
marked = [False for _ in range(n)]
# マークされている頂点数を数える
marked_cnt = 0
# はじめに0頂点をマーク
marked[0] = True
marked_cnt += 1
# heap
q = []
# 頂点0に隣接する辺を保存
for j, c in graph[0]:
heappush(q, (c, j))
# すべての頂点をマークするまでwhileループ
while marked_cnt < n:
# 最小の重みの辺をheapで取り出す
c, i = heappop(q)
# マークされているならスキップ
if marked[i]:
continue
# 頂点をマーク
marked[i] = True
marked_cnt += 1
# 罰金でなければ報酬を
# 受け取りすぎているので報酬分の値を引く
if c >= 0:
cost -= c
# 頂点iに隣接する辺を保存
for j, c in graph[i]:
# マークされていればスキップ
if marked[j]:
continue
heappush(q, (c, j))
print(cost)
if __name__ == '__main__':
main()
コード2（クラスカル法）
クラスカル法ではUnion-Findを用いているが、より詳しく知りたい方はこちらを参考にしていただきたい。
# Union-Find
from collections import defaultdict
class UnionFind():
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)]
def same(self, x, y):
return self.find(x) == self.find(y)
def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]
def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]
def group_count(self):
return len(self.roots())
def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members
def __str__(self):
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())
# Code
def main():
n, m = map(int, input().split())
uf = UnionFind(n)
# 辺を保存する配列
edges = []
# 報酬、つまり、辺の重みを保存する変数
cost = 0
for _ in range(m):
u, v, c = map(int, input().split())
u, v = u-1, v-1 # インデックスずらし
edges.append((c, u, v))
# c_iが0以上のとき、c_iの報酬を得る
if c >= 0:
cost += c
# 重み（報酬）が小さい順に辺をソート
edges.sort()
# できるだけ辺（報酬）をとりたいので、
# 負（罰金）であるか値が小さい辺（報酬）を残した最小全域木を作りたい
# （それ以外の辺は報酬として受け取れる）
for edge in edges:
c, u, v = edge
# 罰金なら、それらの頂点をつなげる
if c <= 0:
uf.union(u, v)
else:
# 頂点がつながっていなければ
if not uf.same(u, v):
cost -= c # 報酬を引き
uf.union(u, v) # 頂点同士をつなげる
print(cost)
if __name__ == '__main__':
main()
編集後記
最小全域木結構面白いけど、例題が少ないのが難点。