ABC281の振り返り(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 - Count Down

略

結果：#37136449

自由欄

B - Sandwich Number

問題略

正規表現使うほどでもないかと思い、普通に条件分岐したら見落として1WA…
以下、振り返って正規表現で提出してみる。

import re def B(S): print("Yes" if re.match(r'^[A-Z][1-9]\d{5}[A-Z]$', S) else "No") B("Q142857Z") # Yes B("AB912278C") # No B('X900000') # No B('K012345K') # No

結果：#37282859

自由欄

C - Circular Playlist

略

結果：#37156434

自由欄

D - Max Multiple

やってみよう！

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

test_dataD = [ { "in":[4, 2, 2, [1, 2, 3, 4]], "out": 6 },{ "in":[3, 1, 2, [1, 3, 5]], "out": -1 }, ] def D(N, K, D, a): pass test_all(D)

自由欄

try

コンテストの終了1分後にACしました😇
自力ACできた嬉しさと、あと1分の悔しさと…

考え方としては3次元のDP配列を使うABC262のD問題とかなり近いです。
詳細は解説参照。

ちなみに、解説の実装例は配るDP、以下は貰うDPです(か？よく分かってない…)
そこらへんちゃんと勉強せなあかんな、とDP問題に出くわすたびに思ってる。

def D(N, K, D, a): dp = [[[-1] * D for _ in range(K + 1)] for _ in range(N + 1)] for i in range(N + 1): dp[i][0][0] = 0 # print(np.array(dp)) for i in range(1, N + 1): for j in range(1, min(i + 1, K + 1)): for k in range(D): dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]) x = dp[i - 1][j - 1][k] if x != -1: y = x + a[i - 1] dp[i][j][y % D] = max(y, dp[i - 1][j][y % D]) # print(np.array(dp)) return dp[-1][-1][0] test_all(D)

結果：#37184061

自由欄

E - Least Elements

やってみよう！

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

test_dataE = [ { "in": [6, 4, 3, [3, 1, 4, 1, 5, 9]], "out": "5 6 10" },{ "in": [10, 6, 3, [12, 2, 17, 11, 19, 8, 4, 3, 6, 20]], "out": "21 14 15 13 13" } ] def E(N, M, K, A): pass test_all(E)

自由欄

try

せっかくなのでE問題もやってみますが、例によってサッパリなので解説を見ます。

🤔❓

いや、まぁ考え方は分からなくもないですが、それをどう実装すんのかも分からない訳で…
KoDさんのACコード見るとなんか謎にBIT(フェニック木)使ってるし…

で、下記けんちょんさんの解説でようやく(何となく)理解できました。

AtCoder ABC 281 E - Least Elements (水色, 500 点) - けんちょんの競プロ精進記録

Aを昇順に並べ替えておいて、そのIndexを使ってBITで管理するわけですね。
ちなみにBITはABC264のDで転倒数を求めるときに出会って、最近ではABC276のCで「順列が辞書順で何番目か」を計算するのに使いました。

今回はそのBITに二分探索のメソッド(get)を追加しました。(下記参照)

Binary Indexed Tree (BIT) 総まとめ！区間加算や二次元BITまで \| アルゴリズムロジック

BITの実装

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 operator import itemgetter as ig def E(N, M, K, A): # data -> [[sorted index, A index, value]] data = sorted(([si, i, a] for si, (i, a) in enumerate(sorted(enumerate(A), key=ig(1)))), key=ig(1)) idx = BIT(N) val = BIT(N) ans = [] for d in data[:M]: idx[d[0]] = 1 val[d[0]] = d[2] ans.append(val.sum(idx.get(K))) for i, d in enumerate(data[M:]): idx[d[0]] = 1 val[d[0]] = d[2] idx[data[i][0]] = 0 val[data[i][0]] = 0 ans.append(val.sum(idx.get(K))) return " ".join(map(str, ans)) test_all(E)

結果：#37372852

自由欄