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')

            

        
      