ABC277の振り返り(A, B, C, D, E)
振り返りです。
A - ^{-1}
略
自由欄
B - Playing Cards Validation
やってみよう!
B
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
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」ボタンをクリックしよう!
自由欄
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
を使ってみました。
これ、存在有無判定しなくていいからめっちゃ便利ですね。
結果:#36746996
自由欄
D - Takahashi's Solitaire
やってみよう!
D
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
try
設問を読んで、「結局連続の数字のカードを出せるってこと?」という浅い理解で提出したらWAとなりました…
modの意味をよくよく考えてみると、「カードの最大値が$M-1$の場合、次に$0$の数字のカードを出せる」と気づいてACした提出が以下。
結果:
自由欄
E - Crystal Switches
やってみよう!
E
関数を完成させて「Run」ボタンをクリックしよう!
自由欄
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)アライグマ「E問題は頂点倍化して01BFSなのだ! スイッチを押した世界線と押してない世界線を行き来するのだ!」 pic.twitter.com/mxqPkTckaT
— 競技プログラミングをするフレンズ (@kyopro_friends) November 12, 2022
結果:#36759317
自由欄