[AtCoder] 第二回全国統一プログラミング王決定戦本戦 A – Count Triplets

2019年12月21日

問題

方針

\( A_i < A_j \) を満たす \( (i, j) \ ( i < j ) \) の数を \( l_j \) とし、\( A_j < A_k \) を満たす \( (j, k) \ ( j < k ) \) の数を \( r_j \) とすると、条件を満たす \( (i,j,k) \) の組み合わせの数は、

\[\sum_{j = 2}^{N – 1} l_jr_j\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ll l = 0;
        ll r = 0;
        for (int j = i - 1; j >= 0; j--) {
            if (A[j] < A[i]) l++;
        }
        for (int j = i + 1; j < N; j++) {
            if (A[i] > A[j]) r++;
        }
        ans += r * l;
    }
    cout << ans << "\n";
    return 0;
}