ARC107

2問でした

https://gyazo.com/270a4eee1e8f883aac8d104b633c0db1

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

https://gyazo.com/e5bb4b1f756a2c4a123ebe89dda9f5ae

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

code: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」の取り得るすべての値に対して「c+d」を求めて、上記ペアの数を求めればよい

code: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分で戻ってきた

誤読に気づいた

それぞれの場合の数を求めて掛け算

最初、交換可能なペアの数を求めて階乗したが、4つが互いに交換できる時ペアは6個になるから正しくない

UnionFindで連結成分を求めた

3WA

「そうかまったく同じ内容の列がある時にはそれを交換しても種類数が増えないのだな」とか思ってそれを除算する実装してたけど、問題条件ですべての数が異なると言ってるので無駄な心配だった

WAの原因は、連結成分のサイズが2以上になるのは一つだけだと思い込んでたこと。実際には複数ある

事後AC

code: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):

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):

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

塗りつぶし順序に自信がなくてメモ化再帰にしてるのが悪いのか、もっと本質的に間違ってるのか

三乗のオーダーの解から累積和