ABC282の振り返り(A, B, C, D, E)

振り返りです。

def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}')): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}: expected: {exp}, output: {ans}")

A - Generalized ABC

問題略

解説通り。

from string import ascii_uppercase def A(K): print(ascii_uppercase[:K]) A(3) A(1)

結果：#37323560

自由欄

B - Let's Get a Perfect Score

問題略

やってみよう！

B関数を完成させて「Run」ボタンをクリックしよう！

test_dataB = [ { "in":[5, 5, ["ooooo","oooxx","xxooo","oxoxo","xxxxx",]], "out": 5 },{ "in":[3, 2, ["ox","xo","xx",]], "out": 1 },{ "in":[2, 4, ["xxxx","oxox",]], "out": 0 }, ] def B(N, M, S): pass test_all(B)

自由欄

try

ちょっと手直ししてこんな感じ。
これも解説通りです。

from itertools import combinations def B(N, M, S): ans = 0 for i, j in combinations(range(N), 2): for m in zip(S[i], S[j]): if "o" not in m: break else: ans += 1 return ans test_all(B)

結果：#37630389

行列積

行列積を用いた解法も紹介されているのでやってみます。

単純に行列積を取ると「二人とも正解か」を意味する行列になってしまうので、ド・モルガンの法則の雰囲気で以下の操作をしています。

$ \overline{\overline{A} \bigcap \overline{B}} \:=\: \overline{\overline{A}} \bigcup \overline{\overline{B}} \:=\: A \bigcup B $

これは、考えつかないな…

import numpy as np def B(N, M, S): s = np.array([list(s) for s in S]) == "o" return np.triu(~(~s @ (~s).T), 1).sum() test_all(B)

結果：#37631270

自由欄

C - String Delimiter

略

結果：#37334723

自由欄

D - Make Bipartite 2

やってみよう！

D関数を完成させて「Run」ボタンをクリックしよう！

test_dataD = [ { "in":[5, 4, [[4, 2], [3, 1], [5, 2], [3, 2]]], "out": 2 },{ "in":[4, 3, [[3, 1], [3, 2], [1, 2]]], "out": 0 },{ "in":[9, 11, [[4, 9], [9, 1], [8, 2], [8, 3], [9, 2], [8, 4], [6, 7], [4, 6], [7, 5], [4, 5], [7, 8]]], "out": 9 }, ] def D(N, M, uv): pass test_all(D)

自由欄

try(コンテスト中)

そもそも二部グラフが初耳だったので、簡単な判定方法ないかなぁ～とググったら頂点倍加union-findという方法にたどり着きました。
- 二部グラフ判定をUnionFindTreeで行う - noshi91のメモ -

@n_vip 頂点aをa0とa1に増やして、辺a-bに対してa0-b1とa1-b0を繋げば最後に全部の頂点についてx0-x1が繋がってなければ二部グラフ
— よすぽ (@yosupot) June 24, 2015

また、前処理として連結成分に分けたほうがよさそうだなぁってとこまではたどり着いたのですが、結局全探索の思考から抜け出せずにTLEのままフィニッシュでした…

最終的に以下。

from collections import defaultdict from copy import deepcopy class DSU(): def __init__(self): self.dsu = defaultdict(lambda: -1) def leader(self, i): if self.dsu[i] < 0: return i self.dsu[i] = self.leader(self.dsu[i]) return self.dsu[i] def merge(self, i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = self.leader(i) y = self.leader(j) if x == y: return if self.dsu[x] > self.dsu[y]: x, y = y, x self.dsu[x] += self.dsu[y] self.dsu[y] = x def members(self, i): l = self.leader(i) return [k for k, v in self.dsu.items() if self.leader(k) == l] def D(N, M, uv): dsu = DSU() g = DSU() edge = defaultdict(list) for u, v in uv: dsu.merge(u, N + v) dsu.merge(N + u, v) g.merge(u, v) edge[u].append(v) edge[v].append(u) leaders = dict() for i in range(1, N + 1): l = g.leader(i) if l in leaders: continue for n in g.members(l): if dsu.leader(n) == dsu.leader(n + N): leaders[l] = False break else: leaders[l] = True ans = 0 for i in range(1, N + 1): e = edge[i] for j in range(i + 1, N + 1): if j in e: continue li = g.leader(i) lj = g.leader(j) if li != lj: if leaders[li] and leaders[lj]: ans += 1 continue else: continue if not leaders[li]: continue target = deepcopy(dsu) target.merge(i, N + j) target.merge(N + i, j) for k in [i, j]: if target.leader(k) == target.leader(k + N): break else: ans += 1 return ans test_all(D)

結果：#37357012

根本的な発想が誤っていたらどんなに細かくチューニングしても無駄だという典型例です…

解説を見る

という訳で解説を見ます。
結局、以下のような考え方にたどり着かなければならなかったということですね…

実装例を見ても、頂点倍加Union-Findとか小手先のテクニックは不要で単純に全探索すればよかったんや…
以下ではBFSで実装し直しました。

from collections import deque, defaultdict def D(N, M, uv): edge = defaultdict(list) for u, v in uv: edge[u].append(v) edge[v].append(u) ans = N * (N - 1) // 2 - M remaind = set(range(1, N + 1)) while remaind: start = remaind.pop() q = deque([start]) classified = {start: 1} while q: now = q.popleft() for n in edge[now]: if n in classified: if classified[n] == classified[now]: return 0 else: remaind.remove(n) q.append(n) classified[n] = 1 ^ classified[now] cl = [0, 0] for v in classified.values(): cl[v] += 1 for i in cl: ans -= i * (i - 1) // 2 return ans test_all(D)

結果：#37672320

自由欄

E - Choose Two and Eat One

やってみよう！

E関数を完成させて「Run」ボタンをクリックしよう！

test_dataE = [ { "in":[4, 10, [4, 2, 3, 2]], "out": 20 },{ "in":[20, 100, [29, 31, 68, 20, 83, 66, 23, 84, 69, 96, 41, 61, 83, 37, 52, 71, 18, 55, 40, 8]], "out": 1733 } ] def E(N, M, A): pass test_all(E)

自由欄

解説を見る

せっかくなのでE問題もやってみます。無理です。解説を見ます。

キーワードは最大全域木、Prim法、Kruskal法といったところでしょうか。
何もわからないのでググるといつものけんちょんさんです。

AtCoder ABC 282 E - Choose Two and Eat One (青色, 500 点) - けんちょんの競プロ精進記録

こんな概念があるんだなぁ(小並)。

とりあえずPythonのpowは繰り返し二乗法で実装されてるっぽい（＆modも与えられる）ので前処理は楽できます。
あとはけんちょんさんのコードをパクってこんな感じ。

from itertools import combinations from collections import defaultdict class DSU(): def __init__(self): self.dsu = defaultdict(lambda: -1) def leader(self, i): if self.dsu[i] < 0: return i self.dsu[i] = self.leader(self.dsu[i]) return self.dsu[i] def merge(self, i, j): '''サイズの大きい方(x)に小さい方(y)をマージ''' if i == j: return x = self.leader(i) y = self.leader(j) if x == y: return if self.dsu[x] > self.dsu[y]: x, y = y, x self.dsu[x] += self.dsu[y] self.dsu[y] = x def members(self, i): l = self.leader(i) return [k for k, v in self.dsu.items() if self.leader(k) == l] def E(N, M, A): edge = [] for i, j in combinations(range(N), 2): edge.append([(pow(A[i], A[j], M) + pow(A[j], A[i], M)) % M, (i, j)]) edge = sorted(edge, reverse=True) ans = 0 cnt = 0 uf = DSU() for point, (i, j) in edge: if uf.leader(i) == uf.leader(j): continue ans += point uf.merge(i, j) cnt += 1 if cnt == N - 1: break return ans test_all(E)

結果：#37675523

自由欄