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

Arakaki Tokyo -

振り返りです。

Daiwa Securities Co. Ltd. Programming Contest 2022 Autumn (AtCoder Beginner Contest 277) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoderAtCoder Inc.
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 - ^{-1}

略

自由欄

B - Playing Cards Validation

やってみよう！

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

test_dataB = [ { "in":[4, ['H3', 'DA', 'D3', 'SK']], "out": "Yes" },{ "in":[5, ['H3', 'DA', 'CK', 'H3', 'S7']], "out": "No" },{ "in":[4, ['3H', 'AD', '3D', 'KS']], "out": "No" },{ "in":[5, ['00', 'AA', 'XX', 'YY', 'ZZ']], "out": "No" }, ] def B(N, S): pass test_all(B)

自由欄

try(振り返り)

コンテスト中の提出とほとんど変わりませんが、一文字との判定であれば解説通り文字列で持っててよかったなーと。

def B(N, S): first = "HDCS" second = "A23456789TJQK" for a, b in S: if a in first and b in second: continue else: return "No" if len(set(S)) == N: return "Yes" else: return "No" test_all(B)

結果：#36736418

自由欄

try(振り返り2)

2つ目の解説に倣って正規表現使ってみます。

import re def B(N, S): pat = re.compile(r'[HDCS][A23456789TJQK]') if not all(re.match(pat, s) for s in S): return "No" if len(set(S)) == N: return "Yes" else: return "No" test_all(B)

結果：#36737255

C - Ladder Takahashi

やってみよう！

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

test_dataC = [ { "in":[4, [[1, 4], [4, 3], [4, 10], [8, 3]]], "out": 10 },{ "in":[6, [[1, 3], [1, 5], [1, 12], [3, 5], [3, 12], [5, 12]]], "out": 12 },{ "in":[3, [[500000000, 600000000], [600000000, 700000000], [700000000, 800000000]]], "out": 1 }, ] def C(N, AB): pass test_all(C)

自由欄

try(コンテスト中)

単純なBFSです。

from collections import deque def C(N, AB): edge = {1: []} def f(x, y): if x in edge: edge[x].append(y) else: edge[x] = [y] for a, b in AB: f(a, b) f(b, a) q = deque([1]) passed = set([1]) while q: now = q.popleft() for e in edge[now]: if e in passed: pass else: passed.add(e) q.append(e) return max(passed) test_all(C)

結果：#36422346

try(振り返り)

連結成分と言えば、解説でも言及されているUnion-Find(DSU)ですね！
ABC264のEやABC269のDでもお世話になりました。

ただし、本問の場合$10^9$階建てのビルなので階数分の要素数のリストを作るとそれだけでTLEとなってしまいます。
という訳で、解説で使われてるdefaultdictを使ってみました。
これ、存在有無判定しなくていいからめっちゃ便利ですね。

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 C(N, AB): dsu = DSU() for a, b in AB: dsu.merge(a, b) return max(dsu.members(1)) test_all(C)

結果：#36746996

自由欄

D - Takahashi's Solitaire

やってみよう！

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

test_dataD = [ { "in":[9, 7, [3, 0, 2, 5, 5, 3, 0, 6, 3]], "out": 11 },{ "in":[1, 10, [4]], "out": 0 },{ "in":[20, 20, [18, 16, 15, 9, 8, 8, 17, 1, 3, 17, 11, 9, 12, 11, 7, 3, 2, 14, 3, 12]], "out": 99 } ] def D(N, M, A): pass test_all(D)

自由欄

try

設問を読んで、「結局連続の数字のカードを出せるってこと？」という浅い理解で提出したらWAとなりました…
modの意味をよくよく考えてみると、「カードの最大値が$M-1$の場合、次に$0$の数字のカードを出せる」と気づいてACした提出が以下。

def D(N, M, A): B = {} total = 0 for a in A: total += a if a in B: B[a] += a else: B[a] = a mx = [] Bs = sorted(B) tmp = B[Bs[0]] for i, b in enumerate(Bs[1:], 1): if Bs[i - 1] == b - 1: tmp += B[b] else: mx.append(tmp) tmp = B[b] if mx and Bs[0] == 0 and Bs[-1] == M - 1: mx[0] += tmp else: mx.append(tmp) return total - max(mx) test_all(D)

結果：

自由欄

E - Crystal Switches

やってみよう！

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

test_dataE = [ { "in":[5, 5, 2, [[1, 3, 0], [2, 3, 1], [5, 4, 1], [2, 1, 1], [1, 4, 0]], [3, 4]], "out": 5 },{ "in":[4, 4, 2, [[4, 3, 0], [1, 2, 1], [1, 2, 0], [2, 1, 1]], [2, 4]], "out": -1 }, ] def E(*n): pass test_all(E)

自由欄

try(振り返り)

コンテスト中は設問を読んだ瞬間に諦めました…
という訳で早速解説を見ます。

01BSFとはなんぞ？ということで以下も参照
01-BFSのちょっと丁寧な解説 - ARMERIA

from collections import deque, defaultdict def E(N, M, K, uva, s): edge = defaultdict(list) for u, v, a in uva: if not a: u = -u v = -v edge[u].append(v) edge[v].append(u) for s in s: edge[s].append(-s) edge[-s].append(s) q = deque([1]) passed = set([1]) route = {} while q: now = q.popleft() for e in edge[now]: if e in passed: continue route[e] = now if e == N or -e == N: break if now == -e: q.appendleft(e) else: q.append(e) passed.add(e) else: continue break else: return -1 ans = 0 now = e while now != 1: nxt = route[now] if now != -nxt: ans += 1 now = nxt return ans test_all(E)

結果：#36759317

自由欄

自由欄