SoundHound Programming Contest 2018 Masters Tournament 本戦
初のオンサイトでした。貴重な体験。開催いただいたSoundHound様に感謝。
10151015 個もの数を1つ1つ割って確かめてたら間に合わないが、区間の方を倍倍して重なった部分を足し合わせていけばよい。
140 170 ... 280 340 ... 560 680 ... ~~~~~~~ ~~~~~~~ ~~~~~~~ ←140以上170未満にできる数 C D |---------------------------------| 160 650 |-| |-----| |--| 10 60 90
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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で解ける。
ただし、一度操作を ii~(i+K−1)(i+K−1) に適用したら、次に範囲を1つずらして操作を行うことで i+Ki+K も単独(っぽく)0にできるため、直前の薬品に対して操作をしたかどうかで分ける必要がある。
すると、遷移は、それぞれ以下の候補の最大値となる。左端から KK 個未満の薬品だけを0にすることはできないため、i<Ki<K の時は少し異なることに注意する。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
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。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
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' ) |