arc107

NISHIO Hirokazu [Translate]
ARC107
2問でした

2問しか解けなかったので緑に反落するかと覚悟したけど意外と-8程度で済んだので水色継続中

A
積と和の交換です
\sum_{i,j} a_i \times b_j = (\sum_i a_i) \times (\sum_j b_j)
和の部分は三角数です
T_n = \sum_{i=1}^n i = n(n + 1) / 2
pythondef solve(A, B, C):
    MOD = 998_244_353
    a = A * (A + 1) // 2
    a %= MOD
    b = B * (B + 1) // 2
    b %= MOD
    c = C * (C + 1) // 2
    c %= MOD
    return (a * b) % MOD * c % MOD

B
二つの数a,bが与えられた時の1 \leq a,b \leq Nを満たすペアの数は定数オーダーで求められる
なので「a+b」の取り得るすべての値に対して「c+d」を求めて、上記ペアの数を求めればよい
pythondef solve(N, K):
    def f(x):
        if x < 2:
            return 0
        if x > 2 * N:
            return 0
        return N - abs(x - (N + 1))

    ret = 0
    for ab in range(2, 2 * N + 1):
        cd = ab - K
        ret += f(ab) * f(cd)

    return ret

C
考えたこと
各値が互いに異なることが重要そう
N=1の時が危険そう
N=50と小さい
"全てのiについて~を満たすx, yを選び、行列のx, y列目をswapする。"
"((全てのiについて~を満たすx, y)を選び、行列のx, y列目をswapする。)"なのだが、 "(全てのiについて(~を満たすx, yを選び、行列のx, y列目をswapする。))"と誤読して混乱した
飛ばしてDへ
残り50分で戻ってきた
誤読に気づいた
列でswapしても行の条件に影響しないので独立の問題として扱ってよい　XとYにわける
それぞれの場合の数を求めて掛け算
最初、交換可能なペアの数を求めて階乗したが、4つが互いに交換できる時ペアは6個になるから正しくない
UnionFindで連結成分を求めた
3WA
「そうかまったく同じ内容の列がある時にはそれを交換しても種類数が増えないのだな」とか思ってそれを除算する実装してたけど、問題条件ですべての数が異なると言ってるので無駄な心配だった
WAの原因は、連結成分のサイズが2以上になるのは一つだけだと思い込んでたこと。実際には複数ある
例　https://twitter.com/cs_c_r_5/status/1322537172088446982?s=21
事後AC
pythondef solve(N, K, AS):
    from collections import Counter
    from collections import defaultdict
    MOD = 998_244_353
    init_unionfind(N)
    for i in range(N):
        for j in range(i + 1, N):
            if all(AS[i][k] + AS[j][k] <= K for k in range(N)):
                unite(i, j)
    ok1 = Counter(find_root(x) for x in range(N)).values()

    init_unionfind(N)
    for i in range(N):
        for j in range(N):
            if all(AS[k][i] + AS[k][j] <= K for k in range(N)):
                unite(i, j)
    ok2 = Counter(find_root(x) for x in range(N)).values()

    ret = 1
    for n in ok1:
        for x in range(1, n + 1):
            ret *= x
            ret %= MOD
    for n in ok2:
        for x in range(1, n + 1):
            ret *= x
            ret %= MOD

    return ret


D
n, kの状態から1をx個使った場合、残りはn - x個。
k - xを1/2以下の数で表現するので、両辺2倍すれば2(k - x)を1以下の数で表現する問題になる
K,Nは最大3000なので、掛けても10^7より小さい
というわけでDPで実装したが、サンプルでTLEするので頭を抱えた
諦めてCに戻る
コンテスト後Twitterを見ていると三乗のオーダーになってそこから進めなかったという投稿が。僕も遷移のたびに1をいくつ使うかでループしてるので同じだろう。
しかし公式解説みたいに1を1個使うかどうかの二択にしてループを無くしても解決しない　14TLE
塗りつぶし順序に自信がなくてメモ化再帰にしてるのが悪いのか、もっと本質的に間違ってるのか
https://maspypy.com/atcoder-参加感想-2020-10-31arc107
三乗のオーダーの解から累積和
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:17:43 PM[Edit]
Related Pages
