ABC283の振り返り(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 - Power

略

自由欄

B - First Query Problem

略

自由欄

C - Cash Register

やってみよう！

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

def C(S): pass C("40004") # 4 C("1355506027") # 10 C("10888869450418352160768000001") # 27

自由欄

try

整数で愚直にループを回してもよくある$10^5$だしいけんじゃね、と思ったらTLEとなりました…
めっちゃでかい値($10^{100000}$)の演算に掛かる時間を考慮してなかった😇

という訳で、正規表現でAC。

import re def C(S): print(len(S) - len(re.findall("00", S))) C("40004") # 4 C("1355506027") # 10 C("10888869450418352160768000001") # 27

結果：#37498694

Pythonだと精度の制限がないので鈍感になりがち(というのは言い訳)ですが、計算量だけではなくそこら辺も気に掛けないといけませんね。

自由欄

D - Scope

やってみよう！

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

def D(S): pass D("((a)ba)") # Yes D("(a(ba))") # No D("(((())))") # Yes D("abca") # No

自由欄

try

コンテスト中にACの提出はAfter contestのテストケースがWAとなるので、若干修正したのが以下。

前処理としてS内でのa~zの場所を取っておいて、累積和で括弧の範囲を管理して、その範囲内でa~zがあるかどうかをニブタンで判定しています。
なんか、すげぇ頑張ってる…

一応コンテスト中はACだったし、バグってた箇所もすぐ分かりはしたのですが、もうちょっとスマートな解法はないものか🤔

from itertools import accumulate from collections import defaultdict from bisect import bisect def D(S): *acc, = accumulate(1 if s == "(" else -1 if s == ")" else 0 for s in S) loc = defaultdict(list) for i, s in enumerate(S): loc[s].append(i) char = set() step = {} for i, s in enumerate(S): if s == ")": char.add(s) # char -= set(S[step[acc[i] + 1]:i + 1]) l = step[acc[i] + 1] r = i rm = set() for c, cloc in loc.items(): cl = bisect(cloc, l) cr = bisect(cloc, r) if cr > cl: rm.add(c) char -= rm elif s == "(": char.add(s) step[acc[i]] = i else: if s in char: print("No") break char.add(s) else: print("Yes") D("((a)ba)") # Yes D("(a(ba))") # No D("(((())))") # Yes D("abca") # No

結果：#37694017

自由欄

解説を見る

という訳で解説を見たらめっちゃスマートでした。
ちょっと論理は難解ですが、具体例で考えれば、まぁ、まぁ、まぁ。なるほどという感じ。

前回のD問題しかり、設問を数学的に読みかえる能力みたいなのが欠けている気がする…

from collections import defaultdict def D(S): used = defaultdict(int) v = defaultdict(set) now = 0 for s in S: if s == "(": now += 1 elif s == ")": for c in v[now]: used[c] = False v[now] = set() now -= 1 else: if used[s]: print("No") return v[now].add(s) used[s] = True print("Yes") D("((a)ba)") # Yes D("(a(ba))") # No D("(((())))") # Yes D("abca") # No

結果：#37693769

自由欄