🎮

2020/09/29に公開

# ABL

## 所感

A,B,Cの3完の581パフォ

segment-treeが重要らしい

## A - Repeat ACL

やるだけ

#!/usr/bin/env python3
def main():
print('ACL' * int(input()))

if __name__ == '__main__':
main()



## B - Integer Preference

#!/usr/bin/env python3
def main():
A, B, C, D = map(int, input().split())

if A <= C <= B or C <= A <= D:
print('Yes')
else:
print('No')

if __name__ == '__main__':
main()



## C - Connect Cities

union-findで(rootの数)-1を出力すればおｋ

ACLだとDSUって名前みたい

#!/usr/bin/env python3
class UnionFind:
"""Union-Find(素集合データ構造)"""
def __init__(self, n: int):
"""
Constructer(Initialize parameter in this class)

Parameters
----------
n : int
Number of node

Yields
-----
root : list
When value is postive, express root of the node.
When it is negative, express this node is root and size of set.
"""

self.root = [-1] * n

def find(self, x: int):
"""
Search root of node x

Parameters
----------
x : int
node x

Returns
-------
x : int
Root of node x
"""

if self.root[x] < 0:
return x
self.root[x] = self.find(self.root[x])
return self.root[x]

def unite(self, x: int, y: int):
"""
Unite two set including node x and node y into one set.

Parameters
----------
x, y : int
Node number

Returns
-------
unite_result : bool
False : Already two node include same set.
True  : United
"""

x = self.find(x)
y = self.find(y)
if x == y:
return False
if self.root[x] > self.root[y]:
x, y = y, x
self.root[x] += self.root[y]
self.root[y] = x
return True

def same(self, x: int, y: int):
"""
Determine if x and y are in same set.

Parameters
----------
x, y : int
Node number

Returns
-------
result : bool
Determining result
"""

return self.find(x) == self.find(y)

def size(self, x: int) -> bool:
"""
Return size of set including node x.

Parameters
----------
x : int
Node number

Returns
-------
Size of set : int
"""

return self.root[self.find(x)] * -1

def main():
N, M = map(int, input().split())

lst = UnionFind(N)
for _ in range(M):
a, b = map(int, input().split())
lst.unite(a - 1, b - 1)

ans = -1
for i in lst.root:
if i < 0:
ans += 1
print(ans)

if __name__ == '__main__':
main()



## D - Flat Subsequence

dpかな~と思ったけど，どんなdpでやれば良いか分からなかった
edpcやるといいらしい
dp[i][j]でi個目までの数で，最後に選んだ値がjの時の部分列の最大長
このままだとdpの項が10^{5 \times 2}個でMLEするので効率化が必要
dpのiは省略してdp[j]とし，chmax(dp[Ai], max(dp[Ai - K:Ai + K + 1]))で更新してけばおｋ

これで全体の計算量はO(N\log N)となる
N_{max}=3 \times 10 ^ 5だからO(10^6)なので何とか間に合いそう？
pypyでac, pythonでtleでした

#!/usr/bin/env python3
class segtree:
"""
segment tree
value store as object type and get update function(merge_func) from outside

Attributes
----------
n : int
Number of elements
initialize_func : func
function for initialization
merge_func : func
function for merge x and y to x(this merge is distruction update)

Methods
-------
update(i, x)
update tree[i] value to x
get(a, b)
get value from [a, b)
include a but not include b, return a merged value
"""
def __init__(self, n, initialize_func, merge_func):
"""
Constructer(Initialize parameter in this class)

Parameters
----------
n : int
Number of elements
initialize_func : func
function for initialization
merge_func : func
function for merge x and y to x(this merge is distruction update)
"""
self.n = n
self.initialize = initialize_func
self.merge = merge_func
n2 = 1  # n2はnより大きい2の冪数
while n2 < n:
n2 <<= 1
self.n2 = n2
self.tree = [initialize_func() for _ in range(n2 << 1)]

def update(self, index, x):
index += self.n2
self.tree[index] = self.merge(self.tree[index], x)
while index > 1:
# (index ^ 1) はiと1の排他的論理和(XOR)
x = self.merge(x, self.tree[index ^ 1])
index >>= 1  # 右ビットシフトで親ノードのインデックスへ移動
self.tree[index] = self.merge(self.tree[index], x)

def get(self, a, b):
result = self.initialize()
q = [(1, 0, self.n2)]
while q:
k, left, right = q.pop()
if a <= left and right <= b:
result = self.merge(result, self.tree[k])
continue
m = (left + right) // 2
k <<= 1
if a < m and left < b:
q.append((k, left, m))
if a < right and left < m:
q.append((k + 1, m, right))
return result

def main():
N, K = map(int, input().split())
A = [int(input()) for _ in range(N)]
max_A = 3 * 10 ** 5 + 1

seg = segtree(max_A, lambda: 0, max)
for a in A:
next = seg.get(max(0, a - K), min(a + K + 1, max_A))
seg.update(a, next + 1)
print(seg.get(0, max_A))

if __name__ == '__main__':
main()