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

振り返りです。

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}")

A - "atcoder".substr()

略

B - Nice Grid

やってみよう！

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

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

結果：提出 #35087826

自由欄

解説を見る

解説ではチェビシェフ距離という概念に言及しています。
初見なので軽く調べてみました。

ディープラーニング関連の文脈で紹介されているのが興味深いですね。
それはさておき、実装はこんな感じ。

def B(R, C): return "black" if max(abs(R - 8), abs(C - 8)) % 2 else "white" print(B(3, 5)) # black print(B(4, 5)) # white

結果：提出 #35089398

参考までに、3つの「距離1」を図示するとこんな感じです。

# 縮小表示 import numpy as np from matplotlib import pyplot as plt fig, ax = plt.subplots(figsize=(8, 3)) angle = np.linspace(0, 2 * np.pi, 100) x = np.cos(angle) y = np.sin(angle) ax.plot(x, y, label="Euclidean distance") x = np.linspace(1, -1, 50) y = 1 - np.abs(x) ax.plot( np.concatenate([x, x[::-1]]), np.concatenate([y, -y]), label="Manhattan distance" ) ax.plot([1, -1, -1, 1, 1], [1, 1, -1, -1, 1], label="Chebyshev distance") ax.spines[:].set_position("center") ax.axis("equal") ax.legend(loc="upper left", bbox_to_anchor=(0, 1)) plt.show()

自由欄

C - Matrix Reducing

やってみよう！

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

test_dataC = [ { "in": [ [ [1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], ], [[6, 8, 9], [16, 18, 19]], ], "out": "Yes", }, {"in": [[[1, 1, 1], [1, 1, 1], [1, 1, 1]], [[2]]], "out": "No"}, ] def C(A, B): pass test_all(C)

自由欄

try

コンテスト中にACした回答が以下。
行・列方向でBがサブセットになるようにAを抽出できればオッケーでしょう、という考え方です。

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)

結果：提出 #34007950

実は不正解だった😭

後日(というかこの記事を書きながら)改めてACしたコードを提出してみるとWAになりました。

提出 #35153007

どうやらコンテスト後に追加されたテストケースのようです。

で、改めて提出したコードについて考えてみると以下のような問題がありました。

NoのケースでYesとしてしまう
以下のようなケースでは、行・列いずれの方向でもBはAのサブセットになるのでYesを返してしまいます。

A = [ [2, 1], [1, 2], ] B = [ [1, 2], [2, 1], ] C(A, B)

YesのケースでNoとしてしまう
以下のようなケースではAの1行目と2列目を削除するとBに一致しますが、コード上はまずAの1行目を保持して2行目を削除してしまうので"No"を返すことになります。

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)

無事AC
結果：提出 #35155638

ちなみに14行目のnp.allをnp.allcloseとすると、ACにはなるものの時間ギリギリになってしまいました(提出 #35155358)。

その他の解説

ここまでやって解説 by kyopro_friendsを見るとまんま同じでした。
解説 by hamayanhamayanも全探索。
解説 by cirno3153はよくわからん。

自由欄

D - "redocta".swap(i,i+1)

やってみよう！

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

test_dataD = [ {"in": "catredo", "out": 8}, {"in": "atcoder", "out": 0}, {"in": "redocta", "out": 21}, ] def D(*S): pass test_all(D)

自由欄

try

バブルソートの実装です。
正直、D問題のレベルではないと思います。
(バブルソートってどんなんだっけとコンテスト中にググったのは内緒です。)

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 ans test_all(D)

結果：提出 #34012391

解説を見る

なんて調子に乗りながら解説を見ると、幅優先探索だったり転倒数だったり小難しい解法が紹介されています。

という訳でちょっと調べてみました。
どうやらこの問題で求める値のような数を転倒数というらしいです。
そしてバブルソートでは$O(N^2)$掛かる計算量が、Binary Indexed Tree (BIT)というデータ構造を使えば$O(N \log N)$で求められるらしいです。(幅優先探索は知らん)

参考

ちなみに、BITで文字通りBinary Indexを実装するために必要な最下位ビット(least significant bit: LSB)を求めるための2の補数表現のpythonでの考え方については、ABC262のA問題でも解説しました。
意外なところで繋がるもんですね。

BITを使った解法

以下は基本的に上記サイトを参考に実装し(パクリ)ました。
ただパクるだけではつまらないので、初期値としてiterableを受け取れたり、基本的なlistとしても操作できるように特殊メソッドを追加しました。

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 def sum(self, i): '''get sum of data[:i] ''' total="0" while> 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 ans test_all(D)

結果：提出 #35266096

自由欄

E - Blackout 2

やってみよう！

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

test_dataE = [ { "in":[5, 5, [[2, 3], [4, 10], [5, 10], [6, 9], [2, 9], [4, 8], [1, 7], [3, 6], [8, 10], [1, 8]], [3, 5, 8, 10, 2, 7]], "out": """4 4 2 2 2 1""" }, ] def E(N, M, UV, X): pass test_all(E)

自由欄

try

ムズかった…
コンテスト中にACならず、翌日に解説を読んでもうまく実装できず寝かしておりました💦

改めて解説のエッセンス(逆から見る、発電所を全て同一視)を取り込んで、頑張って幅優先探索で実装したのが以下。

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)

結果：#35422923

自由欄

DSU -- Union-Find --

さて、解説ではなにやらAtcoder提供のライブラリを使用してサクッと実装しています。ズルい！！
そんなズルい武器はどんどん自分のものにしていきたいところです。

という訳で以下DSU(Disjoint Set Union、または素集合データ構造：disjoint-set data structure、またはunion–find data structure)を使って解いてみます。(呼び名が多い…)

参考

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)

結果：#35458365

無事AC。こんなシンプルな実装で解けてしまうとは…！恐るべしUnion-Find

自由欄

まとめ

学びの多い回でした。

以上！