mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #206 (Div. 1) C. Vasya and Beautiful Arrays

解法

配列がすべて d の倍数になるように出来るとすると, 配列のすべての数が m*d + x (x は min(k, d-1) 以下の数)という形で表せることになるので, このようになっているかを調べます。d を全列挙したとしても, これを調べるのにかかる時間は, D を配列 a の最大値として,

D/1 + D/2 + D/3 + ...

となり, これは D log D に収束するので, 時間内に答えを求めることが出来ます。

const int MAXN = 300030;
const int MAXK = 1000000;
int s[2*MAXK+1];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        s[a]++;
    }
    for (int i = 1; i <= 2*MAXK; i++) {
        s[i] += s[i-1];
    }
    for (int d = MAXK; d >= 1; d--) {
        int cnt = 0;
        for (int x = d; x <= MAXK; x+=d) {
            cnt += s[x+min(d-1, k)] - s[x-1];
            if (cnt >= n) {
                cout << d << endl;
                return 0;
            }
        }
    }
    assert(true);
    return 0;
}