import copy
def test_all(f):
for i, data in enumerate(eval(f"test_data{f.__name__[0]}")):
exp = data["out"]
ans = f(*copy.deepcopy(data["in"]))
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
def B(R, C):
pass
print(B(3, 5)) # black
print(B(4, 5)) # white
自由欄
try
解法がパッと思いつかなかったので、設問のグリッドをつくりました。
import numpy as np
def B(R, C):
g = [[0]]
for i in range(7):
g = np.pad(g, 1, constant_values=0 if i % 2 else 1)
return "black" if g[R - 1, C - 1] else "white"print(B(3, 5)) # black
print(B(4, 5)) # white
def C(A, B):
def proc(A, B):
A1 = []
for br in B:
while A:
ar = A.pop(0)
if set(br).issubset(set(ar)):
A1.append(ar)
break
else:
return None
return A1
A1 = proc(A, B)
if not A1:
return "No"
A2 = proc(list(zip(*A1)), list(zip(*B)))
if not A2:
return "No"
return "Yes"test_all(C)
A = [
[2, 9, 1],
[1, 9, 2],
[3, 9, 4],
]
B = [[1, 2], [3, 4]]
C(A, B)
元々思いつきで実装してみたらACだったという感じで自信はなかったのですが…
全然ダメやん😇
自由欄
解説を見る
という訳で、暫く考えてもいい方法が思いつかないので解説を見ます。
解説 by leaf1415では全探索の解法を紹介しています。
なかなかの力技ですが、「制約の小さいC問題」は全探索が第一候補でしたね…
from itertools import combinations
import numpy as np
def C(A, B):
A = np.array(A)
B = np.array(B)
ar, ac = A.shape
br, bc = B.shape
for rows in combinations(range(ar), br):
A2 = A[rows, :]
for cols in combinations(range(ac), bc):
if np.all(A2[:, cols] == B):
return "Yes"
return "No"test_all(C)
def D(*S):
ATCODER = "atcoder"
a = [ATCODER.index(s) for s in S]
ans = 0
for i in range(len(a)):
for j in range(len(a) - 1, i, -1):
if a[j] < a[j - 1]:
a[j], a[j - 1] = a[j - 1], a[j]
ans += 1
return anstest_all(D)
class BIT:
def __init__(self, a):
if hasattr(a, "__iter__"):
self.size = len(a)
self.data = [0] * self.size
self.bit = [0] * (self.size + 1)
for i, j in enumerate(a):
self.add(i, j)
elif isinstance(a, int):
self.size = a
self.data = [0] * a
self.bit = [0] * (a + 1)
else:
raise TypeError()
def add(self, i, x):
self.data[i] += x
i += 1
while i <= self.size:
self.bit[i] += x
i += i & -i
def sum(self, i):
'''Get sum of data[:i]
'''
total = 0
while i > 0:
total += self.bit[i]
i -= i & -i
return total
def __getitem__(self, key):
return self.data[key]
def __setitem__(self, key, value):
self.add(key, value - self[key])
self.data[key] = value
def __len__(self):
return self.size
def __repr__(self):
return self.data.__repr__()
def __iter__(self):
return self.data.__iter__()def D(*S):
ATCODER = "atcoder"
a = [ATCODER.index(s) for s in S]
bit = BIT(len(a))
ans = 0
for i, j in enumerate(a):
bit[j] = 1
ans += i - bit.sum(j)
return anstest_all(D)
from collections import deque
def E(N, M, UV, X):
UV = [[0 if u > N else u, 0 if v > N else v] for u, v in UV]
edges = [[] for _ in range(N + 1)]
for i in set(range(1, len(UV) + 1)) - set(X):
u, v = UV[i - 1]
if u == 0: continue
edges[u].append(v)
edges[v].append(u)
ret = [0] # 電気が通っている都市の数
passed = set([0]) # 発電所
q = deque([0]) # 発電所から探索スタート
for x in X[::-1]:
# BFS
while q:
for i in edges[q.pop()]:
if i in passed: continue
ret[-1] += 1
passed.add(i)
q.append(i)
ret.append(ret[-1])
# 電線を繋ぐ
u, v = UV[x - 1]
if u == 0:
## 両方発電所
q = False
continue
edges[u].append(v)
edges[v].append(u)
c = set([u, v])
p = passed & c
if len(p) == 1:
nxt = (c - p).pop()
ret[-1] += 1
passed.add(nxt)
q = deque([nxt])
else:
q = False
continue
return "\n".join(map(str, ret[:-1][::-1]))test_all(E)
def E(N, M, UV, X):
dsu = [-1] * (N + 1)
def leader(i):
if dsu[i] < 0: return i
dsu[i] = leader(dsu[i])
return dsu[i]
def merge(i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
if i == j: return
x = leader(i)
y = leader(j)
if x == y: return
if dsu[x] > dsu[y]: x, y = y, x
dsu[x] += dsu[y]
dsu[y] = x
UV = [[0 if u > N else u, 0 if v > N else v] for u, v in UV]
for i in set(range(1, len(UV) + 1)) - set(X):
u, v = UV[i - 1]
if u == 0: continue
merge(u, v)
ret = []
for x in X[::-1]:
ret.append(- dsu[leader(0)] - 1)
# 電線を繋ぐ
merge(*UV[x - 1])
return "\n".join(map(str, ret[::-1]))test_all(E)
AtCoder Inc.
