TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

05 /
22
2022
 

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

2022年5月21日に開催されたAtCoder Beginner Contest 252(以下、ABC252) に参加しました。

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

結果

良かった点

良くなかった点

今回はD問題を復習します。複数の方が解説していただいているので、わかる範囲で解説ACします。

目次

  1. D問題について
  2. まず気がつかないといけなかったこと
  3. 累積和を利用する
  4. DPで解いてみる
  5. 組み合わせ( \(_{n}C_{a}\) ) を利用する

D問題について

問題等は以下のリンクをご確認ください。

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

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

どの解き方にせよ、D問題の入力例1の場合、

3 1 4 1


1 が 2 個、3 が 1 個、4 が 1 個あると考えます。
そこから3個抜き出したときに、全部値が異なるのは何通りあるか?みたいに考える必要がありました。
これはリアルタイムで参加している時にも気がついていたのでよかったです。

累積和を利用する

kyopro_friends さんの解説 を参考にして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];
  }

  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}\) を利用する方法もコンテスト中に思いついたのですが、余事象は思いつきませんでした。
何かのパターン数を数えるときは余事象も検討するということも忘れないようしよう。

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