目次
はじめに
AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、初級者向け？の競技プログラミングコンテストのことです。
参加者はレーティングによってランク分けされます。私は8ランクあるうち、下から2番目のランク（茶色）のため、まだまだひよっこです。一つ上のランク（緑色）を目指して、現在精進しています。
ABCでは毎回8題の問題が出題され、後半の問題ほど、難易度が高くなります。ここでは私が戦える前半4題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。
ABC293
A – Swap Odd and Even
問題
文字列の奇数番目と偶数番目を入れ替える問題です。
解説
2文字ずつループさせることで解くことができます。
コード
S = input()
ans = ""
for i in range(len(S) // 2):
ans += S[2 * i + 1]
ans += S[2 * i]
print(ans)B – Call the ID Number
問題
番号を一度も呼ばれていない人を列挙する問題です。
解説
集合を使って呼ばれた人の管理を行います。
出力したいのは呼ばれていない人のため、全体集合{1, 2, … , N}から差集合を取りましょう。
コード
N = int(input())
A = list(map(int, input().split()))
S = set()
for i in range(N):
# すでに呼ばれている人でなければ対象の番号を呼ぶ
if not i + 1 in S:
S.add(A[i])
# 全体集合{1, 2, … , N}から差集合を取る
ans = set(range(1, N + 1)) - S
print(len(ans))
print(*ans)C – Make Takahashi Happy
問題
数字が書かれた2次元平面上のマスをスタートからゴールまで移動します。通ったマスの数字がすべて異なるような通り方は何通りあるかを求める問題です。
解説
この問題も集合を使いましょう。通ったマスの数字を集合で管理します。集合は要素の重複を排除できるため、「通ったマスの数字がすべて異なる」は「集合の要素の個数がH+W-1」として考えることができます。
モノの存在管理には集合を使おう
・要素の検索がO(1)で済むため
・要素の重複を排除できるため
また、この問題は右のマスに進むか下のマスに進むかの2択の繰り返しです。
HとWが10以下であることから、右のマスへの移動と下のマスへの移動は計18回以下です。2の18乗程度であれば全探索を行うことができます。
2択の繰り返しの全探索にはbit全探索を使おう
・for文を多重にすることなく2択の繰り返しを表現できるため
2択とはいえ、盤上をはみ出ないようにする必要があります。はみ出したケースについてはbreakするとよいでしょう。
コード
from sys import stdin
H, W = map(int, input().split())
A = [list(map(int, stdin.readline().split())) for _ in range(H)]
count = 0
# bit全探索
for i in range(2 ** (H + W - 2)):
y, x = 0, 0
S = {A[y][x]}
for j in range(H + W - 2):
if (i >> j) & 1:
y += 1
if y == H:
break
else:
x += 1
if x == W:
break
S.add(A[y][x])
if len(S) == H + W - 1:
count += 1
print(count)類題
bit全探索の類題 ABC289_C
D – Tying Rope
問題
N本のロープを繋げていきます。その結果、環状になっているロープの組と、そうでない組の個数を求める問題です。
解説
各ロープを頂点と捉え、グラフ上の問題として考えましょう。連結成分の問題なので、Union-Find木が使えないか検討するとよいです。
連結成分の問題ではUnion-Find木を考えよう
ひもは他のひもと2つまでしか繋がらないため、各頂点の次数は2以下です。
環状な連結成分の場合、属するすべての頂点の次数は2となるのに対し、連結成分でない場合、次数1の頂点が2つ存在します。次数1の頂点どうしが繋がり、すべての頂点の次数が2となることで、非環状→環状となります。
つまり、頂点と頂点を繋ぐ際、繋ぐ前から2頂点が同じ連結成分に属していれば、同じ連結成分の次数1の頂点どうしの証ですので、今回の接続によって、その連結成分は環状になります。そのような接続の回数をcountすることで、答えを求めることができます。
コード
class UnionFind():
# 初期化
def __init__(self, n):
self.n = n
self.par = [-1] * (n + 1)
self.rank = [0] * (n + 1)
self.siz = [1] * (n + 1)
# 根を求める
def root(self, x):
if self.par[x] == -1:
return x
else:
self.par[x] = self.root(self.par[x])
return self.par[x]
# x と y が同じグループに属するか (根が一致するか)
def issame(self, x, y):
return self.root(x) == self.root(y)
# x を含むグループと y を含むグループを併合する
def unite(self, x, y):
rx = self.root(x)
ry = self.root(y)
if rx == ry:
return False
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.par[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
self.siz[rx] += self.siz[ry]
return True
# グループの数を返す
def group_count(self):
return sum(x < 0 for x in self.par[1:])
N, M = map(int, input().split())
uf = UnionFind(N)
count = 0
for _ in range(M):
A, B, C, D = input().split()
if uf.issame(int(A), int(C)):
count += 1
else:
uf.unite(int(A), int(C))
print(count, uf.group_count() - count)類題
Union-Find木の類題 ABC292_D
最後に
以上、ABC293のA-D問題の説明でした。
ではまた！
モノの存在管理には集合を使おう
・要素の検索がO(1)で済むため
・要素の重複を排除できるため