#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

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

  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
  }

  vector<int> cnt(200010);
  rep(i, N) {
    cnt[A[i]]++;
  }

  rep(i, 200009) {
    cnt[i+1] += cnt[i];
  }

  ll ans = 0;
  rep(j, N) {
    ans += cnt[A[j]-1] * (N - cnt[A[j]]);
  }

  cout << ans << endl;
  return 0;
}

D問題の入力例1は、1 が 2 個、3 が 1 個、4 が 1 個あるので、累積和で整理すると以下のようになる。

値　 | 1 | 2 | 3 | 4 |
個数 | 2 | 2 | 3 | 4 |

\(j\) を値 \(3\) だとすると \(2\) 以下は \(2\) 個あって \(4\) 以下は \(1 = 4 – 3\) 個ある。
したがって、\(j\) が値 \(3\) の場合は、\(2 \times 1 = 2\) パターンある。
なるほど。
この発想はコンテスト中に全く思いつかなかったので、忘れないようにしたいです。

DPで解いてみる

Nyaan さんの解説を参考にしてACしたのが以下のコードです。

提出した結果はこちらです。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

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

  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
  }

  map<ll,ll> mp;
  ll mx = 0;
  rep(i, N){
    mp[A[i]]++;
    mx = max(mx, A[i]);
  }

  vector<vector<ll>> dp(200010, vector<ll>(4));
  dp[0][0] = 1;

  rep(i, mx+1) {
    if (i == 0) {continue;}
    rep(j, 4) {
      if (j == 0) {
        dp[i][j] += dp[i-1][j];
      } else {
        dp[i][j] += dp[i-1][j];
        dp[i][j] += dp[i-1][j-1] * mp[i];
      }
    }
  }

  cout << dp[mx][3] << endl;
  return 0;
}

\(dp_{i,j} := i\) まで確定していて、集合のサイズが \(j\) である通り数。

コンテスト中も一瞬「DPでいけるんじゃないか？」と考えたのですが、\(i\) を \(A[i]\) まで見たとき…と考えていたのでできませんでした。
あー、なるほど。
こうすればよかったのか。

組み合わせ（ \(_{n}C_{a}\) ) を利用する

toam さんの解説を参考にしてACしたのが以下のコードです。

提出した結果はこちらです。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

// n_C_a を計算する
ll f(int n, int a) {
  ll x = 1;
  ll y = 1;
  for(int i = 0; i < a; i++) {
    x =(ll) x * (n - i);
    x /=(ll) (i + 1);
  }
  return x;
}

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

  vector<ll> A(N);
  rep(i, N) {
    cin >> A[i];
  }

  map<int,int> mp;
  rep(i, N) {
    mp[A[i]]++;
  }

  // 全パターン計算する
  ll ans = f(N, 3);

  for(auto i:mp) {
    // 3つのうち2個同じ数のパターンを引く
    ans -= f(i.second, 2) * (N - i.second);
    // 3つ全部同じ数のパターンを引く
    ans -= f(i.second, 3);
  }

  cout << ans << endl;
  return 0;
}

\(_{n}C_{a}\) を利用する方法もコンテスト中に思いついたのですが、余事象は思いつきませんでした。
何かのパターン数を数えるときは余事象も検討するということも忘れないようしよう。

どの解き方も全く知らない知識ではなかったので、発想できなかったのはやっぱり残念だったなぁ。
次にいかそう。

TakahiroNakamori

ナカモリタカヒロ

【ABC252-Dの反省】いろいろな方法で解いてみる

結果

良かった点

良くなかった点

目次

D問題について

まず気がつかないといけなかったこと

累積和を利用する

DPで解いてみる

組み合わせ（ \(_{n}C_{a}\) ) を利用する