目次

SoundHound 2018 本戦

SoundHound Programming Contest 2018 Masters Tournament 本戦

初のオンサイトでした。貴重な体験。開催いただいたSoundHound様に感謝。

A - Feel the Beat

A - Feel the Beat

問題

解法

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)

B - Neutralize

B - Neutralize

問題

K=3

-1 -2 -3  4  5 -6 -7 -8 -9
↓
 0  0  0  4  5  0  0  0  0

解法

DPで解ける。

ただし、一度操作を ii(i+K1)(i+K1) に適用したら、次に範囲を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]))

D - Propagating Edges

D - Propagating Edges

問題

解法

Complete(u)の時に行う操作は、愚直にやれば

なのだが、後半になってくるとまず探索の時点でキューに最大 N1 個のタスクが積まれるので、それが空になるまでの処理が1万回とか来ると探索だけでTLEとなる。

ここで、Checkは「直接結ぶ辺があるか」さえわかればよく、とあるCompleteクエリの時点で u から繋がってるグループ内の頂点同士はそれ以降のCheckではみんなYesである。

よって、UnionFind木を使い、Completeされた頂点はグループとして縮約してしまえば、探索する頂点・辺を減らすことができる。

グラフの状態を、3つの構造で管理する。

Add(u,v)

既にu,vが contracted 上で同じグループ内なら、何もしない

違うグループなら、

Complete(u)

uの属するグループの代表から、connected の辺を辿り、DFSなどで探索を行う。

たどり着いた頂点の属するグループを、contracted 上でuの属するグループに併合(縮約)していく。

最後に、今回縮約したグループの最終的な代表の connected の辺を全て削除する。(ここに残ってるのは、全て今回Completeして縮約済みの頂点。もう探索の必要は無い。が、残していると次のCompleteクエリで再探索してしまい、計算量の削減にならない)

Check(u,v)

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