Back to : algorithms
Contents

풀이

문제를 간단히 요약하면, 자연수들이 주어질 때 $f(k, I)$ 를 $k$로 나눈 나머지가 $I$인 수들로 정의한다. 이때 이 값을 최대한 크게 하는 문제이다.

단순하게 접근한다면 한 $(k, I)$ 값이 주어졌을 때 $O(n)$에 $f$값을 계산해 볼 수 있지만, 어차피 계속 $k$로 나눈 모듈러값을 쓸 것이므로 잘 계산하면 $O(n)$에 $k$ 하나와 해당하는 모든 $I$값에 대해 함수값을 동시에 계산할 수 있다. 이렇게 계산하면 시간 복잡도는 $O(mn)$ ($m$은 최대 범위) 인데, 이는 아직 시간 초과를 피하기 힘들다.

여기서 비둘기집의 원리를 이용한 최적화를 하는데, $k = 2$인 경우를 생각해 보면, $f(2, 0)$은 주어진 수 중 짝수의 개수, $f(2, 1)$은 홀수의 개수이므로 둘 중 하나는 반드시 $n / 2$ 를 넘게 된다. 따라서, 답의 하한이 $n / 2$임을 알 수 있다.

모든 수가 다르다 는 것에 주목하자. $f(k, I)$값이 크려면, $I, k + I, 2k + I, \dots$ 형태의 수들이 많아야 한다. 그런데 만약 $k > 2m / n$ 이면, 모든 수가 $m$ 이하이므로, 이 수들이 $n / 2$ 개 이상 될 수 없다. 따라서 $k$의 값을 $2m / n$ 까지만 보면 충분하고, 이렇게 계산하면 시간 복잡도는 $O(m)$ 이 된다.

$O(n)$에 모든 $I$값에 대해 한번에 계산하는 부분이 조금 어려워서 (memset을 매번 하면 시간이 꼬였었다) 고민을 많이 하다가 따로 풀이를 듣고 알았다. :( 상당히 clever하다는 생각이 들었다.

코드

#include <bits/stdc++.h>
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

int n, m = 2e6, arr[1010];
int rem[2020202];
int vst[2020202];
int chk(int c)
{
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int r = arr[i]%c;
        if (vst[r] != c)
        {
            vst[r] = c;
            rem[r] = 1;
        }
        else
            rem[r]++;
        ans = max(ans, rem[r]);
    }
    return ans;
}
int32_t main()
{
    usecppio
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    int ans = 0;
    int mv = min(m, 2*m / n + 5);
    fflush(stdout);
    for (int i = 2; i <= mv; i++)
        ans = max(ans, chk(i));
    cout << ans << '\n';
}