SoundHound 2018 本戦
SoundHound Programming Contest 2018 Masters Tournament 本戦
初のオンサイトでした。貴重な体験。開催いただいたSoundHound様に感謝。
A - Feel the Beat
問題
- 2つの正整数で指定される区間の整数 $[C,D)=C,C+1,...,D-1$ の内、何回か2で割って(0回も可)「140以上170未満」にできる数はいくつあるか
- $140 \le C \lt D \le 10^{15}$
解法
$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)
B - Neutralize
問題
- $N$ 個の薬品が一列に並ぶ
- 薬品には効用 $u_i$ が決まっている（負もある）
- 連続して並んだ $K$ 個の薬品の効用をまとめて0にする操作を好きなだけできる
- 操作後、薬品の効用の和を最大化せよ
例
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にできるため、直前の薬品に対して操作をしたかどうかで分ける必要がある。
- $dp1[i]=$ 薬品 $i$ まででの、$i$ の効用を0にした上での最大値
- $dp2[i]=$ 薬品 $i$ まででの、$i$ の効用を0にしなかった上での最大値
すると、遷移は、それぞれ以下の候補の最大値となる。左端から $K$ 個未満の薬品だけを0にすることはできないため、$i \lt K$ の時は少し異なることに注意する。
- $dp1[i+1]$（※ $i \ge K$）
- $dp1[i]:$ 直前のDPで $(i-k+1)$～$i$ まで0にした区間を1つずらして再度操作を行う
- $dp2[i-k+1]:$ $(i-k+2)$～$(i+1)$ の区間に対して操作を行う
- $dp2[i+1]$
- $dp1[i]+b_{i+1}:$ そのまま $i+1$ 番目の薬品を用いる（但し $i \ge K$）
- $dp2[i]+b_{i+1}:$ そのまま $i+1$ 番目の薬品を用いる
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]))
D - Propagating Edges
問題
- まず、$N$ 頂点0辺のグラフがある
- 次の3種類のクエリ $Q$ 個を与えられた順番に処理する
- 1:Add(u, v)
- 頂点 $u,v$ の間に辺を追加する
- 2:Complete(u)
- 頂点 $u$ の連結成分（$u$ から辺を通じて到達できる範囲）を完全グラフにする（全ての2頂点間に辺を追加する）
- 3:Check(u, v)
- 頂点 $u,v$ を直接結ぶ辺があるかを出力する
解法
Complete(u)の時に行う操作は、愚直にやれば
- $u$ からDFSなどで探索（キューが空になるまで）
- 到達できた頂点間に辺を追加
なのだが、後半になってくるとまず探索の時点でキューに最大 $N-1$ 個のタスクが積まれるので、それが空になるまでの処理が1万回とか来ると探索だけでTLEとなる。
ここで、Checkは「直接結ぶ辺があるか」さえわかればよく、とあるCompleteクエリの時点で $u$ から繋がってるグループ内の頂点同士はそれ以降のCheckではみんなYesである。
よって、UnionFind木を使い、Completeされた頂点はグループとして縮約してしまえば、探索する頂点・辺を減らすことができる。
グラフの状態を、3つの構造で管理する。
- direct: 直接繋がってる辺
- connected: 直接とは限らないけど繋がってる辺（探索に必要な分のみ）
- contracted: 縮約済みのグループを管理するUnionFind木
Add(u,v)
既にu,vが contracted 上で同じグループ内なら、何もしない
違うグループなら、
- グループの代表同士の間に connected の辺を張る
- u,vの間に direct の辺を張る
Complete(u)
uの属するグループの代表から、connected の辺を辿り、DFSなどで探索を行う。
たどり着いた頂点の属するグループを、contracted 上でuの属するグループに併合(縮約)していく。
最後に、今回縮約したグループの最終的な代表の connected の辺を全て削除する。（ここに残ってるのは、全て今回Completeして縮約済みの頂点。もう探索の必要は無い。が、残していると次のCompleteクエリで再探索してしまい、計算量の削減にならない）
Check(u,v)
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')
