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

振り返りです。

Sky Inc, Programming Contest 2023(AtCoder Beginner Contest 289) - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
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 - flip

やってみよう!

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

test_dataA = [ { "in":["01"], "out": "10" },{ "in":["1011"], "out": "0100" },{ "in":["100100001"], "out": "011011110" }, ] def A(s): pass test_all(A)

自由欄

振り返り

初っ端から遊び心をくすぐられる問題です。
なので遊んでみます。

典型例

オーソドックスな方法としては一旦別の文字に置き換えてから置換するパターン。
コンテスト中もこんな感じで提出しました。

def A(s): return ( s .replace("0", "2") .replace("1", "0") .replace("2", "1") ) test_all(A)

結果:#39087495

ビットXORを使う

インプットが01なので、ビット列に見立てて演算ができます。
1111111...との排他的論理和を取るのもありふれた手法ですね。

def A(s): return bin(int(s, base=2) ^ ((1 << 11) - 1))[-len(s):] test_all(A)

結果:#39087684

愚直解

普通にループを回してもいいでしょう。
ここでは01をbooleanとしてnotで反転させてます。

def A(s): return "".join([str(int(not int(c))) for c in s]) test_all(A)

結果:#39087915

解説を見る

解説によるとPythonではtranslateメソッドが使えるとのこと。
知らなかった…

def A(s:str): return s.translate(str.maketrans("01", "10")) test_all(A)

結果:#39089523

自由欄

B - レ

やってみよう!

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

test_dataB = [ { "in":[5, 3, [1, 3, 4]], "out": "2 1 5 4 3" },{ "in":[5, 0, []], "out": "1 2 3 4 5" },{ "in":[10, 6, [1, 2, 3, 7, 8, 9]], "out": "4 3 2 1 5 6 10 9 8 7" }, ] def B(N, M, a): pass test_all(B)

自由欄

コンテスト中

全然しっくりくるロジックが思いつかなくてめっちゃ時間掛かりました😇
結局、レ点が続く限り範囲を広げ、途切れたらその範囲を逆順にする、みたいな実装でAC。
以下はちょっとキレイにした版。

def B(N, M, a): a = a + [0] ans = list(range(1, N + 1)) cnt = 1 for i in range(M): if a[i + 1] == a[i] + 1: cnt += 1 else: s = slice(a[i] - cnt, a[i] + 1) ans[s] = ans[s][::-1] cnt = 1 return " ".join(map(str, ans)) test_all(B)

結果: #39090005

自由欄

振り返り

で、振り返ると問題文通りに実装したほうが結局早かったんじゃね?となりました。
それが以下。

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 B(N, M, a): dsu = DSU(N + 1) for ai in a: dsu.merge(ai, ai + 1) tmp = defaultdict(list) for i in range(1, N + 1): tmp[dsu.leader(i)].append(i) ans = [] for _, v in sorted(tmp.items()): ans.extend(v[::-1]) return " ".join(map(str, ans)) test_all(B)

結果: #39091003

問題文ちゃんと読もう…

自由欄

C - Coverage

やってみよう!

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

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

自由欄

try

制約が小さいので全探索です。

from itertools import combinations def C(N, M, S): *S, = map(set, S) target = set(range(1, N + 1)) ans = 0 for i in range(1, M + 1): for com in combinations(S, i): if target.issubset(set().union(*com)): ans += 1 return ans test_all(C)

結果:#38806454

自由欄

D - Step Up Robot

やってみよう!

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

test_dataD = [ { "in":[3, [3, 4, 5], 4, [4, 5, 6, 8], 15], "out": "Yes" },{ "in":[4, [2, 3, 4, 5], 4, [3, 4, 5, 6], 8], "out": "No" },{ "in":[4, [2, 5, 7, 8], 5, [2, 9, 10, 11, 19], 20], "out": "Yes" }, ] def D(N, A, M, B, X): pass test_all(D)

自由欄

コンテスト中

数字を作る系の問題って結構出題頻度高いですね。(ref. ABC271のD, ABC274のD, ABC286のD)
そして未だに自分の中で型が定まらずに毎回苦戦してしまってます…

今回もこれまでと同じような実装をしたものの、TLEを解消できず試合終了。

def D(N, A, M, B, X): B = set(B) dp = set([0]) while True: new = set() for d in dp: for a in A: if a + d in B or a + d > X: pass else: new.add(a + d) if X in new: return "Yes" if not new: return "No" dp = new test_all(D)

結果:#38816439

TLE x 2 😭

自由欄

振り返り

振り返ってよくよく考えてみると、

  • 恐らくNoのケースでAの小さい数字がXを超えるまでループを回してしまうのがTLEの原因かなぁ
  • いやいや、ケースにかかわらずAの小さい数字で新たに作れる数字って既に出てる可能性高くね?それら重複して何度も検討しちゃってね?

という訳で、既に出た数字はもう検討しないという実装にしたのが以下。

def D(N, A, M, B, X): B = set(B) dp = set([0]) found = set() while True: new = set() for d in dp: for a in A: if a + d in B or a + d > X: pass elif a + d not in found: new.add(a + d) found.add(a + d) if X in new: return "Yes" if not new: return "No" dp = new test_all(D)

結果:#39172731

最大実行時間101ms
圧倒的に速度改善できました。ということは、もとの実装ではめちゃくちゃ無駄が多かったということですね…

自由欄

E - Swap Places

やってみよう!

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

test_dataE = [ { "in":[4, 4, [None, 0, 1, 0, 1], {1: [2, 3], 2: [1, 3, 4], 3: [2, 1], 4: [2]}], "out": 3 },{ "in":[3, 3, [None, 0, 1, 0], {1: [2, 3], 2: [1, 3], 3: [2, 1]}], "out": -1 },{ "in":[6, 6, [None, 0, 0, 1, 1, 0, 1], {1: [2], 2: [1, 6, 4], 6: [2, 3, 4], 3: [6], 4: [6, 5, 2], 5: [4]}], "out": 3 }, ] def E(N, M, C, edge): pass test_all(E)

自由欄

try

せっかくなのでE問題も見てみます。分かりません。解説を見ます。(定型文になってるな…)
「う~ん、言いたいことは何となく伝わるけどどう実装すればいいんだ😖」と諦めかけた矢先、類題としてABC272のDが紹介されています。

過去の俺、どうにか頑張って自力ACしとる…!
なんだか退化してるような疑念は横に置いといて、過去の実装を参考にしたのが以下。(ちゃんと振り返ってブログに残しとくって大事ね)

from collections import defaultdict, deque from itertools import product def E(N, M, C, edge): init = [(1, N)] q = deque(init) step = [[0] * (N + 1) for _ in range(N +1)] while q: now = q.popleft() for nxt in product(edge[now[0]], edge[now[1]]): a, b = nxt if C[a] == C[b] or step[a][b]: continue step[a][b] = step[now[0]][now[1]] + 1 if nxt == (N, 1): return step[a][b] else: q.append(nxt) else: return -1 test_all(E)

結果:#39178709

実は上に辿り着くまで、既に見た状態をsetで管理したり、stepdictで管理するような実装にしたらTLEとなりなかなか抜け出せませんでした😭
存在判定だったり$O(1)$で特定の値を更新・取得する目的であれば配列が最も効率的だと再認識。

自由欄

自由欄