abc177

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

B - Substring
1000文字のSと500文字のTを比べるときに500×501で25万文字くらいの比較が必要になるけど、高々その程度なのでやってよい
pythondef solve(S, T):
    buf = []
    for i in range(len(S) - len(T) + 1):
        diff = 0
        for j in range(len(T)):
            if S[i + j] != T[j]:
                diff += 1
        buf.append(diff)
    return min(buf)
 len(S) - len(T) + 1 の+1を忘れてランタイムエラー
長さが等しいときにループしなくなり、minの対象が空になる

ABC177C

D - Friends
問題文を見てUnionFindで友達グループの個数を求めるのだと思った
グループの個数を求めるのではなく、最大グループのサイズを求めるべきだった
そのグループを1人ずつバラバラにするので。
UnionFindで実装してたが、上記の勘違いで答えが合わない
なのでサンプル1を図に書いて確認しようとした
サンプル1の入力を見て5 3を「5番と3番が友達」と勘違いしてしまった(本当は5人の間に3本の関係)
実際にコンテスト中に描いた図
答えが3になるように問題を解釈し直して「なるほど友達関係は対称ではないのだな」と思い込む
これはてっきりUnionFindだと思い込ませて実はダメですって罠だな！とか思ってた
友人関係が一方通行の場合、最長パスの長さを求める問題になる
この間違った方針でもサンプル1と2は正解しちゃう
方針が正しいと思い込んだままで、サンプル3が合わなくて詰まった
pythondef main():
    global parent, rank
    # parse input
    N, M = map(int, input().split())
    parent = [-1] * N
    rank = [0] * N
    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した
unite, find_rootの実装はこちら https://github.com/nishio/atcoder/blob/master/yosupo/unionfind.py

E - Coprime
エラトステネスの篩で小さい方から素数を確定させながら、その素数でN個の数を割っていった
問題の判定のためには各素因数についてそれぞれ注目して求まるので、素因数分解の結果を保持する必要がない
N個の数のうちある素因数pを持つものがd個あった時、
dが2以上ならpairwiseになり得ない
dがNならnot coprimeに確定
残念ながらTLE
間に合ったもの11件は正しい答えだった
pythondef solve(N, AS):
    is_pairwise = True
    maxAS = max(AS)
    sieved = [False] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if sieved[p]:
            continue
        # p is prime
        x = p + p
        while x <= maxAS:
            sieved[x] = True
            x += p
        sum_div = 0
        for i, a in enumerate(AS):
            dividable = 0
            while a % p == 0:
                a //= p
                dividable = 1
            AS[i] = a
            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ではなく、最初に割り切った素数を書くことで、割り算のツリーを構築するようだ
高速素因数分解であっさりACした
素因数分解の結果を保持することを嫌って上記の書き方にしたのだが、雑にリストに突っ込む方針で問題なかった
pythondef solve(N, AS):
    maxAS = max(AS)
    eratree = [0] * (maxAS + 10)
    for p in range(2, maxAS + 1):
        if eratree[p]:
            continue
        # p is prime
        eratree[p] = p
        x = p * p
        while x <= maxAS:
            if not eratree[x]:
                eratree[x] = p
            x += p

    count = defaultdict(int)
    for a in AS:
        factors = []
        while a > 1:
            d = eratree[a]
            factors.append(d)
            a //= d
        for f in set(factors):
            count[f] += 1

    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)
素数の個数は M / \log(M) ぐらい
素数を求めてから割り算してもNM/\log(M)だからダメ
素数がもっと少ないイメージでいた、\log(M)ぐらい
高速素因数分解は試し割りなしで素因数が求まる
これが本当に\log(M)回でできる
一番多い場合が2^xの時だけど、せいぜい20ぐらい
雑にリストに突っ込むことが問題にならなかったのも、そもそもその程度の個数でしかないからか
今回は有無だけ知りたかったのでsetでuniqしたけど、個数を知りたければCounterに雑に突っ込むだけで良さげ