2014 Yandex.Algorithm Elimination Stage, Round 2 B - Remainders

問題文

解法

ある数 a_i からスタートした時に，それ以上の値で余りをとっても変化はない．
したがって，数列をまずソートし，最初にする数字を何にするか全部試すのが良さそうである．
これは dp で計算できて，
dp[i] := 大きい方から i 番目まで見た時に，あまりとしてありえる数字の集合
とすると，
dp[i] = dp[i - 1] + (dp[i - 1] に含まれる数を a[i] で割った余り) + a[i]
となる（+ は集合の和とする）．

dp[i - 1] の部分についてだが，途中で a_j で割った後にそれ以上の値 a_k で割っても変化がないという議論のとおり，a_i を最初に選んだ後，それ以下の数字 a_j を次に選んだとすれば，a_j <= a_k <= a_i となる a_k は無視してよくなる．
これをあらわすのが dp[i - 1] の部分である．
あとの2項はそれはそう．

最後に，今できている数字の集合のうち，数列の最小の値以下のものをカウントすると答えになる．以下である理由は，最小値を一番最初の数に選べば，ずっと最後まで残るからである．
ただし，数列に含まれる最小値が複数ある場合は，その値自体を取ることが不可能であるので，その場合は未満でカウントする．

計算量は O(N * max(a[i])) である．

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(rbegin(a), rend(a));

    unordered_set<int> dp;
    for(int i = 0; i < n; ++i) {
        unordered_set<int> nxt = dp;
        nxt.insert(a[i]);
        for(auto x : dp) {
            nxt.insert(x % a[i]);
        }
        dp = move(nxt);
    }

    int ans = 0;
    const int lim = a.back() == a[a.size() - 2] ? a.back() - 1 : a.back();
    for(auto x : dp) {
        ans += x <= lim;
    }

    cout << ans << endl;
}

感想

すぐに書けたけど，よく考えるとうまくできてる問題だなあ．