ARC106
A,B,Dの三問でした。Cに悩みかけたけど、今までの経験から「まずは問題を全部読もう」と気づいてDを読んで、Dの方は単なる式変形で僕にとってやさしいからそっちを先に解いてからCに戻った。Cは正しそうな出力を生成できてるのだけど2件だけWAになって間に合わなかった。
やったー、水色になったよ！！
https://gyazo.com/f6135300b90474a9c0175d10ef3dfc84
最後の10分くらいにドタバタしてた。
Dを40分弱で通して残り45分だったのだがバグを取りきれなくてCは通らず。まあDを先にやる判断が出来たのが僕の中での進歩か。
https://gyazo.com/6dcc9c30c3a947d684e21eeb966422c6
https://gyazo.com/aba565e81dd5db9689935f8782ad2c78
考えたこと
AやBの取りうる値は対数オーダーなので実際のところいくつあるのか？
10^18以下の3^Aを数えてみる→37個
じゃあ全探索で余裕だね
code:python
def solve(N):
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
https://gyazo.com/931e302096bd35ae11211d9a78108dc6
考えたこと
パスを通して値を移動できる
連結成分の中身の和が同じならOK
UnionFindで連結成分を求めて、連結成分ごとのAとBの和を求める、一つでも差があればNo code: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)
for k in sumA:
return "No"
return "Yes"
Cはしばらく眺めて手で具体例を作ったけど道筋が見えなかったので他の問題を読むことにした。Dが簡単そうだったのでDを解くことにした。
https://gyazo.com/4e95f3152b0c1452034c7670d5a85f7e
考えたこと
$ \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回TLEしたのは前処理部分のケアレスミス
最初a ** xにしてて余りを取る前に桁が爆発し15TLE
次にpow(a, x, MOD)にしたが9TLE、しばらく頭を抱えた
上記は対数オーダー、毎回累乗しないで過去の結果を使いまわせば定数オーダーになる
code:python
def solve(N, K, AS):
MOD = 998_244_353
div2 = pow(2, MOD - 2, MOD)
for x in range(1, K + 1):
s = 0
for i in range(N):
s %= MOD
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) * sumTablex - i * sumTablei ret %= MOD
p = pow(2, x, MOD)
ret %= MOD
ret *= div2
ret %= MOD
print(ret)
https://gyazo.com/12f24063a7495df28c9c1469f9750843
まず素直に実装してランダム入力を叩き込んで観察します
code: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が負になることはなさそう
上は$ \lceil N/2 \rceilまで？(違います)
上は$ N - 2までだな！(追記:違います)
観察結果の中に図Aみたいなのがあったので、あーなるほどね、ってBみたいな感じで生成することにしました
足りない部分の入れ方を忘れてたのでCに修正
https://gyazo.com/6f1e9a3674c93e46adbdfc591ca487f8
大きいのを包み、細かい包まれてるものを子、最後に並んでるのを尻尾と呼ぶことにする
Lでソートすると
包みが真っ先に来るので包まれてる子は排除される
尻尾も排除される
→1
Rでソートすると子が先に処理される
子の数はM個
尻尾の最初のものも追加される
→全体でM+1
これでMが達成できると思っていた
MはN - 2までだと思い込んでたからね
MはN - 1になりうるんじゃないか？と気づいて制約を緩めたが、N - 1の時には尻尾がないので「尻尾の最初のものが追加されて+1」が起きないからこのアルゴリズムで正しいデータを生成できない
ここでコンテスト時間が尽きた
公式解説
MはN-1にはならない
ただしN=1の場合を除く
僕のWAもそこの見落としだった
https://gyazo.com/cc67ffeb9e3557505cab212c7944375f
N-1の時に-1を返していたのをやめた結果N1M0は通るようになったが上記のアルゴリズムが正しくない結果を作るので他のM=N-1のテストが通らなくなった
https://gyazo.com/6e461c5b6fdb24b8675f88e0136c565a
反省点
残り10分くらいで完全にパニクってた
問題条件を見た時にNが1からなのは一瞬心に引っ掛かりがあったのだがスルーしてしまった
区間の交わりについて議論する時に、対象が1つしか存在しないってのは明らかな罠だった