D2. Half of Same Codeforces Round #748 (Div. 3)

f:id:baitop:20220124165334p:plain

問題

N要素の整数列Aと以下の操作が与えられる

・あるiについてA[i]-=Kする

あるKについて上の操作を任意の回数行った後に

同じ数字が過半数を占めました

考える最大のKを求めよ

Kには単調性が無いので二分探索などは難しい

（倍数については単調性があるが）

ここでS⊂AなるSで

Sの全要素の値を全て同じに出来る条件は

任意のiについて、S[i]%Kが等しい事だと分かる

しかし今回はこれを使わない（ここから考えて遠くなってしまった...）

Sについて考えるのは正しくて

A, Sを昇順にソートした上で

S[i]についてS[i+1] - S[i]はKの倍数になっていることから

全部を同じ数にしたいようなSとして採用するindexのmaskを決め打って

K = gcd*1で

そのmaskについての答えがKだと求める重い処理よりも

Sの任意の隣り合う2要素の差がKの倍数になるようにした方が効果的である

これは結局

dp[i][k] := iを左端として、そこからkの倍数ずつ右に増える時の長さとすれば

max(dp)が答えになる

ここでiについてkを1~10^6まで考える必要はない

次に使う(隣り合う)インデックスがjだとすると

Kとしてあり得るのは(A[j] - A[i])の約数のみだからである。

よってdpの構築にN * 2*10^6

遷移がi, jの選び方のO(N^2)

kとしてあり得る約数の個数で

間に合う

思った事

maskを使えば性質を考えず解くことが出来る(dpのように)

良い性質が無い場合はそれでいいのだが少し重い

今回は隣接する2要素が条件を満たせば全体も条件を満たすという

dpを高速化するうえでとてもいい性質があったため

maskを使う必要が無かったわけだ

*1:S[i] - S[0]) | 1<= i <= size(S

バイトの競プロメモ