面白かった！

問題へのリンク

問題概要

正の整数からなる長さ $N$ の数列 $A_{1}, A_{2}, \dots, A_{N}$ が与えられる。

$\displaystyle \sum_{i=1}^{N-1} \sum_{j=i+1}^{N} \lfloor \frac{\max(A_{i}, A_{j})}{\min(A_{i}, A_{j})} \rfloor$

の値を求めよ。

制約

$2 \le N \le 2 \times 10^{5}$
$1 \le A_{i} \le 10^{6}$

考えたこと

まず、 $A_{i} \le 10^{6}$ という制約が怪しい！！！
きっと、 $M = \max(A_{1}, A_{2}, \dots, A_{N})$ として $O(M \log M)$ な計算量になるに違いないと思えた。

とりあえず、数列を元のまま考えるのではなく、度数分布表を作ることにした。つまり、次の配列を考えることにした。

num[v] ← 数列 $A_{1}, A_{2}, \dots, A_{N}$ の中の整数値 $v$ の個数

まず $A_{i} = A_{j}$ であるような $(i, j)$ については別に数えることにする。このとき、 $d = 1, 2, \dots, M$ に対して、次の値の総和を求めて、num[d] をかけた値を求めていけばよいことがわかる。

値が $(d, 2d)$ であるものの、数列の中での個数
値が $\lbrack 2d, 3d)$ であるものの、数列の中での個数 $\times 2$
値が $\lbrack 3d, 4d)$ であるものの、数列の中での個数 $\times 3$
...

そしてこの値を $d = 1, 2, \dots, M$ について合算していけばよい。

最後に計算量を見積もる。各 $d$ について、上記の区間 $(d, 2d), \lbrack 2d, 3d), \lbrack 3d, 4d), \dots$ の個数は $\frac{M}{d}$ 個あるため、全体の計算量は

$\frac{M}{1} + \frac{M}{2} + \dots + \frac{M}{M} = O(M \log M)$

と評価できる

コード

ここでは、上記の値の代わりに、

値が $(d, M \lbrack$ であるものの、数列の中での個数
値が $\lbrack 2d, M \lbrack$ であるものの、数列の中での個数
値が $\lbrack 3d, M \lbrack$ であるものの、数列の中での個数
...

の総和を求めるようにした。

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

int main() {
    const int MAX = 1100000;
    long long N;
    cin >> N;
    vector<long long> A(N), num(MAX, 0), sum(MAX + 1, 0);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        num[A[i]]++;
    }
    for (int i = 0; i < MAX; ++i) sum[i + 1] = sum[i] + num[i];
 
    long long res = 0;
    for (int i = 1; i < MAX; ++i) {
        if (num[i] == 0) continue;
        
        // (i, MAX), [2i, MAX), [3i, MAX), ... の総和
        res += (sum.back() - sum[i+1]) * num[i];
        
        for (int j = i*2; j <= MAX; j += i) {
            res += (sum.back() - sum[j]) * num[i];
        }
    }
    
    // 等しいところは別途処理
    for (int i = 1; i < MAX; ++i) {
        res += num[i] * (num[i] - 1) / 2;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 356 E - Max/Min (1D, 水色, 475 点)

問題概要

制約

考えたこと

コード