🪴 Quartz 4.0

Search

SearchSearch

ARC107

Dec 01, 2023, 6 min read

2問でした image

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

A

  • 積と和の交換です
  • 和の部分は三角数です
  • python
def 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が与えられた時のを満たすペアの数は定数オーダーで求められる
  • なので「a+b」の取り得るすべての値に対して「c+d」を求めて、上記ペアの数を求めればよい python
def 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以上になるのは一つだけだと思い込んでたこと。実際には複数ある
    • 事後AC python
def 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
    • 三乗のオーダーの解から累積和

Graph View

Backlinks