ABC270の振り返り(A, B, C, D)

振り返りです。

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-2-4 Test

やってみよう！

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

def A(A, B): pass A(1, 2) # 3 A(5, 3) # 7 A(0, 0) # 0

自由欄

try

配点が1, 2, 4なんて都合よくあるか！と言いたくなりますが、2の累乗で特定の項目のフラグを管理してその合計値で表現するなんてことはままあったりします。例えばLinuxのファイルのパーミッションとか。(参考：パーミッションを表す数値
直近だとABC264のD問題で使ったBITなど、ビット演算を用いたアルゴリズムも意外にある(はずな)ので基本を抑えておきたいところですな。

def A(A, B): print(A | B) A(1, 2) # 3 A(5, 3) # 7 A(0, 0) # 0

結果：#35092854

try2

from operator import or_ as bo def A(*arg): print(bo(*arg)) A(1, 2) # 3 A(5, 3) # 7 A(0, 0) # 0

結果：#35769287

自由欄

B - Hammer

やってみよう！

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

test_dataB = [ { "in":[10, -10, 1], "out": 10 },{ "in":[20, 10, -10], "out": 40 },{ "in":[100, 10, 1000], "out": -1 }, ] def B(X, Y, Z): pass test_all(B)

自由欄

try(コンテスト中)

このような単純な場合分けの問題が結構苦手です…

def B(X, Y, Z): if abs(X) > abs(Y) and X * Y > 0: if Y * Z > 0: if abs(Y) < abs(Z): return -1 else: return abs(X) else: return abs(Z) * 2 + abs(X) else: return abs(X) test_all(B)

結果：#35101624

try(振り返り)

振り返っても大体同じになりました。

def B(X, Y, Z): if abs(X) < abs(Y) or X * Y < 0: return abs(X) else: if Y * Z < 0: return abs(X - 2 * Z) elif abs(Z) > abs(Y): return -1 else: return abs(X) test_all(B)

結果：#35788168

解説

解説でも大体一緒なんですが、壁を壊す場合はabs(Z) + abs(X - Z)でまとめられるんですね！
どうやったらこんな発想ができるんだろう…🤔

自由欄

C - Simple path

やってみよう！

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

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

自由欄

try

コンテスト中の提出が以下(BFS)。
DFSでの実装でREが出たり(後述)、BFSで経路を保存する方法を調べたりして時間掛かりました…

from collections import deque def C(N, X, Y, UV): edge = [[] for _ in range(N+1)] for u, v in UV: edge[u].append(v) edge[v].append(u) route = [None] * (N + 1) q = deque([X]) while len(q): now = q.popleft() for n in edge[now]: if route[n] is None: route[n] = now if n == Y: break q.append(n) else: continue break ans = [Y] now = Y while now != X: now = route[now] ans.append(now) return " ".join(map(str, ans[::-1])) test_all(C)

結果：#35130541

解説を見る

元々DFSの実装に自信無かったので、コンテスト中のデバッグは諦めて上のBFSに切り替えました。
解説がちょうどDFSなのでPythonで書き換えたのが以下。

from collections import deque def C(N, X, Y, UV): flag = [False] * (N + 1) s = [] stop = False def dfs(k, to): nonlocal stop if stop: return else: s.append(k) if k == to: stop = True return flag[k] = True for i in edge[k]: if not flag[i]: dfs(i, to) if not stop: s.pop() edge = [[] for _ in range(N+1)] for u, v in UV: edge[u].append(v) edge[v].append(u) dfs(X, Y) import io out = io.StringIO() print(*s, file=out, end="") return out.getvalue() test_all(C)

結果：#35811853

REやんけ！！！！！！

なぜDFSでREになるのか？

ググったところ、どうやら原因はsys.getrecursionlimit()とのこと。

この制限は Python プログラムが無限に再帰し、C スタックがオーバーフローしてクラッシュすることを防止するために設けられています。

sys.setrecursionlimit(limit)で設定を変更できます。

import sys sys.getrecursionlimit() def recur(n): '''再帰コール確認''' print(n, end=" ") if n: recur(n - 1) sys.setrecursionlimit(50) # 40回ぐらいでRecursionErrorが出る recur(40)

今回の問題では$1 \le N \le 2 \times 10^5$ で頂点を辿る度に再帰呼び出しを行うので、sys.setrecursionlimit(2 * 10 ** 6)をコードの最初に挿入してみました。
すると…

結果：#35811986

TLEやんけ！！！！！

なぜTLEになるのか？

はい、またググりました。どうやらPyPyは再帰コールが遅いらしいです。
という訳でPythonで提出してみました。
すると…

結果：#35812008

ようやくAC😇

小括

まとめると、「recursionlimit」と「PyPyで再帰コールが遅い」という二重のトラップが仕掛けられていた訳ですね…
というか、この2つを回避すればコンテスト中に最初に提出したDFS(以下)でもACできてたというオチ。

from collections import deque import sys sys.setrecursionlimit(2 * 10 ** 6) route = [] def C(N, X, Y, UV): def dfs(n): route.append(n) if n == Y: print(*route) # exit() # 提出用 for nxt in edge[n]: if len(route) >= 2 and nxt == route[-2]: continue else: dfs(nxt) route.pop() edge = [[] for _ in range(N+1)] for u, v in UV: edge[u].append(v) edge[v].append(u) dfs(X) test_all(C)

結果：#35812113

再帰コールせずにDFSの実装

最後に表題の件。
再帰版のDFSの実装ってグローバル変数をいじるところが前からイヤだったんすよね😩
今回Atcoderでの2つのトラップを知り、基本的に使わないという方針を採ることにしました。

ただ、どうしてもDFSを使いたい場合(ってあるのか？)にどうするか。
再帰を使わず実装すればいいじゃない！
という訳で以下。BFSでのキュー(FIFO)をスタック(LIFO)に変えるだけです。

def C(N, X, Y, UV): edge = [[] for _ in range(N+1)] for u, v in UV: edge[u].append(v) edge[v].append(u) route = [None] * (N + 1) q = [X] while len(q): now = q.pop() for n in edge[now]: if route[n] is None: route[n] = now if n == Y: break q.append(n) else: continue break ans = [Y] now = Y while now != X: now = route[now] ans.append(now) return " ".join(map(str, ans[::-1])) test_all(C)

結果：#35921859

いまいちDFSとBFSの使い分け、というかDFSの使い所が分かってないです…
BFSだったら探索だけじゃなくて最短経路にも使えるから、基本BFSでいいんじゃないかなぁ

自由欄

D - Stones

やってみよう！

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

test_dataD = [ { "in":[10, 2, [1, 4]], "out": 5 },{ "in":[11, 4, [1, 2, 3, 6]], "out": 8 },{ "in":[10000, 10, [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]], "out": 5136 }, ] def D(N, K, A): pass test_all(D)

自由欄

try(コンテスト中)

コンテスト中に想定誤解法のようなコードを書いて、想定通りWAとなりました…

from bisect import bisect def D(N, K, A): ans = 0 i = 0 while N >= A[0]: get = A[bisect(A, N) - 1] if i % 2 == 0: ans += get N -= get i += 1 return ans test_all(D)

結果：#35133986

解説を見る

「最適な行動」系の問題はまだ全然イメージが掴めないのでさっさと解説を見ます。

要点は以下の通り

$DP[n]$ = 石が$n$個残っている状態からゲームを始めたとき、先手が取ることのできる石の個数

遷移：$DP[n] = \max{A_i + (n - A_i) - DP[n - A_i] \;|\; A_i \le n}$

遷移の意味：先手番が$A_i$個の石を取ったとき、最終的に取れる石の個数は、$A_i$+「石が$n-A_i$個残っている状態からゲームを始めたとき、後手が取ることのできる石の個数」なので、これを全ての$i$について調べて$\max$を取ったものが求める値

実装例をPythonで書き換えたのが以下。
めっちゃ短いです…
が、「石がn個残っている状態からゲームを始める」とか「後手が取れる石の数を引く」とかいう発想ができないとそもそもロジック立てられないんですよね…
勉強になります😇

def D(N, K, A): dp = [0] * (N + 1) for i in range(N + 1): for a in A: if a > i: break dp[i] = max(dp[i], i - dp[i - a]) return dp[N] test_all(D)

結果：#35924245

自由欄