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 python

def 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} (k n) x^{n - k} y^{k}$
- $\sum_{i} (S + A_{i})^{X} = \sum_{i} (S^{X} + (1 X) S^{X - 1} A_{i}^{1} + \dots)$
- 足し算の順序の変更
  - 中身の足し算を外に出してやると $\sum_{i} A_{i}^{k}$ の形になりそう
  - これは線形オーダーで計算できるから前処理で計算しといて高速化するのだな
  - Sの部分もキレイになりそうだ
- 改めて整理
  - $\sum_{L = 1}^{N - 1} \sum_{R = L + 1}^{N} (A_{L} + A_{R})^{X} = (\sum_{L} \sum_{R} (A_{L} + A_{R})^{X} - \sum_{i} (2 A_{i})^{X}) /2$ … 行列の半分
  - $\sum_{L} \sum_{R} (A_{L} + A_{R})^{X} = \sum_{L} \sum_{R} \sum_{i} (i X) A_{L}^{X - i} A_{R}^{i}$ … 二項定理
  - $= \sum_{i} ((i X) \sum_{L} A_{L}^{X - i} \sum_{R} A_{R}^{i})$ … 足し算の順序の変更　積と和の交換
  - $f (k) = \sum_{i} A_{i}^{k}$ を前計算しとけば $\sum_{i} (i X) f (X - i) f (i)$ になる
実装
- 素朴に書き下していく
  - 2で割るところはmod Pでの逆元を掛ける
  - 組み合わせ計算はmod Pでの組み合わせ
  - 2回TLEしたのは前処理部分のケアレスミス
    - 最初a ** xにしてて余りを取る前に桁が爆発し15TLE
    - 次にpow(a, x, MOD)にしたが9TLE、しばらく頭を抱えた
    - 上記は対数オーダー、毎回累乗しないで過去の結果を使いまわせば定数オーダーになる python

def 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

まず素直に実装してランダム入力を叩き込んで観察します python

def 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が負になることはなさそう
- 上は $⌈ N /2 ⌉$ まで？(違います)
- 上は $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つしか存在しないってのは明らかな罠だった
  - 境界値テスト
元ネタは区間スケジューリングで、知っていれば高橋解が最適解だとわかったそうだ

🪴 Quartz 4.0

ARC106

Graph View

Backlinks