ABC177

始まる前から体調悪い自覚症状はあったんだけど、ボロボロですな。3完でレーティングは初めて下がってしまいました。

https://gyazo.com/a1c1ce807b5c48bb8acf5b1378021952

https://gyazo.com/157cbe9e3a257f5f09ef30b0ce3a73ef

https://gyazo.com/31963897ac43a0a816ff702807ccfb41

1000文字のSと500文字のTを比べるときに500×501で25万文字くらいの比較が必要になるけど、高々その程度なのでやってよい

code:python

def solve(S, T):

buf = []

for i in range(len(S) - len(T) + 1):

diff = 0

for j in range(len(T)):

diff += 1

buf.append(diff)

return min(buf)

長さが等しいときにループしなくなり、minの対象が空になる

https://gyazo.com/3c84120da2969ef35f6b0afd857a4453

グループの個数を求めるのではなく、最大グループのサイズを求めるべきだった

そのグループを1人ずつバラバラにするので。

UnionFindで実装してたが、上記の勘違いで答えが合わない

なのでサンプル1を図に書いて確認しようとした

サンプル1の入力を見て5 3を「5番と3番が友達」と勘違いしてしまった(本当は5人の間に3本の関係)

https://gyazo.com/689970ee403670a824ab06cbf43739f8

実際にコンテスト中に描いた図

https://gyazo.com/416dd244072893bb42a898bd7c4153f3

答えが3になるように問題を解釈し直して「なるほど友達関係は対称ではないのだな」と思い込む

これはてっきりUnionFindだと思い込ませて実はダメですって罠だな！とか思ってた

友人関係が一方通行の場合、最長パスの長さを求める問題になる

この間違った方針でもサンプル1と2は正解しちゃう

方針が正しいと思い込んだままで、サンプル3が合わなくて詰まった

code:python

def main():

global parent, rank

# parse input

N, M = map(int, input().split())

for q in range(M):

a, b = map(int, input().split())

unite(a - 1, b - 1)

xs = list(find_root(x) for x in range(N))

# debug(": xs", xs)

# print(len(set(xs))) # WRONG!

from collections import Counter

print(max(Counter(xs).values()))

グループの個数を求める間違った一行を消して、最大グループのサイズを求める二行を足したらACした

https://gyazo.com/3f83c85c25e404bbf5ad558341687eb7

問題の判定のためには各素因数についてそれぞれ注目して求まるので、素因数分解の結果を保持する必要がない

N個の数のうちある素因数pを持つものがd個あった時、

dが2以上ならpairwiseになり得ない

dがNならnot coprimeに確定

残念ながらTLE

間に合ったもの11件は正しい答えだった

code:python

def solve(N, AS):

is_pairwise = True

maxAS = max(AS)

for p in range(2, maxAS + 1):

continue

# p is prime

x = p + p

while x <= maxAS:

x += p

sum_div = 0

for i, a in enumerate(AS):

dividable = 0

while a % p == 0:

a //= p

dividable = 1

sum_div += dividable

if sum_div >= 2:

is_pairwise = False

if sum_div == N:

return "not coprime"

if is_pairwise:

return "pairwise coprime"

return "setwise coprime"

複数の数の高速な素因数分解は先にエラトステネスを終わらせるらしい

単にboolではなく、最初に割り切った素数を書くことで、割り算のツリーを構築するようだ

code:python

def solve(N, AS):

maxAS = max(AS)

for p in range(2, maxAS + 1):

continue

# p is prime

x = p * p

while x <= maxAS:

x += p

count = defaultdict(int)

for a in AS:

factors = []

while a > 1:

factors.append(d)

a //= d

for f in set(factors):

if any(x == N for x in count.values()):

return "not coprime"

if any(x >= 2 for x in count.values()):

return "setwise coprime"

return "pairwise coprime"

除算の回数をカウントして比較した

100000 100001 100003の時、僕の元のバージョンは 28792回なのに対して高速素因数分解は13回だったのでまったく比較にならないということがわかった

計算量の考察

数の個数をN、一番大きい数をMとする(今回はどちらも10^6)

高速素因数分解は試し割りなしで素因数が求まる

一番多い場合が2^xの時だけど、せいぜい20ぐらい

雑にリストに突っ込むことが問題にならなかったのも、そもそもその程度の個数でしかないからか

今回は有無だけ知りたかったのでsetでuniqしたけど、個数を知りたければCounterに雑に突っ込むだけで良さげ