baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ Codeforces 最大公約数 余り 数学 DP高速化 任意の隣接要素が条件を満たせば、全体も条件を満たす bit https://codeforces.com/contest/1593/problem/D2 問題 N要素の整数列Aと以下の操作が与えられる ・あるiについてA[i]-=Kする あるKについて上の操作を任意の回数行った後に 同じ数字が過半数を占めました 考える最大のKを求めよ Kには単調性が無いので二分探索などは難しい （倍数については単調性があるが） ここでS⊂AなるSで Sの全要素の値を全て同じに出来る条件は 任意のiについて、S[i]%Kが等しい事だと分かる しかし今回はこれを使わない（ここから考えて遠くなってしまった...） Sについて考えるのは正しくて A, Sを昇順にソートした上で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2022%2F01%2F24%2F170811" title="D2. Half of Same Codeforces Round #748 (Div. 3) - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/baitop/20220124/20220124165334.png Hatena Blog https://hatena.blog 2022-01-24 17:08:11 rich https://baitop.hatenadiary.jp/entry/2022/01/24/170811 1.0 100%