振り返りです。

UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - 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 - Range Swap

B - Cat

C - Rotate and Palindrome

やってみよう!

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

test_dataC = [ { "in":[5, 1, 2, 'rrefa'], "out": 3 },{ "in":[8, 1000000000, 1000000000, 'bcdfcgaa'], "out": 4000000000 } ] def C(N, A, B, S): pass test_all(C)

自由欄

try

こんなんどうすりゃいいんだ…とコンテスト中は早々にスルーしましたが、解説を見るとなんてことはない全探索でした。
という訳で以下。

def C(N, A, B, S): ans = B * (N // 2) for i in range(N): total = A * i for l, r in zip(S[:N // 2], S[(N + 1) // 2:][::-1]): if l != r: total += B ans = min(ans, total) S = S[1:] + S[:1] return ans test_all(C)

結果:#38485608

解説の実装例

ここまでやって解説をスクロールすると、実装例のほうが断然スッキリしてますね…
という訳で参考にしてこんな感じ。Sを倍加させて範囲を探索していくという手法はどこかで使えそう。

def C(N, A, B, S): ans = B * (N // 2) S += S for i in range(N - 1): total = A * i for j in range(N // 2): if S[i + j] != S[i + (N - 1 - j)]: total += B ans = min(ans, total) return ans test_all(C)

自由欄

D - Money in Hand

やってみよう!

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

test_dataD = [ { "in":[2, 19, {2: 3, 5: 6}], "out": "Yes" },{ "in":[2, 18, {2: 3, 5: 6}], "out": "No" },{ "in":[3, 1001, {1: 1, 2: 1, 100: 10}], "out": "Yes" }, ] def D(N, X, AB): pass test_all(D)

自由欄

try

単純な数字を作る系の問題です。…ですがRE×3, TLE×1とかなり苦戦してしまいました😭
過去の同様の問題(ABC271のDABC274のD)を参考にしたのですが、過去提出に引っ張られて適切な実装ができず、紆余曲折を経てACしたのが以下。
無駄に関数化してるのはABC274から援用した名残です…

def D(N, X, AB): seed = [] for A, B in AB.items(): seed += [A] * B def search(seed, target): numbers = set([0]) for s in seed: for n in list(numbers): nxt = n + s if nxt == target: return True if nxt < target: numbers.add(nxt) return False return "Yes" if search(seed, X) else "No" test_all(D)

結果:#38215755

自由欄

振り返り

なぜ上でsetを使っているのかというと、DP配列を使った実装だとどうにもREが解決できなかったからでした。
という訳でまっさらな状態からやり直してみたのが以下。

def D(N, X, AB): seed = [] for A, B in AB.items(): seed += [A] * B dp = [True] + [False] * X for s in seed: for i in range(X - s, -1, -1): if dp[i]: dp[i + s] = True return "Yes" if dp[X] else "No" test_all(D)

結果:#38524547

上を微修正してループの中でYesを判定するようにした提出では若干早くなりましたが、判定条件にちょっと注意です。

自由欄

バグ取り

コンテスト中のREとなった提出を解決しないと気持ち悪いので考えてみたのですが、結論わかりませんでした😇
コードを整理して、下記はACとなるのですがコメントアウト部分を採用するとREになってしまいます。
処理は同じはずなのに…

def D(N, X, AB): seed = [] for A, B in AB.items(): seed += [A] * B dp = [True] + [False] * X for s in seed: new = dp.copy() # for i, b in enumerate(dp[: X + 1 - s]): # if b: new[i + s] = True for i in range(X + 1 - s): if dp[i]: new[i + s] = True if new[-1]: return "Yes" dp = new return "No" test_all(D)

結果
 RE:#38525368
 AC:#38525401

自由欄

解説を見る

最後に、解説で紹介されている$O(NX)$の解法を写経してみました。
解説を読んでもコードを追っても、何をやってるか理解できません…

def D(N, X, AB): A, B = zip(*AB.items()) mx = [0] * 100 dp = [True] + [False] * X for i in range(N): for j in range(A[i]): mx[j] = -10000 for j in range(X + 1): if dp[j]: mx[j % A[i]] = j if mx[j % A[i]] >= j - (A[i] * B[i]): dp[j] = True else: dp[j] = False return "Yes" if dp[X] else "No" test_all(D)

結果:#38550084

自由欄

小括

振り返っても全然スッキリしない…
またいつか見直します!

E - Souvenir

やってみよう!

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

test_dataE = [ { "in":[5, [30, 50, 70, 20, 60], ['NYYNN', 'NNYNN', 'NNNYY', 'YNNNN', 'YNNNN'], 3, [[1, 3], [3, 1], [4, 5]]], "out": """1 100 2 160 3 180""" },{ "in":[2, [100, 100], ['NN', 'NN'], 1, [[1, 2]]], "out": "Impossible" }, ] def E(N, A, S, Q, UV): pass test_all(E)

自由欄

try

コンテスト中はどうにか幅優先探索(BFS)で攻略できないかと試行錯誤したのですがダメでした…
コードぐちゃぐちゃだったので、振り返って整理したのが以下。

from collections import deque, defaultdict def E(N, A, S, Q, UV): A = [0] + A edge = defaultdict(list) for i, s in enumerate(S, 1): for j, k in enumerate(s, 1): if k == "Y": edge[i].append(j) for u, v in UV: value = [0] * (N + 1) value[u] = A[u] step = [N] * (N + 1) step[u] = 0 q = deque([u]) while q: now = q.popleft() if now == v: break for city in edge[now]: if step[city] > step[now] + 1: step[city] = step[now] + 1 value[city] = value[now] + A[city] q.append(city) elif step[city] == step[now] + 1: value[city] = max(value[city], value[now] + A[city]) else: print("Impossible") continue print(step[v], value[v]) test_all(E)

結果:#38586541

TLE × 19😭

解説写経

どうしようもないので解説を見ます。
ワーシャルフロイド法(wiki)を使えば$O(N^3)$で解けるとのこと。

ここで、「BFSも最悪全頂点の探索だから$O(N)$で$Q$が最大$N^2$だから一緒じゃん!」と思ってしまったのですが、改めてググるとBFSの計算量は$O(|E|)$($E$は辺の数)とのことで、本問で辺の数は最大$N^2$となるので結果$O(N^4)$となります。そりゃTLEなるわ…

さて、ワーシャルフロイド法です。
解説の実装例を見た瞬間は「なんでこれで求まるんだ…???🤔」となったのですが、以下記事を参照してなんとなくDPの雰囲気で呑み込むことができました。なんとなく。

from itertools import product def E(N, A, S, Q, UV): A = [0] + A d = [[N] * (N + 1) for _ in range(N + 1)] for i in range(N): d[i][i] = 0 val = [[0] * (N + 1) for _ in range(N + 1)] for i, s in enumerate(S, 1): for j, k in enumerate(s, 1): if k == "Y": d[i][j] = 1 val[i][j] = A[j] for j, i, k in product(range(1,N + 1), repeat=3): if d[i][j] + d[j][k] < d[i][k]: d[i][k] = d[i][j] + d[j][k] val[i][k] = val[i][j] + val[j][k] elif d[i][j] + d[j][k] == d[i][k] and val[i][j] + val[j][k] > val[i][k]: val[i][k] = val[i][j] + val[j][k] for u, v in UV: if d[u][v] == N: print("Impossible") else: print(d[u][v], val[u][v] + A[u]) test_all(E)

結果:#38589961

やっぱり幅優先探索でもイケんじゃね?

解説の実装例を見て思ったのですが、事前にすべての組み合わせの答えを出しておくんだったら幅優先探索でも$O(N^3)$でイケんじゃね?
という訳で以下。

from collections import deque, defaultdict def E(N, A, S, Q, UV): A = [0] + A edge = defaultdict(list) for i, s in enumerate(S, 1): for j, k in enumerate(s, 1): if k == "Y": edge[i].append(j) ans = {} for i in range(1, N + 1): value = [0] * (N + 1) value[i] = A[i] dist = [N] * (N + 1) dist[i] = 0 q = deque([i]) while q: now = q.popleft() for city in edge[now]: if dist[city] > dist[now] + 1: dist[city] = dist[now] + 1 value[city] = value[now] + A[city] q.append(city) elif dist[city] == dist[now] + 1: value[city] = max(value[city], value[now] + A[city]) ans[i] = *zip(dist, value), for u, v in UV: if ans[u][v][0] == N: print("Impossible") else: print(*ans[u][v]) test_all(E)

結果:#38694774

はい、イケたーー!
しかもワーシャルフロイド法より半分以下の実行時間です。

設問と制約の内容に沿って適切に実装できれば、今持っている武器だけでも戦えるという教訓になりました😇

自由欄

まとめ

振り返ってみると、ACできなかったC問題もE問題も全探索でしたね…
精進します!

自由欄