鏡餅を構成する \(2\) つの餅のうち大きいほうを固定して、つまり「ある餅をひとつ取ってきて、その餅が下になる鏡餅についてのみ」考えます。

大きさ \(a\) の餅が下になる鏡餅の種類数は、大きさが \(\dfrac a2\) 以下である餅の個数と等しいです。 よって、すべての餅について、大きさが自身の半分以下である餅の個数を求め、それを合計することでこの問題を解くことができます。

しかし、\(i\) 番目の餅に対して大きさが自身の半分以下である餅の個数は \(\Theta(i)\) 個程度まで多くなることがあり、一つ一つ数えていては実行時間制限に間に合いません（\(A _ i=i\) とすることで個数を \(\dfrac i2\) 個とできます。適切なケースを作ることでより多くすることもできます）。

ここで、尺取り法や二分探索を用いるとこの問題を十分高速に解くことができます。 より具体的には、餅が小さいほうから並んでいることから「どこまでの餅が大きさが \(x\) 以下でどこからが \(x\) より大きいか」がわかれば \(x\) 以下の餅の個数を求めることができます。

尺取り法を用いることで全体の時間計算量を \(\Theta(N)\) に、二分探索を用いた場合は時間計算量を \(\Theta(N\log N)\) とすることができます。

答えが \(32\operatorname{bit}\) 整数に収まらない大きさになる場合があることに注意してください。

実装例は以下のようになります。

(C++, 二分探索)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    for (auto&& a : A)
        cin >> a;

    long ans = 0;
    for (const auto a : A)
        // a / 2 以下の餅の個数 = a / 2 を超える餅と先頭との距離
        ans += ranges::upper_bound(A, a / 2) - begin(A);

    // 合計が答え
    cout << ans << endl;

    return 0;
}

(Python, 二分探索)

from bisect import bisect


N = int(input())
A = list(map(int, input().split()))

ans = 0

for a in A:
    # A の要素のうち a / 2 以下のものの個数を合計する
    ans += bisect(A, a // 2)

print(ans)

(C++, 尺取り法)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N;
    cin >> N;

    vector<int> A(N);
    for (auto&& a : A)
        cin >> a;

    long ans = 0;
    // a / 2 より大きい最初の要素（なければ最後の次）を表す値 j
    for (int j = 0; const auto a : A) {
        // 越えるまで進める
        while (j < N && A[j] * 2 <= a) j++;
        ans += j;
    }

    cout << ans << endl;

    return 0;
}

(Python, 尺取り法)

N = int(input())
A = list(map(int, input().split()))

ans = 0

# a / 2 より大きい最初の要素（なければ最後の次）を表す値 j
j = 0

for a in A:
    # 越えるまで進める
    while j < N and A[j] * 2 <= a:
        j += 1
    ans += j

print(ans)