ABC285の振り返り(A, B, C, D, E, F)

振り返りです。

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 - Edge Checker 2

やってみよう！

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

def A(a, b): pass A(1, 2) # Yes A(2, 8) # No A(14, 15) # No

自由欄

try

プラス・マイナスを間違えてWAになった戒めとして記録しておきます…

def A(a, b): if a > b: a, b = b, a if a * 2 == b or a * 2 == b - 1: print("Yes") else: print("No") A(1, 2) # Yes A(2, 8) # No A(14, 15) # No

結果：#38044890

振り返り

色々無駄が多いのでやり直したのが以下。

めっちゃ短く書けるやん。コンテスト中、全然頭回ってなかったな…

def A(a, b): print("Yes" if b // 2 == a else "No") A(1, 2) # Yes A(2, 8) # No A(14, 15) # No

結果：#38188781

自由欄

B - Longest Uncommon Prefix

問題略

やってみよう！

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

def B(N, S): pass B(6, "abcbac") # 5 # 1 # 2 # 0 # 1

自由欄

try

題意を正確に読み取る類の問題。
実装は色々で短くできる余地は多分にありそうですが、こういう問題ではできるだけ忠実に設問に沿ったコーディングをしたほうがリーダブルでバグを防げると思います。

以下コンテスト中の提出。

def B(N, S): S = "0" + S for i in range(1, N): for k in range(1, N - i + 1): if S[k] == S[k + i]: break else: print(k) continue print(k - 1) B(6, "abcbac") # 5 # 1 # 2 # 0 # 1

結果：#38050823

自由欄

C - abc285_brutmhyhiizp

問題略

やってみよう！

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

def C(S): pass C("AB") # 28 C("C") # 3 C("BRUTMHYHIIZP") # 10000000000000000

自由欄

try

26進数→10進数の変換。
コンテスト中の提出が以下。

from string import ascii_uppercase def C(S): ans = 0 for i, c in enumerate(S[::-1]): ans += len(ascii_uppercase) ** i * (ascii_uppercase.index(c) + 1) print(ans) C("AB") # 28 C("C") # 3 C("BRUTMHYHIIZP") # 10000000000000000

結果：#38054498

振り返り

ほとんど同じですが、処理としてはちょっとシンプルになった(、か…？)

def C(S): n = lambda c: ord(c) - ord("A") + 1 CARDINAL = n("Z") ans = 0 for c in S: ans *= CARDINAL ans += n(c) print(ans) C("AB") # 28 C("C") # 3 C("BRUTMHYHIIZP") # 10000000000000000

結果：#38249291

でも改めて考えると、10進数の10は見た通り二桁になるのに対して、設問のIDは26進数で26番目がZと一桁で表せる最大の数になるのがなんか不思議。
0が無いとこうなるのか。

自由欄

D - Change Usernames

やってみよう！

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

test_dataD = [ { "in":[2, [['b', 'm'], ['m', 'd']]], "out": "Yes" },{ "in":[3, [['a', 'b'], ['b', 'c'], ['c', 'a']]], "out": "No" },{ "in":[5, [['aaa', 'bbb'], ['yyy', 'zzz'], ['ccc', 'ddd'], ['xxx', 'yyy'], ['bbb', 'ccc']]], "out": "Yes" }, ] def D(N, ST): pass test_all(D)

自由欄

try

グラフの閉路(サイクル)判定問題。だいぶ苦戦しました…
コンテスト中はどうにかBFSで一発ACできましたが、かなり無駄が多い実装だったのでやり直したのが以下。

from collections import deque def D(N, ST): edge = {} for s, t in ST: edge[s] = t while edge: a, b = edge.popitem() passed = set([a, b]) q = deque([b]) while q: now = q.popleft() if now not in edge: continue nxt = edge.pop(now) if nxt in passed: return "No" else: q.append(nxt) passed.add(nxt) return "Yes" test_all(D)

結果：#38282949

コード量も実行時間も短縮できました。

DSUで解く

解説によるとDSU(Union-Find)でも解けるとのこと。
ABC284のDSUクラスを使いまわしたいところですが、これは頂点として整数が与えられる想定で実装されています。なので前処理としてユーザー名に一意の整数を割り振ることにしました。

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]) from itertools import chain def D(N, ST): mapper = {name: i for i, name in enumerate(set(chain.from_iterable(ST)))} dsu = DSU() for s, t in ST: if dsu.leader(mapper[s]) == dsu.leader(mapper[t]): return "No" dsu.merge(mapper[s], mapper[t]) return "Yes" test_all(D)

結果：#38284930

メイン処理部分がすげぇ短くなった。
ググった範囲だと、DSU(Union-Find)クラスを文字列対応にするか、上記同様ユーザー名にID(整数)を振るかで対応が分かれる感じ。

自由欄

E - Work or Rest

やってみよう！

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

test_dataE = [ { "in":[7, [10, 10, 1, 1, 1, 1, 1]], "out": 50 },{ "in":[10, [200000000, 500000000, 1000000000, 800000000, 100000000, 80000000, 600000, 900000000, 1, 20]], "out": 5100000000 },{ "in":[20, [38, 7719, 21238, 2437, 8855, 11797, 8365, 32285, 10450, 30612, 5853, 28100, 1142, 281, 20537, 15921, 8945, 26285, 2997, 14680]], "out": 236980 }, ] def E(N, A): pass test_all(E)

自由欄

try

コンテスト中は全く糸口が掴めず時間切れとなりました。
解説を読んでもよく分からないので、とりあえずPythonで書き直したのが以下。

from itertools import accumulate def E(N, A): A = [0] + A *B, = accumulate(A[(i + 1) // 2] for i in range(N + 1)) dp = [[-1] * (N + 1) for _ in range(N + 1)] dp[1][0] = 0 for i in range(1, N): for j in range(N + 1): if dp[i][j] < 0: continue dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]) dp[i + 1][0] = max(dp[i + 1][0], dp[i][j] + B[j]) res = 0 for i in range(N): res = max(res, dp[N][i] + B[i]) return res test_all(E)

結果はACとなりましたが、これ13行目のdp[i + 1][j + 1]への代入なんて1回しか実行しないんだからmaxとる必要なくない？
ていうか値を新たに計算しているのは14行目のdp[i + 1][0]だけで、あとは右下にコピーしてるだけじゃん。

という訳で短くしてみたのが以下。

from itertools import accumulate def E(N, A): A = [0] + A *B, = accumulate(A[(i + 1) // 2] for i in range(N + 1)) dp = [0] for i in range(1, N + 1): dp = [max(d + b for d, b in zip(dp, B))] + dp return dp[0] test_all(E)

結果：#38320849

めっちゃ短くなって無事ACとなりました。

自由欄

解説を理解する

短くはできても、どんな意図でコーディングされたのかが理解できていません。
とりあえずループを回すたびにdpを出力してみます。

from itertools import accumulate def E_debug(N, A, debug=False): A = [0] + A *B, = accumulate(A[(i + 1) // 2] for i in range(N + 1)) print(f"{B=}") dp = [0] for i in range(1, N + 1): dp = [max(d + b for d, b in zip(dp, B))] + dp print(i, dp) return dp[0] E_debug(*test_dataE[0]["in"])

前述の通り、新たに計算されるのは配列の先頭要素のみです。

で、結局このdpが持っている数字は何かというと、一週間が[i日, i-1日, ..., 1日, 0日]の場合の生産量の最大値となっています。(一週間の一日目は休み)
なぜそうなるのかを考えるために、i == 7のときの計算を確認してみます。

1週間が6日の生産量の最大値 + 1休 　　 = 41 + 0 = 41
 　〃　5日　　　〃　　　　 + 1休1連勤 = 40 + 10 = 50
 　〃　4日　　　〃　　　　 + 1休2連勤 = 30 + 20 = 50
 　〃　3日　　　〃　　　　 + 1休3連勤 = 20 + 30 = 50
 　〃　2日　　　〃　　　　 + 1休4連勤 = 10 + 40 = 50
 　〃　1日　　　〃　　　　 + 1休5連勤 = 0 + 41 = 41
 　〃　0日　　　〃　　　　 + 1休6連勤 = 0 + 42 = 42

という訳で、結局1週間が7日の場合の生産量は最大50ということになるわけですね。

最初にB配列を作り、それを上のような計算で使えるという発想を、とても思いつくことができませんでした…
理解できた今でも、化かされたような気分。DPムズい。

自由欄

F - Substring of Sorted String

やってみよう！

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

test_dataF = [ { "in":[6, "abcdcf", 4, ["2 1 3", "2 2 6", "1 5 e", "2 2 6"]], "out": "Yes\nNo\nYes" } ] def F(N, S, Q, queries): pass test_all(F)

自由欄

try

せっかくなのでF問題もやってみます。
とは言え全くどうすればいいか分からないので解説を見ます。

問題の難易度が上がってくると『考察力』というか『条件を言い換える能力』がより重要になってきますね…😩
本問では部分文字列を判定する上で実際に$T$($S$を昇順に並び替えた文字列)を作る必要はなく、$S[L:R]$(コード上はS[L:R+1])が昇順であること(条件①)ともう一つの条件(条件②)を満たせば「部分文字列である」と判定できることが解説で示されています。

ではそれぞれの条件をどのように判定するかですが、上の解説を参考に(セグ木ではなくBITで)実装したところTLEとなったので、条件①を別の解説(こちらやこちら)を参考に(セグ木ではなくBITで)実装し直したところ、やっとのことでACとなりました。

それが以下。

class BIT: def __init__(self, a): if hasattr(a, "__iter__"): self.size = len(a) self.data = [0] * self.size self.bit = [0] * (self.size + 1) for i, j in enumerate(a): self.add(i, j) elif isinstance(a, int): self.size = a self.data = [0] * a self.bit = [0] * (a + 1) else: raise TypeError() def add(self, i, x): self.data[i] += x i += 1 while i <= self.size: self.bit[i] +="x" i & -i def sum(self, i): '''get sum of data[:i] ''' total="0" while> 0: total += self.bit[i] i -= i & -i return total def get(self, x): res = 0 i = 1 while i < (self.size + 1) / 2: i <<= 1 while i> 0: if res + i < self.size and self.bit[res + i] < x: x -= self.bit[res + i] res += i i >>= 1 res += 1 return res if res >= x else -1 def __getitem__(self, key): return self.data[key] def __setitem__(self, key, value): self.add(key, value - self[key]) self.data[key] = value def __len__(self): return self.size def __repr__(self): return self.data.__repr__() def __iter__(self): return self.data.__iter__() from collections import defaultdict from string import ascii_lowercase def next_c(c): return chr(ord(c) + 1) def F(N, S, Q, queries): S = list(S) # S内に各文字が何個あるかを保持 num = defaultdict(int) # S[i]時点で各文字のS[0]からの合計をBITで管理 abc = defaultdict(lambda: BIT(N)) # Sの任意区間が昇順かを判断するための情報を管理 ## S[i-1]とS[i]が昇順であればS[i]=0、そうでなければS[i]=1 ## is_sorted.sum(l + 1) == is_sorted.sum(r + 1) ならS[l:r+1]は昇順 is_sorted = BIT(N) # 前処理 for i, c in enumerate(S): num[c] += 1 abc[c][i] = 1 if i > 0 and S[i - 1] > c: is_sorted[i] = 1 for q in queries: type, *args = q.split() if type == "1": x = int(args[0]) - 1 c = args[1] # 置き換えられる文字の処理 num[S[x]] -= 1 abc[S[x]][x] = 0 # 置き換える文字の処理 S[x] = c abc[c][x] = 1 num[c] += 1 if x > 0: is_sorted[x] = 0 if S[x - 1] <= 1 c else if x < n - 1: is_sorted[x + 1]="0" s[x>= c else 1 else: l, r = map(lambda x: int(x) - 1, args) # 前処理 c_max = "a" c_min = "z" num_lr = defaultdict(int) for c in ascii_lowercase: num_lr[c] = abc[c].sum(r + 1) - abc[c].sum(l) if num_lr[c] > 0: c_max = max(c_max, c) c_min = min(c_min, c) # 昇順？ if is_sorted.sum(r + 1) == is_sorted.sum(l + 1): # 部分文字列？ c = next_c(c_min) while c < c_max: if num_lr[c] != num[c]: break c = chr(ord(c) + 1) else: print("Yes") continue print("No") test_all(F)

結果：#38445485

昇順の判定をBITで実現できる、というテクニックを知れたのは有益でした。
こういう小技を地道に積み重ねて、条件の言い換えなど『考察力』を高めていこうと思います！