問題

D – Distinct Trio

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/5/21 リアルタイム参加　解法わからず。

解法

• あとで書く

コード例1

#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;
}

コード例2

#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;
}

コード例3

#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;
}