SRM 668 Div2 Hard AnArray

TopCoder Statistics - Problem Statement

• 復習してなかったので、復習。
• 前後半列挙のように一部だけ全探索して、各イテレーションで高速に残りを計算する問題。
• 二分探索とか使えないのでどうしたものかと思っていて時間切れだった。
• 実はイテレーションしながら配列をアップデートする問題。No.122 傾向と対策：門松列（その３） - shifth’s blogと同じようなタイプ。
• ポイントは
  • イテレーションの方向
  • イテレーション変数をどれにするか
  • 配列 A の縮約化(gcd(K,a) することで A[i] <= K となり、num[K] まで考えればよくなる。上記問題でも同じケースだった。)

class AnArray {
public:
int solveProblem(vector <int> A, int K) {
        int N = A.size();

        // K の約数しか判定に使わないので
        // 事前に約数だけの配列にしておく
        // A[i] <= K となる
        for (auto &a : A)
            a = gcd(K,a);

        //
        // (p,q) を固定したとき q より右側で出現する K/gcd(A[p]*A[q],K) の倍数の数が高速で計算できればよい。
        // 事前計算をするのであれば dp[K][N] と O(K*N) のメモリ確保が
        // 必要になってしまうので一つの配列 num を使いまわすようにする。
        //
        // q を降順に移動させていくとき
        // (*,N-1) ... r になるものは 0 個
        // (*,N-2) ... r になり得るものは A[N-1] => A[N-1] の約数をカウント
        // (*,N-3) ... r になり得るものは A[N-2],A[N-1] => A[N-2],A[N-1] の約数をカウント
        //  :
        //
        // という関係性があるのでイテレーションしながら倍数の個数を更新していけばよい。
        vector<int> num(K+1,0);

        // O(N^2)
        int cnt = 0;
        for (int q = N-1; q >= 0; --q)
        {
            REP(p,q)
            {
                int k = K/gcd((ll)A[p]*A[q],(ll)K);
                cnt += num[k];
            }
            auto divs = allDivs(A[q]);
            for (auto d : divs)
                ++num[d];
        }
        return cnt;
}
};