ABC291の振り返り(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 - camel Case

提出：#39225518

B - Trimmed Mean

提出：#39231783

C - LRUD Instructions 2

やってみよう！

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

test_dataC = [ { "in":[5, "RLURU"], "out": "Yes" },{ "in":[20, "URDDLLUUURRRDDDDLLLL"], "out": "No" } ] def C(N, S): pass test_all(C)

自由欄

振り返り

振り返ってゼロからやってみたのがこちら。

from collections import defaultdict def C(N, S): move = { "R": lambda x, y: (x + 1, y), "L": lambda x, y: (x - 1, y), "U": lambda x, y: (x, y + 1), "D": lambda x, y: (x, y - 1), } now = (0, 0) points = defaultdict(int, {now: 1}) for c in S: nxt = move[c](*now) if points[nxt]: return "Yes" break else: points[nxt] += 1 now = nxt else: return "No" test_all(C)

結果：#39371279

自由欄

コンテスト中

コンテスト中の提出がこちら。
とりあえずsetにぶっこんで後から要素数を数えてるんですね。
なんかコンテスト中のほうが時間に追われてるせいか、無駄がない実装ができてるな笑(でも1回WA出したのは内緒)

def C(N, S): move = { "R": lambda x, y: (x + 1, y), "L": lambda x, y: (x - 1, y), "U": lambda x, y: (x, y + 1), "D": lambda x, y: (x, y - 1), } now = (0, 0) points = set([now]) for c in S: now = move[c](*now) points.add(now) return "No" if len(points) == (N + 1) else "Yes" test_all(C)

結果：#39240915

自由欄

D - Flip Cards

やってみよう！

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

test_dataD = [ { "in":[3, [[1, 2], [4, 2], [3, 4]]], "out": 4 },{ "in":[4, [[1, 5], [2, 6], [3, 7], [4, 8]]], "out": 16 },{ "in":[8, [[877914575, 602436426], [861648772, 623690081], [476190629, 262703497], [971407775, 628894325], [822804784, 450968417], [161735902, 822804784], [161735902, 822804784], [822804784, 161735902]]], "out": 48 }, ] def D(N, AB): pass test_all(D)

自由欄

コンテスト中

単純なDPです。
段々DPが解けるようになってきて嬉しい😊

def D(N, AB): dp = [[0] * 2 for _ in range(N)] dp[0][0] = 1 dp[0][1] = 1 for i in range(1, N): if AB[i][0] != AB[i - 1][0]: dp[i][0] += dp[i - 1][0] if AB[i][0] != AB[i - 1][1]: dp[i][0] += dp[i - 1][1] if AB[i][1] != AB[i - 1][0]: dp[i][1] += dp[i - 1][0] if AB[i][1] != AB[i - 1][1]: dp[i][1] += dp[i - 1][1] dp[i][0] %= 998244353 dp[i][1] %= 998244353 return sum(dp[-1]) % 998244353 test_all(D)

結果：#39253036

自由欄

E - Find Permutation

やってみよう！

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

test_dataE = [ { "in":[3, 2, [[3, 1], [2, 3]]], "out": """Yes 3 1 2\n""" },{ "in":[3, 2, [[3, 1], [3, 2]]], "out": """No\n""" },{ "in":[4, 6, [[1, 2], [1, 2], [2, 3], [2, 3], [3, 4], [3, 4]]], "out": """Yes 1 2 3 4\n""" }, ] from io import StringIO def E(N, M, XY): out = StringIO() print("answer", file=out) return out.getvalue() test_all(E)

自由欄

コンテスト中

コンテスト中は「DFSで葉まで辿り着いた時に全ての数字を通っていれば"Yes"だろう」って考えで実装したのが以下。
ブラウザ環境で実行するために余計な処理が入ってますが、基本は単純なDFSです。

が、TLEとなりその後微修正を繰り返すもACならず試合終了。

from collections import defaultdict, deque def E(N, M, XY): out = StringIO() edge = defaultdict(list) larger = set() for X, Y in XY: larger.add(Y) edge[X].append(Y) route = [] exit = [False] def dfs(n): if exit[0]: return route.append(n) if len(route) == N: _, ans = zip(*sorted(zip(route, range(1, N + 1)))) print("Yes", file=out) print(*ans, file=out) exit[0] = True for nxt in edge[n]: dfs(nxt) route.pop() first = set(range(1, N + 1)) - larger if len(first) > 1: print("No", file=out) else: dfs(first.pop()) if not exit[0]: print("No", file=out) return out.getvalue() test_all(E)

結果：#39261710

振り返り

「DFSの計算量って$O(N + M)$なのになんでTLEなんの！？😡」と思ったのですが、今回のように「葉にたどり着いたときに全ての数字を通っている」ことを確認するためには一度通った頂点や辺を何度も重複して探索する必要があるんですね。
通常の全探索を行うDFSなら一度通った頂点はパスするので$O(N + M)$になりますが、上の実装では上記理由からその処理を行っていないのでTLEになるのは当然だったのでした…

ではどうするか。
今回の問題では最短経路ならぬ最長経路を求めているようなものなので、ある頂点に辿り着く経路が複数ある場合、その経路が短い方は明らかに解ではありません。
そのような管理ができるのはBFSで、最短経路を求めるように探索しながら、ある頂点に辿り着いたときにその頂点に辿り着ける別の未探索の経路がある場合にはそれ以上探索しない(最短経路探索なので未探索の経路の方が長い)ことで計算量を$O(N + M)$に抑えることができます。

そんな感じで実装したのが以下。
数字の昇順にインデックスを繋ぐグラフをedgeで、逆方向の降順のグラフをegdeで管理することで上の考えを実現できました。

from collections import defaultdict, deque def E(N, M, XY): edge = defaultdict(set) egde = defaultdict(set) larger = set() for X, Y in XY: larger.add(Y) edge[X].add(Y) egde[Y].add(X) route = defaultdict(int) first = set(range(1, N + 1)) - larger if len(first) > 1: return "No\n" first = first.pop() q = deque([first]) while q: now = q.popleft() for nxt in edge[now]: if len(egde[nxt]) > 1: egde[nxt].remove(now) continue route[nxt] = now q.append(nxt) ans = [] while now != 0: ans.append(now) now = route[now] if len(ans) < N: return "No\n" else: _, ans = zip(*sorted(zip(ans[::-1], range(1, N + 1)))) return "Yes\n" + " ".join(map(str, ans)) + "\n" test_all(E)

結果：#39377313

解説で言及されているトポロジカルソートについては、いつか勉強します😇

自由欄