AtCoder Beginner Contest 177 振り返り
D - Friends
・友達の友達は友達
・友達同士がいないように分ける場合，最低何グループ必要か
解）
最大の友達集合の大きさを求めればよい．
Union Find 木構造が役に立つ．
実装：
parent[] は大きさN，-1を初期値とし，parent[i]には i の根を格納．
iが根の場合はグループの要素の数を負で格納．
根を見つけ，道中にある数字の根も書き換える関数．
負の数（グループの構成要素数）
def find(parent, i):
t = parent[i]
if t < 0:
return i
t = find(parent, t)
parent[i] = t
return t
根をつなぎなおす関数
def unite(parent, i, j):
i = find(parent, i)
j = find(parent, j)
if i == j:
return
parent[j] += parent[i]
parent[i] = j
例：
入力を
7 5
1 7
2 6
3 5
4 5
4 6
とすると，
#i について
f:0
[-1, -1, -1, -1, -1, -1, -1]
i:0
#j について
f:6
[-1, -1, -1, -1, -1, -1, -1]
j:6
#unite内のparent書き換え
[6, -1, -1, -1, -1, -1, -2]
f:1
[6, -1, -1, -1, -1, -1, -2]
i:1
f:5
[6, -1, -1, -1, -1, -1, -2]
j:5
[6, 5, -1, -1, -1, -2, -2]
f:2
[6, 5, -1, -1, -1, -2, -2]
i:2
f:4
[6, 5, -1, -1, -1, -2, -2]
j:4
[6, 5, 4, -1, -2, -2, -2]
f:3
[6, 5, 4, -1, -2, -2, -2]
i:3
f:4
[6, 5, 4, -1, -2, -2, -2]
j:4
[6, 5, 4, 4, -3, -2, -2]
f:3
[6, 5, 4, 4, -3, -2, -2]
f:4
[6, 5, 4, 4, -3, -2, -2]
i:4
f:5
[6, 5, 4, 4, -3, -2, -2]
j:5
[6, 5, 4, 4, 5, -5, -2]
# 答え
5
（参考）
Submission #16326133 - AtCoder Beginner Contest 177
E - Coprime
集合｛Ai｝から任意の2つの要素を選んでも互いに素であれば pairwise coprime
上記を満たさないが全要素の最大公約数が1であれば setwise coprime
上二つの条件を満たすかどうかを判定する．
（制約）Ai の長さNは10**6以下，要素の大きさも10**6以下．
解）高速で素因数分解をし，要素に重複があるか調べればよい．
前計算で2と奇数から約数候補を生成する．
def facs(n):
"""試し割り法における割る数を生成する。"""
yield 2
for x in range(3, n, 2):
yield x
main関数では，最初に各数字を入れた配列を作成する．
for x in array:
histogram[int(x)] += 1
ここで先ほど作成した約数候補を用いて，約数の重複がなければpairwise coprime
for divider in facs(MAX_A):
count = sum(histogram[divider::divider])
if count > 1:
break
else:
return 'pairwise coprime'
setwise coprime はgcd関数を利用すればよい.
3つ以上の数の最大公約数を求めるには複数回使用する必要があるが，reduce関数を利用することで簡潔に書ける．
from math import gcd
from functools import reduce
gcd_total = reduce(gcd, array)
if gcd_total == 1:
return 'setwise coprime'
（参考）
Submission #16392807 - AtCoder Beginner Contest 177
F - I hate Shortest Path Problem
右あるいは下に動くことができる．
K+1番目までの最短ルートを求めたい．
解）
縦方向の移動量は等しいので，横方向の移動の最小量を求めればよい．
初期位置と現在位置のずれが最小であるものを求めたい．
各行における答え ret，
初期位置と現在位置を保管しておくdp0とdp，
直進できる場合のインデックスと直進できない場合の最小値のインデックスをarg0，argとして更新していく．
def solve(a, b, H, W):
ret = np.empty(H, i8)
for i in range(H):
ret[i] = -1
dp0 = np.arange(W) #初期位置
dp = np.arange(W) #現在位置
arg0 = W - 1
arg = 0
for i in range(H):
r1 = np.searchsorted(dp, a[i])
r2 = np.searchsorted(dp, b[i])
if b[i] == W: #右端まで壁が続く場合
if r1 == 0:
return ret
else:
dp0 = dp0[: r1] #壁があるところより先は無視する
dp = dp[: r1]
else:
dp[r1:r2] = b[i] #合流させる
if arg0 > -1: #直進する流れが残っている場合
if r1 <= arg0 < r2: #壁がある場合
for j in range(r1 - 1, -1, -1):
if dp[j] == dp0[j]:
arg0 = j #ここまで直進してきた他の流れに乗り換える
ret[i] = i + 1
break
else:
arg0 = -1
arg = np.argmin(dp - dp0) #残っている値の中での最小値
ret[i] = dp[arg] - dp0[arg] + i + 1
else:
ret[i] = i + 1
else:
if r1 <= arg < r2:
arg = np.argmin(dp - dp0)
ret[i] = dp[arg] - dp0[arg] + i + 1
このままでも計算できるが，TLEするものが一つある．
1000行おきに一回流れをまとめて初期位置，現在位置などを残っている流れに応じて初期化することで計算時間を短くすることができる．
if i % 1000 == 999:
m = 0
prev = dp[0]
for k in range(1, dp.shape[0]):
if dp[k] > prev: #dp[0]とは別の流れにあるものについて
dp0[m] = dp0[k - 1] #最小のずれを持つもののみ残してまとめる
dp[m] = prev
m += 1
prev = dp[k]
else: #流れが一つのみの場合はこの流れの実を追いかける
dp0[m] = dp0[dp0.shape[0] - 1]
dp[m] = prev
m += 1
dp0 = dp0[: m]
dp = dp[: m]
if arg0 > -1: #現在最小である流れなどの情報も更新しておく
for j in range(m - 1, -1, -1):
if dp[j] == dp0[j]:
arg0 = j
break
else:
arg = np.argmin(dp - dp0)
（参考）
