始めて本番中にE問題が解けた！＆パフォーマンスが1000超えた！
という訳で振り返りです。

AtCoder Beginner Contest 284 - 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}")

C - Count Connected Components

問題略

やってみよう！

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

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

自由欄

try(コンテスト中)

コンテスト中の提出がこんな感じ。
連結成分と言えばこれ、ってことで単純なDSUの実装です。

def C(N, M, uv): 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 for u, v in uv: merge(u, v) ans = 0 for v in dsu[1:]: if v < 0: ans += 1 return ans test_all(C)

結果：#37810410

自由欄

try(振り返り)

実は最初、ABC277のCでdefaultdictを使うようにしたDSUクラスを思考停止でコピペして使ってみたらテストケースでWAとなりました。
原因は孤立頂点をカウントしてなかったから。
という訳で、コンストラクタで頂点数を設定できるように、ついでにlenで連結成分の個数を返すように修正したのが以下。

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) for u, v in uv: dsu.merge(u, v) return len(dsu) - 1 test_all(C)

結果：#37924884

使い勝手がいまいちかなぁ…

D - Happy New Year 2023

やってみよう！

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

def D(N): pass D(2023) # 17 7 D(63) # 3 7 D(1059872604593911) # 104149 97711

自由欄

try

「こんなんNデカすぎて間に合う訳ないやん！」ということでコンテスト中は手が出せず…

結局、解説にある通り $min(p, q) \le\sqrt[3]{N}$ に気づけるかどうかの1点を問う問題でした。
「どれか小さい(大きい)一つに着目する」という考え方は割りと使う機会ありそう。

解説の実装例をPythonで再現してもACとなりますが、けっこう時間掛かります。
という訳で、エラトステネスの篩で素数を列挙する前処理を行うようにしたのが以下。

MAX = int((9 * 10 ** 18) ** (1/3) + 1) MAX = 100000 # ブラウザ環境用に上限設定 prime = [True] * (MAX + 1) for i in range(2, MAX + 1): if not i: continue # prime[i * 2::i] = [False] * ((MAX - i * 2) // i + 1) for j in range(i * 2, MAX + 1, i): prime[j] = False primes = [i for i in range(2, MAX + 1) if prime[i]] def D(N): for p in primes: if N % p == 0: break a = N // p if a % p == 0: print(p, a // p) else: print(int(a ** (1/2)), p) D(2023) # 17 7 D(63) # 3 7 D(1059872604593911) # 104149 97711

結果：#37945165

さすがPyPyだと速いです。

try2

numpyを使うと前処理がちょっとだけ楽になります。

import numpy as np MAX = int((9 * 10 ** 18) ** (1/3) + 1) MAX = 100000 # ブラウザ環境用に上限設定 prime = np.ones(MAX + 1, dtype=np.bool_) for i in range(2, MAX + 1): prime[i * 2::i] = False primes = [i for i in range(2, MAX + 1) if prime[i]] def D(N): for p in primes: if N % p == 0: break a = N // p if a % p == 0: print(p, a // p) else: print(int(a ** (1/2)), p) D(2023) # 17 7 D(63) # 3 7 D(1059872604593911) # 104149 97711

結果：#37876263

速度的にもまぁまぁですね。

自由欄

E - Count Simple Paths

やってみよう！

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

test_dataE = [ { "in":[4, 2, [[1, 2], [2, 3]]], "out": 3 },{ "in":[4, 6, [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]], "out": 16 },{ "in":[8, 21, [[2, 6], [1, 3], [5, 6], [3, 8], [3, 6], [4, 7], [4, 6], [3, 4], [1, 5], [2, 4], [1, 2], [2, 7], [1, 4], [3, 5], [2, 5], [2, 3], [4, 5], [3, 7], [6, 7], [5, 7], [2, 8]]], "out": 2023 }, ] def E(N, M, uv): pass test_all(E)

自由欄

try

はじめて深さ優先探索(DFS)の使い所を実感できた問題です！

以前振り返った通り、AtcoderでPythonで再帰コールでDFSを実装する場合、「recursionlimit」と「PyPyで再帰コールが遅い」という二重のトラップを回避する必要があります。
「じゃあ全探索でも最短経路でもBFSでいいや。ていうかDFSじゃないと解けない問題なんてあるん？」と思っていたところ、本問はまさにDFSじゃないと(多分)解けないでした。
最初はBFSで考えたのですが、「全ての頂点への全ての経路」なのでどうしたって一旦最後まで行かないと列挙できないんですね～。

という訳で、コンテスト中の提出を若干手直ししてこんな感じです。

from collections import defaultdict, deque import sys sys.setrecursionlimit(2 * 10 ** 6) def E(N, M, uv): route = set() ans = [0] def dfs(n): route.add(n) ans[0] += 1 if ans[0] == 10 ** 6: # print(10 ** 6) # exit() return for nxt in edge[n]: if nxt in route: continue else: dfs(nxt) route.remove(n) edge = defaultdict(list) for u, v in uv: edge[u].append(v) edge[v].append(u) dfs(1) # print(ans[0]) return ans[0] test_all(E)

結果：#37962672

振り返ってやり直した時にまたPyPyトラップに引っかかってしまった…
やっぱDFS嫌いだ😡

自由欄

F - ABCBAC

やってみよう！

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

def F(N, T): pass test_all(E) F(3, "abcbac") # abc # 2 F(4, "abababab") # abab # 1 F(3, "agccga") # cga # 0 F(4, "atcodeer") # -1

自由欄

try

コンテスト中はDを諦めてEがサービス問題で解けてしまったので、始めてFまで見てみました。
愚直な実装で当然のごとくTLEとなったので、解説を見ます。

Z algorithmとはなんぞ？という訳で以下参照。
なんとなく言いたいことは理解しましたが、実装が素晴らしくスマートですね…

def z_algorithm(S): z = [0] * len(S) z[0] = len(S) i = 1 j = 0 while i < len(S): while i + j < len(S) and S[j] == S[i + j]: j += 1 z[i] = j if j == 0: i += 1 continue k = 1 while i + k < len(S) and k + z[k] < j: z[i + k] = z[k] k += 1 i += k j -= k return z def F(N, T): a = z_algorithm(T[:N] + T[N:][::-1]) b = z_algorithm(T[N:][::-1] + T[:N]) a += [0] for i in range(0, N): if a[2 * N - i] >= i and b[N + i] >= N - i: print(T[:i] + T[N + i:]) print(i) break else: print(-1) F(3, "abcbac") # abc # 2 F(4, "abababab") # abab # 1 F(3, "agccga") # cga # 0 F(4, "atcodeer") # -1

結果：#37908061

自由欄

自由欄