SoundHound Programming Contest 2018 Masters Tournament 本戦
初のオンサイトでした。貴重な体験。開催いただいたSoundHound様に感謝。
$10^{15}$ 個もの数を1つ1つ割って確かめてたら間に合わないが、区間の方を倍倍して重なった部分を足し合わせていけばよい。
140 170 ... 280 340 ... 560 680 ... ~~~~~~~ ~~~~~~~ ~~~~~~~ ←140以上170未満にできる数 C D |---------------------------------| 160 650 |-| |-----| |--| 10 60 90
c, d = map(int, input().split()) a=140 b=170 ans=0 while a<d: if b<c: a<<=1 b<<=1 continue ans+= min(b,d)-max(a,c) a<<=1 b<<=1 print(ans)
K=3 -1 -2 -3 4 5 -6 -7 -8 -9 ↓ 0 0 0 4 5 0 0 0 0
DPで解ける。
ただし、一度操作を $i$~$(i+K-1)$ に適用したら、次に範囲を1つずらして操作を行うことで $i+K$ も単独(っぽく)0にできるため、直前の薬品に対して操作をしたかどうかで分ける必要がある。
すると、遷移は、それぞれ以下の候補の最大値となる。左端から $K$ 個未満の薬品だけを0にすることはできないため、$i \lt K$ の時は少し異なることに注意する。
import sys n, k = list(map(int, input().split())) bbb = list(map(int, sys.stdin.readlines())) dp1 = [0] * (n + 1) dp2 = [0] * (n + 1) for i, b in enumerate(bbb): if i < k: dp2[i + 1] = dp2[i] + b else: dp1[i + 1] = max(dp1[i], dp2[i - k + 1]) dp2[i + 1] = max(dp1[i], dp2[i]) + b print(max(dp1[-1], dp2[-1]))
Complete(u)の時に行う操作は、愚直にやれば
なのだが、後半になってくるとまず探索の時点でキューに最大 $N-1$ 個のタスクが積まれるので、それが空になるまでの処理が1万回とか来ると探索だけでTLEとなる。
ここで、Checkは「直接結ぶ辺があるか」さえわかればよく、とあるCompleteクエリの時点で $u$ から繋がってるグループ内の頂点同士はそれ以降のCheckではみんなYesである。
よって、UnionFind木を使い、Completeされた頂点はグループとして縮約してしまえば、探索する頂点・辺を減らすことができる。
グラフの状態を、3つの構造で管理する。
既にu,vが contracted 上で同じグループ内なら、何もしない
違うグループなら、
uの属するグループの代表から、connected の辺を辿り、DFSなどで探索を行う。
たどり着いた頂点の属するグループを、contracted 上でuの属するグループに併合(縮約)していく。
最後に、今回縮約したグループの最終的な代表の connected の辺を全て削除する。(ここに残ってるのは、全て今回Completeして縮約済みの頂点。もう探索の必要は無い。が、残していると次のCompleteクエリで再探索してしまい、計算量の削減にならない)
uとvが contracted 上で同じグループか、もしくは direct 上で直接繋がってるか、いずれかならYes。
import sys class UnionFind: def __init__(self, n): self.table = [-1] * n def root(self, x): if self.table[x] < 0: return x else: self.table[x] = self.root(self.table[x]) return self.table[x] def find(self, x, y): return self.root(x) == self.root(y) def union(self, x, y): r1 = self.root(x) r2 = self.root(y) if r1 == r2: return r1 d1 = self.table[r1] d2 = self.table[r2] if d1 <= d2: self.table[r2] = r1 if d1 == d2: self.table[r1] -= 1 return r1 else: self.table[r1] = r2 return r2 def dfs(s): cs = contracted.root(s) checked = {cs} q = list(connected[cs]) while q: v = q.pop() if v in checked: continue checked.add(v) cs = contracted.union(cs, v) q.extend(u for u in connected[v] if u not in checked) connected[cs].clear() n, q = list(map(int, input().split())) direct = [set() for _ in range(n + 1)] connected = [set() for _ in range(n + 1)] contracted = UnionFind(n + 1) for line in sys.stdin.readlines(): t, u, v = map(int, line.split()) if t == 1: cu = contracted.root(u) cv = contracted.root(v) if cu == cv: continue connected[cu].add(cv) connected[cv].add(cu) direct[u].add(v) direct[v].add(u) if t == 2: dfs(u) if t == 3: print('Yes' if contracted.find(u, v) or v in direct[u] else 'No')