ARC106

NISHIO Hirokazu [Translate]
ARC106
A,B,Dの三問でした。Cに悩みかけたけど、今までの経験から「まずは問題を全部読もう」と気づいてDを読んで、Dの方は単なる式変形で僕にとってやさしいからそっちを先に解いてからCに戻った。Cは正しそうな出力を生成できてるのだけど2件だけWAになって間に合わなかった。

やったー、水色になったよ！！
最後の10分くらいにドタバタしてた。
Dを40分弱で通して残り45分だったのだがバグを取りきれなくてCは通らず。まあDを先にやる判断が出来たのが僕の中での進歩か。

A - 106
考えたこと
AやBの取りうる値は対数オーダーなので実際のところいくつあるのか？
10^18以下の3^Aを数えてみる→37個
じゃあ全探索で余裕だね
python def solve(N):
     P3 = [3, 9, 27, 81, ...]
     P5 = [5, 25, 125, 625, ...]
     for i, x in enumerate(P3):
         for j, y in enumerate(P5):
             if x + y == N:
                 print(i + 1, j + 1)
                 return
     print(-1)
Aではなく3^Aをprintしてしまって1WA

B - Values
考えたこと
パスを通して値を移動できる
連結成分の中身の和が同じならOK
UnionFindで連結成分を求めて、連結成分ごとのAとBの和を求める、一つでも差があればNo
pythondef solve(N, M, AS, BS, CD):
    init_unionfind(N)
    for (c, d) in CD:
        unite(c - 1, d - 1)

    sumA = defaultdict(int)
    sumB = defaultdict(int)
    for v in range(N):
        root = find_root(v)
        sumA[root] += AS[v]
        sumB[root] += BS[v]

    for k in sumA:
        if sumA[k] != sumB[k]:
            return "No"
    return "Yes"

Cはしばらく眺めて手で具体例を作ったけど道筋が見えなかったので他の問題を読むことにした。Dが簡単そうだったのでDを解くことにした。

D - Powers
考えたこと
行列の半分:
\sum_{i=1}^{N-1} \sum_{j=i+1}^N A_{ij} = (\sum_{ij} A_{ij} - \sum_i A_{ii}) / 2
Nが10^5と大きいので二乗のオーダーになるような処理はできない、ということは一列まとめて処理できるかも
jを固定して考えてみる
\sum_i (S + A_i)^X
二項定理:
(x+y)^{n}=\sum _{k=0}^{n}{n \choose k}x^{n-k}y^{k}
\sum_i (S + A_i)^X = \sum_i \left( S^X + \binom{X}{1} S^{X-1}A_i^1 + \ldots \right)
足し算の順序の変更
中身の足し算を外に出してやると\sum_i A_i^kの形になりそう
これは線形オーダーで計算できるから前処理で計算しといて高速化するのだな
Sの部分もキレイになりそうだ
改めて整理
\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (A_L+A_R)^X = \left(\sum_L\sum_R (A_L + A_R)^X - \sum_i (2A_i)^X \right) / 2 ... 行列の半分
\sum_L\sum_R (A_L + A_R)^X = \sum_L\sum_R\sum_i \binom{X}{i} A_L^{X-i}A_R^i ... 二項定理
= \sum_i \left(\binom{X}{i} \sum_LA_L^{X-i} \sum_R A_R^i \right)... 足し算の順序の変更　積と和の交換
f(k) = \sum_i A_i^k を前計算しとけば \sum_i \binom{X}{i} f(X-i) f(i)になる
実装
素朴に書き下していく
2で割るところはmod Pでの逆元を掛ける
組み合わせ計算はmod Pでの組み合わせ
2回TLEしたのは前処理部分のケアレスミス
最初a ** xにしてて余りを取る前に桁が爆発し15TLE
次にpow(a, x, MOD)にしたが9TLE、しばらく頭を抱えた
上記は対数オーダー、毎回累乗しないで過去の結果を使いまわせば定数オーダーになる
pythondef solve(N, K, AS):
    MOD = 998_244_353
    div2 = pow(2, MOD - 2, MOD)
    sumTable = [N] * (K + 2)
    ps = AS[:]
    for x in range(1, K + 1):
        s = 0
        for i in range(N):
            s += ps[i]
            s %= MOD
            ps[i] *= AS[i]
            ps[i] %= MOD
        sumTable[x] = s

    c = Comb(K + 1, MOD)
    for x in range(1, K + 1):
        ret = 0
        for i in range(x + 1):
            ret += c.comb(x, i) * sumTable[x - i] * sumTable[i]
            ret %= MOD
        p = pow(2, x, MOD)
        ret -= sumTable[x] * p
        ret %= MOD
        ret *= div2
        ret %= MOD
        print(ret)

C - Solutions
まず素直に実装してランダム入力を叩き込んで観察します
pythondef aoki(LR):
    selected = []
    for lr1 in sorted(LR):
        if not any(is_p(lr1, lr2) for lr2 in selected):
            selected.append(lr1)
    return len(selected)


def takahashi(LR):
    from operator import itemgetter
    selected = []
    for lr1 in sorted(LR, key=itemgetter(1)):
        if not any(is_p(lr1, lr2) for lr2 in selected):
            selected.append(lr1)
    return len(selected)


def random_test():
    from random import seed, randint
    for s in range(1000):
        seed(s)
        LR = []
        for i in range(5):
            W = 20
            l = randint(0, W - 1)
            r = randint(l + 1, W)
            LR.append((l, r))
        t = takahashi(LR)
        a = aoki(LR)
        if t != a:
            print(s, LR, t, a)
観察
Mが負になることはなさそう
上は\lceil N/2 \rceilまで？(違います)
上はN - 2までだな！(追記:違います)
観察結果の中に図Aみたいなのがあったので、あーなるほどね、ってBみたいな感じで生成することにしました
足りない部分の入れ方を忘れてたのでCに修正

大きいのを包み、細かい包まれてるものを子、最後に並んでるのを尻尾と呼ぶことにする
Lでソートすると
包みが真っ先に来るので包まれてる子は排除される
尻尾も排除される
→1
Rでソートすると子が先に処理される
子の数はM個
尻尾の最初のものも追加される
→全体でM+1
これでMが達成できると思っていた
MはN - 2までだと思い込んでたからね
MはN - 1になりうるんじゃないか？と気づいて制約を緩めたが、N - 1の時には尻尾がないので「尻尾の最初のものが追加されて+1」が起きないからこのアルゴリズムで正しいデータを生成できない
ここでコンテスト時間が尽きた
公式解説
MはN-1にはならない
ただしN=1の場合を除く
僕のWAもそこの見落としだった
N-1の時に-1を返していたのをやめた結果N1M0は通るようになったが上記のアルゴリズムが正しくない結果を作るので他のM=N-1のテストが通らなくなった
反省点
残り10分くらいで完全にパニクってた
問題条件を見た時にNが1からなのは一瞬心に引っ掛かりがあったのだがスルーしてしまった
区間の交わりについて議論する時に、対象が1つしか存在しないってのは明らかな罠だった
境界値テスト
元ネタは区間スケジューリングで、知っていれば高橋解が最適解だとわかったそうだ