ABC306の振り返り(B, C, D, E)

振り返りです。

import sys from io import StringIO input = lambda: sys.stdin.readline()[:-1] def test(f, data, detail=True): stdin = sys.stdin stdout = sys.stdout sys.stdin = StringIO(data["in"]) out = StringIO() sys.stdout = out err = None try: f() except BaseException as e: err = e else: ans = out.getvalue() exp = data["out"] sys.stdin = stdin sys.stdout = stdout if err: raise err result = "AC" if exp == ans else "WA" print(f"{result}: expected: {exp if detail else ''}, output: {ans if detail else ''}") def test_all(f): for i, data in enumerate(eval(f'test_data{f.__name__[0]}'), 1): print(f"case {i}") test(f, data)

B - Base 2

やってみよう！

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

test_dataB = [ { "in":"""1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 """, "out": """13 """ },{ "in":"""1 0 1 0 1 0 0 0 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 """, "out": """766067858140017173 """ }, ] def B(): pass test_all(B)

自由欄

コンテスト中

2進数から10進数変換。
コンテスト中は素朴にこんな感じ

def B(): (*A,) = map(int, input().split()) ans = 0 base2 = 1 for a in A: ans += a * base2 base2 *= 2 print(ans) test_all(B)

結果：#42323982

自由欄

振り返り

int()で一発でしたね。。

def B(): print(int(input().replace(" ", "")[::-1], base=2)) test_all(B)

結果：#43665287

自由欄

他の人の提出を見る

わざわざスペースをreplaceする必要もないのか…！

def B(): print(int(input()[::-2], base=2)) test_all(B)

C - Centers

やってみよう！

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

test_dataC = [ { "in":"""3 1 1 3 2 3 2 2 3 1 """, "out": """1 3 2 """ },{ "in":"""1 1 1 1 """, "out": """1 """ },{ "in":"""4 2 3 4 3 4 1 3 1 1 4 2 2 """, "out": """3 4 1 2 """ }, ] def C(): pass test_all(C)

自由欄

コンテスト中

こんな感じ。
num_idxにインデックスをappendするのは走査順なので、最終的に1~Nのインデックス配列の2つ目の要素が真ん中のインデックスということですね。

def C(): from collections import defaultdict N = int(input()) (*A,) = map(int, input().split()) num_idx = defaultdict(list) for i, a in enumerate(A): num_idx[a].append(i) _, ans = zip(*sorted([[idx[1], n] for n, idx in num_idx.items()])) print(*ans) test_all(C)

結果：#42335811

自由欄

D - Poisonous Full-Course

やってみよう！

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

test_dataD = [ { "in":"""5 1 100 1 300 0 -200 1 500 1 300 """, "out": """600 """ },{ "in":"""4 0 -1 1 -2 0 -3 1 -4 """, "out": """0 """ },{ "in":"""15 1 900000000 0 600000000 1 -300000000 0 -700000000 1 200000000 1 300000000 0 -600000000 1 -900000000 1 600000000 1 -100000000 1 -400000000 0 900000000 0 200000000 1 -500000000 1 900000000 """, "out": """4100000000 """ }, ] def D(): pass test_all(D)

自由欄

コンテスト中

こんな感じ。
単純なDPです。

def D(): N = int(input()) XY = [list(map(int, input().split())) for _ in range(N)] # dp[j]: 状態別(j=0: 健康、j=1: 腹壊し)最大値 dp = [0, 0] for x, y in XY: if x == 0: dp[0] = max(dp[0], dp[0] + y, dp[1] + y) else: dp[1] = max(dp[1], dp[0] + y) print(max(dp)) test_all(D)

結果：#42347396

自由欄

E - Best Performances

やってみよう！

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

test_dataE = [ { "in":"""4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0 """, "out": """5 6 8 8 15 13 13 11 1 0 """ },{#test_01 "in":"""1 1 1 1 900924422 """, "out": """900924422 """ }, ] def E(): pass test_all(E)

自由欄

振り返り

ついでのE問題。
とりあえず愚直に二分探索でソート済み配列を更新するような実装にしてみたら、案の定というかTLEとなりました...(これとかこれとかこれ)
→多分削除は高速でも追加でダメなんだろうなぁ😩

という訳で解説で使われているmultisetのPython代替を調べます。
下記サイトのアイディアを参考にheapq + dictで削除機能付きのheapqラッパー(my_heapq)を作って無事ACとなりました。(存在確認機能の実装は割愛。代わりに降順で値を持てるようにしたよ。)

Pythonでmultisetの代用ができるデータ構造 - Tsuboの競プロブログ

なお代替案としてBITを使う方法もあるようですが、今回は値の範囲が$0 \le Y_i \le 10^9$で先読みもできないので不可となります。

from heapq import * from collections import defaultdict class my_heapq: def __init__(self, a, reverse=False): self.reverse = reverse if reverse: a = [-v for v in a] self.a = a heapify(self.a) self.rm_list = defaultdict(int) def heappush(self, item): if self.reverse: item *= -1 heappush(self.a, item) def heappop(self): x = heappop(self.a) while self.rm_list[x]: self.rm_list[x] -= 1 x = heappop(self.a) if self.reverse: x *= -1 return x def heappushpop(self, item): if self.reverse: return -heappushpop(self.a, -item) else: return heappushpop(self.a, item) def rm(self, item): if self.reverse: item *= -1 self.rm_list[item] += 1 def get_first(self): while self.rm_list[self.a[0]]: self.rm_list[self.a[0]] -= 1 heappop(self.a) if self.reverse: return -self.a[0] else: return self.a[0] def E(): N, K, Q = map(int, input().split()) A = [0] * (N + 1) top_k = my_heapq([0] * K) # 通常heap: 先頭が最小 others = my_heapq([0] * (N - K), reverse=True) # 降順heap: 先頭が最大 ans = 0 if N == K: for _ in range(Q): x, y = map(int, input().split()) now = A[x] ans -= now ans += y A[x] = y print(ans) return for _ in range(Q): x, y = map(int, input().split()) now = A[x] A[x] = y if now >= top_k.get_first(): top_k.rm(now) if y >= others.get_first(): # top_kにいて、残る ans -= now ans += y top_k.heappush(y) else: # top_kにいて、外れる ans -= now new = others.heappop() ans += new top_k.heappush(new) others.heappush(y) else: others.rm(now) if y > top_k.get_first(): # top_kにおらず、入る old = top_k.heappop() ans -= old others.heappush(old) ans += y top_k.heappush(y) else: # top_kにおらず、入らない others.heappush(y) print(ans) test_all(E)

結果：#43688460

自由欄