ABC287の振り返り(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 - Majority

略

B - Postal Card

やってみよう！

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

test_dataB = [ { "in":[3, 3, ['142857', '004159', '071028'], ['159', '287', '857']], "out": 2 },{ "in":[5, 4, ['235983', '109467', '823476', '592801', '000333'], ['333', '108', '467', '983']], "out": 3 },{ "in":[4, 4, ['000000', '123456', '987111', '000000'], ['000', '111', '999', '111']], "out": 3 }, ] def B(N, M, S, T): pass test_all(B)

自由欄

振り返り

コンテスト中の提出は想定解と同様に素朴な2重ループで実装したのですが、dict等でTを持てば$O(1)$で判定できるので2重ループの$O(N \times M)$から$O(N + M)$に改善できますね。

from collections import defaultdict def B(N, M, S, T): T = defaultdict(bool, {t: True for t in T}) return len([1 for s in S if T[s[3:]]]) test_all(B)

結果：#38714058

自由欄

C - Path Graph?

やってみよう！

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

test_dataC = [ { "in":[4, 3, [[1, 3], [4, 2], [3, 2]]], "out": "Yes" },{ "in":[2, 0, []], "out": "No" },{ "in":[5, 5, [[1, 2], [2, 3], [3, 4], [4, 5], [5, 1]]], "out": "No" }, ] def C(N, M, uv): pass test_all(C)

自由欄

振り返り

競プロを始めて久しぶりに凡ミスでドツボにはまった案件です。
まず最初に考えたのが、閉路判定(直近でABC285のD)と同じようにDSUでマージしていき、最終的に閉路がなく、かつ全ての頂点が連結していればYesでは？という感じで提出①するとWA…

で考え直すと、例えばXみたいな形でもYes判定してしまうので、そりゃWAなるわ。
という訳で以下のように条件を整理

閉路がない
全ての頂点が連結
全ての頂点の次数が2以下

これならXもちゃんとNo判定してくれるはず！
で提出②したらまたもWA…

コンテスト中はこっからドツボにはまる訳ですが、実は上の考え方自体はあたっていて、「2. すべての頂点が連結」を判定する実装をミスってただけでした(ミスというか、自分で作ったDSUクラスの使い方がしっかり頭に入ってなかった…アホです🤮)

という訳で、振り返って提出②を修正したのが以下。

from collections import defaultdict class DSU(): def __init__(self, n=None): self.dsu = defaultdict(lambda: -1) if n: for i in range(n): self.dsu[i] 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 __len__(self): return len([1 for v in self.dsu.values() if v < 0]) def C(N, M, uv): dsu = DSU(N + 1) edge = defaultdict(int) for u, v in uv: if dsu.leader(u) == dsu.leader(v) or edge[u] == 2 or edge[v] == 2: return "No" dsu.merge(u, v) edge[u] += 1 edge[v] += 1 if dsu.dsu[dsu.leader(1)] == -N: return "Yes" else: return "No" test_all(C)

結果：#38735323

ちなみに、コンテスト中の試行錯誤の末のAC提出ではBFSで経路保存しながら上の3つの条件を判定しました。が、迷走しただけあってカッコ悪い実装なのでここでは割愛します😇。

自由欄

D - Match or Not

やってみよう！

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

test_dataD = [ { "in":['a?c', 'b?'], "out": "Yes\nNo\nNo" },{ "in":['atcoder', '?????'], "out": "※出力略(Yes 6行)" },{ "in":['beginner', 'contest'], "out": "※出力略(No 8行)" }, ] def D(S, T): pass test_all(D)

自由欄

振り返り

コンテスト中はC問題に苦戦した影響(というのは言い訳)で、前処理して$O(|S| + |T|)$ぐらいを想定した提出がWA & TLEとなりデバッグできず…

振り返ってみると、WAの原因は判定部分のインデックスずれ、TLEの原因は|T + 1|回ループの中で配列のT個の要素を合計していて結局$O(T^2)$になってしまっていたことでした。

それぞれ修正したのが以下。

from itertools import accumulate def D(S, T): len_S = len(S) len_T = len(T) T = T m = [[0] * len_S for _ in range(2)] def check(s, i): return i < 0 or i >= len_T or "?" in [s, T[i]] or s == T[i] for i, s in enumerate(S): if not check(s, i): m[0][i] = 1 if not check(s, i - (len_S - len_T)): m[1][i] = 1 *acc, = map(lambda x: list(accumulate([0] + x)), m) for i in range(len_T + 1): print("No" if acc[0][i] + acc[1][len_S] - acc[1][len_S - (len_T - i)] else "Yes") test_all(D)

結果：#38772554

自由欄

解説を見る

WAを招いたインデックスずれですが、振り返って考えてみても頭がこんがらがってしまいました…

解説の実装例を見てみると、だいぶスッキリした印象。
無理にまとめて処理しようとせず、(実行時間が許すなら)単純な問題に分解して実装したほうが安全かつ時短で解けるということですね。勉強になります😇

というわけで解説を参考に以下。

def D(S, T): len_S = len(S) len_T = len(T) m = [] for s, t in [(S, T), (S[len_S - len_T:][::-1], T[::-1])]: tmp = [False] * len_S for i, (s, t) in enumerate(zip(s, t)): tmp[i] = "?" in [s, t] or s == t if not tmp[i]: break m.append([True] + tmp) for i in range(len_T + 1): print("Yes" if m[0][i] and m[1][len_T - i] else "No") test_all(D)

結果：#38775182

自由欄

E - Karuta

やってみよう！

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

test_dataE = [ { "in":[3, ['abc', 'abb', 'aac']], "out": """2 2 1""" },{ "in":[11, ['abracadabra', 'bracadabra', 'racadabra', 'acadabra', 'cadabra', 'adabra', 'dabra', 'abra', 'bra', 'ra', 'a']], "out": """4 3 2 1 0 1 0 4 3 2 1""" }, ] def E(N, S): pass test_all(E)

自由欄

解説を見る①

せっかくなのでE問題も見てみます。
例によって$O(N ^ 2)$以外の解法が思いつかないので解説を見ます。

文字種による分類を再帰的に適用、ですか…。かしこっ😇
そんな感じで実装したのが以下。

from collections import defaultdict def E(N, S): ans = [0] * N def rec(idx, l): abc = defaultdict(list) for i in l: try: abc[S[i][idx]].append(i) except: ans[i] = idx for sl in abc.values(): if len(sl) == 1: ans[sl[0]] = idx else: rec(idx + 1, sl) rec(0, range(N)) print(*ans, sep="\n") test_all(E)

結果：#38776249

Pythonで再帰コールの罠にかからないよう、sys.setrecursionlimitの設定と言語の選択を「Python (3.8.2)」にするのを忘れずに。(参考)

自由欄

解説を見る②

せっかくなのでもう一つの解説を見ます。

辞書順でソートして隣り合う組だけで計算すればいいのか…。かしこすぎるっ😇😇
そんな感じで実装したのが以下。

def E(N, S): ans = [0] * N S = sorted([(s, i) for i, s in enumerate(S)]) for i in range(N - 1): s1, i1 = S[i] s2, i2 = S[i + 1] for j, (a, b) in enumerate(zip(s1, s2)): if a != b: break else: j += 1 ans[i1] = max(ans[i1], j) ans[i2] = max(ans[i2], j) print(*ans, sep="\n") test_all(E)

結果：#38884805

自由欄