ABC264のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
よかったらLGTMや拡散していただけると喜びます！
目次
ABC264 まとめ
A問題『"atcoder".substr()』
B問題『Nice Grid』
C問題『Matrix Reducing』
D問題『"redocta".swap(i,i+1)』
E問題『Blackout 2』
ABC264 まとめ
全提出人数: 8422人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 47分 | 5917(5659)位 |
| 400 | AB------ | 300 | 14分 | 4872(4614)位 |
| 600 | AB-D---- | 700 | 76分 | 3969(3726)位 |
| 800 | AB-D---- | 700 | 29分 | 3125(2883)位 |
| 1000 | ABCD---- | 1000 | 66分 | 2311(2071)位 |
| 1200 | ABCD---- | 1000 | 22分 | 1673(1434)位 |
| 1400 | ABCDE--- | 1500 | 78分 | 1151(936)位 |
| 1600 | ABCDE--- | 1500 | 52分 | 782(575)位 |
| 1800 | AB-DEF-- | 1700 | 98分 | 516(334)位 |
| 2000 | ABCDEF-- | 2000 | 85分 | 348(184)位 |
| 2200 | ABCDEF-- | 2000 | 65分 | 220(87)位 |
| 2400 | ABCDEF-- | 2000 | 40分 | 149(42)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 2734 | 98.1 % | 82.6 % | 11.4 % | 33.5 % | 1.7 % | 0.1 % | 0.0 % | 0.0 % |
| 茶 | 1431 | 99.0 % | 95.4 % | 43.9 % | 69.5 % | 6.2 % | 0.3 % | 0.0 % | 0.1 % |
| 緑 | 1149 | 98.3 % | 96.1 % | 76.6 % | 92.2 % | 31.1 % | 1.6 % | 0.1 % | 0.1 % |
| 水 | 678 | 97.9 % | 96.3 % | 91.9 % | 96.9 % | 79.9 % | 14.3 % | 0.9 % | 0.3 % |
| 青 | 404 | 95.5 % | 95.5 % | 94.8 % | 96.0 % | 93.8 % | 50.2 % | 7.9 % | 2.0 % |
| 黄 | 196 | 86.2 % | 85.2 % | 83.7 % | 85.7 % | 85.7 % | 64.8 % | 33.7 % | 9.7 % |
| 橙 | 43 | 83.7 % | 81.4 % | 79.1 % | 81.4 % | 81.4 % | 79.1 % | 83.7 % | 44.2 % |
| 赤 | 23 | 95.7 % | 95.7 % | 95.7 % | 95.7 % | 95.7 % | 95.7 % | 87.0 % | 73.9 % |
※表示レート、灰に初参加者は含めず
A問題『"atcoder".substr()』
問題ページ：A - "atcoder".substr()
灰コーダー正解率：98.1 %
茶コーダー正解率：99.0 %
緑コーダー正解率：98.3 %
考察
スライスを使ってatcoderの $L$ 文字目から $R$ 文字目を出力すればいいです。
コード
L, R = map(int, input().split())
S = "atcoder"
print(S[L - 1:R])
B問題『Nice Grid』
問題ページ：B - Nice Grid
灰コーダー正解率：82.6 %
茶コーダー正解率：95.4 %
緑コーダー正解率：96.1 %
考察
チェビシェフ距離
中央 $(8,8)$ は白です。そこからひとつ外側は黒、その外側は白……となっています。
中央から $k$ 個外側の色は、$k$ が偶数なら白、奇数なら黒です。この $k$ は、$k=\max(|R-8|,|C-8|)$ で求められます。（チェビシェフ距離といいます）
マス目を埋め込む
面倒ですが、$15\times15$ で $225$ マスしかないので、がんばって手でマス目を打ち込んで、$(R,C)$ の色を求めることもできます。
S = ["###############",
"#.............#",
"#.###########.#",
"#.#.........#.#",
"#.#.#######.#.#",
"#.#.#.....#.#.#",
"#.#.#.###.#.#.#",
"#.#.#.#.#.#.#.#",
"#.#.#.###.#.#.#",
"#.#.#.....#.#.#",
"#.#.#######.#.#",
"#.#.........#.#",
"#.###########.#",
"#.............#",
"###############"]
コード
チェビシェフ距離
def solve():
R, C = map(int, input().split())
dist = max(abs(R - 8), abs(C - 8))
return "white" if dist % 2 == 0 else "black"
print(solve())
マス目を埋め込む
S = ["###############",
"#.............#",
"#.###########.#",
"#.#.........#.#",
"#.#.#######.#.#",
"#.#.#.....#.#.#",
"#.#.#.###.#.#.#",
"#.#.#.#.#.#.#.#",
"#.#.#.###.#.#.#",
"#.#.#.....#.#.#",
"#.#.#######.#.#",
"#.#.........#.#",
"#.###########.#",
"#.............#",
"###############"]
def solve():
R, C = map(int, input().split())
R -= 1
C -= 1
return "white" if S[R][C] == "." else "black"
print(solve())
C問題『Matrix Reducing』
問題ページ：C - Matrix Reducing
灰コーダー正解率：11.4 %
茶コーダー正解率：43.9 %
緑コーダー正解率：76.6 %
考察
bit全探索で消す行・消す列を全探索します。
一つでも $B$ に一致する消し方があるならYes、ないならNoです。
コード
PyPyで出してください。bit_r の $1$ の立っている数が $H_2$ と等しく、bit_c の $1$ の立っている数が $W_2$ と等しい場合だけ判定するようにすれば、Pythonでも通ります。
def solve():
def judge(bit_r, bit_c):
A2 = []
for row in range(H1):
if not (bit_r >> row & 1):
continue
V = []
for col in range(W1):
if bit_c >> col & 1:
V.append(A[row][col])
A2.append(V)
return A2 == B
H1, W1 = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H1)]
H2, W2 = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(H2)]
for bit_r in range(1 << H1):
for bit_c in range(1 << W1):
if judge(bit_r, bit_c):
return True
return False
print("Yes" if solve() else "No")
D問題『"redocta".swap(i,i+1)』
問題ページ：D - "redocta".swap(i,i+1)
灰コーダー正解率：33.5 %
茶コーダー正解率：69.5 %
緑コーダー正解率：92.2 %
考察
隣接する $2$ つの要素が昇順になっていない場合、入れ替える操作を繰り返してソートするアルゴリズムを、バブルソートといいます。
この問題ではアルファベットの昇順ではなく、atcoderの並びにすることが目的ですが、$S$ の各文字を a=0, t=1, c=2, o=3, d=4, e=5, r=6の数字に置き換えることで、バブルソートで数列を[0, 1, 2, 3, 4, 5, 6] の昇順にするとき、要素を入れ替える回数が何回であるか求める問題になります。
つまり、$S$ の各文字を $0$ ～ $6$ に置き換えたリストに対して、実際にバブルソートを行って、要素を入れ替えた回数をカウントすればいいです。
コード
S = input()
P = "atcoder"
N = len(P)
L = [P.index(c) for c in S]
ans = 0
for i in range(N - 1):
for j in range(N - i - 1):
if L[j] > L[j + 1]:
L[j], L[j + 1] = L[j + 1], L[j]
ans += 1
print(ans)
備考
バブルソートで要素を入れ替える回数は、転倒数と一致することが知られています。したがって、実際にバブルソートを行わずとも、転倒数を求めればそれが答えと一致します。
転倒数を求めるライブラリを持っている場合は、こちらのほうが楽だと思います。
def main():
S = input()
P = "atcoder"
L = [P.index(c) for c in S]
print(calc_inversion_number(L))
class FenwickTree:
def __init__(self, n):
self.__array = [0] * n
self.__size = n + 1
self.__container = [0] * (n + 1)
self.__depth = n.bit_length()
def add(self, i, x):
"""a[i]にxを加算"""
self.__array[i] += x
i += 1
while i < self.__size:
self.__container[i] += x
i += i & (-i)
def sum(self, r):
"""[0, r) の総和"""
s = 0
while r > 0:
s += self.__container[r]
r -= r & (-r)
return s
def calc_inversion_number(A):
N = len(A)
ft = FenwickTree(N + 1)
ret = 0
for i, x in enumerate(A):
ret += i - ft.sum(x)
ft.add(x, 1)
return ret
if __name__ == '__main__':
main()
E問題『Blackout 2』
問題ページ：E - Blackout 2
灰コーダー正解率：1.7 %
茶コーダー正解率：6.2 %
緑コーダー正解率：31.1 %
考察
都市がどの発電所に繋がっているか区別する必要はありません。また、都市は $1$ つでも発電所と繋がっていれば電気が通ります。発電所と繋がっているか繋がっていないかだけが重要で、いくつの発電所と繋がっているかという情報は不要です。
そこで、 $M$ 個の発電所をすべて同一視してしまいます。 具体的には、地点 $N+1,N+2,\dots,N+M$ が発電所ですが、これらの地点をすべて頂点 $N+1$ として扱います。
すると、ある時点での電気が通っている都市の数は、データ構造のUnionFindを使って、$(頂点\ N+1\ の連結成分のサイズ) - 1$ で求められます（$-1$ は発電所の頂点のぶん）。
ただし、UnionFindは辺を削除することができません。そこで、$Q$ 個のイベントを逆から見ていって、電線 $X_i$ が切れるのではなく、電線 $X_i$ が繋がったことにすればいいです。
コード
考察では 頂点を $1$ から数え始めましたが、コードでは $1$ 引いて 頂点 $0$ から数え始めています。発電所は頂点 $N$ です。
import sys
readline = sys.stdin.readline # 入力が多く時間がかかるので、inputより高速な入力を使います（800ms程度高速になります）
def main():
N, M, E = map(int, readline().split())
edge = []
for i in range(E):
u, v = map(int, readline().split())
edge.append((min(u - 1, N), min(v - 1, N))) # N以上なら発電所なので、すべてNに置き換える
Q = int(readline())
X = []
connected = [True] * E # Q個のイベントの後、残っている辺をつなげる
for i in range(Q):
x = int(readline())
x -= 1
connected[x] = False
X.append(x)
uf = UnionFind(N + 1)
for i in range(E):
if connected[i]: # 切れてない辺なら接続
u, v = edge[i]
uf.unite(u, v)
ans = [0] * Q # 逆再生します
for i in reversed(range(Q)):
ans[i] = uf.size(N) - 1
u, v = edge[X[i]]
uf.unite(u, v) # 逆再生なので、答えを求めてから接続します
print(*ans, sep='\n')
from typing import List
class UnionFind:
"""0-indexed"""
def __init__(self, n):
self.n = n
self.parent = [-1] * n
self.__group_count = n
def unite(self, x, y) -> bool:
"""xとyをマージ"""
x = self.root(x)
y = self.root(y)
if x == y:
return False
self.__group_count -= 1
if self.parent[x] > self.parent[y]:
x, y = y, x
self.parent[x] += self.parent[y]
self.parent[y] = x
return True
def is_same(self, x, y) -> bool:
"""xとyが同じ連結成分か判定"""
return self.root(x) == self.root(y)
def root(self, x) -> int:
"""xの根を取得"""
xc = x
while self.parent[x] >= 0:
x = self.parent[x]
while xc != x:
self.parent[xc], xc = x, self.parent[xc]
return x
def size(self, x) -> int:
"""xが属する連結成分のサイズを取得"""
return -self.parent[self.root(x)]
def all_sizes(self) -> List[int]:
"""全連結成分のサイズのリストを取得 O(N)"""
sizes = []
for i in range(self.n):
size = self.parent[i]
if size < 0:
sizes.append(-size)
return sizes
def groups(self) -> List[List[int]]:
"""全連結成分の内容のリストを取得 O(N・α(N))"""
groups = dict()
for i in range(self.n):
p = self.root(i)
if not groups.get(p):
groups[p] = []
groups[p].append(i)
return list(groups.values())
@property
def group_count(self) -> int:
"""連結成分の数を取得 O(1)"""
return self.__group_count
if __name__ == '__main__':
main()