22
2022
【ABC252-Dの反省】いろいろな方法で解いてみる
2022年5月21日に開催されたAtCoder Beginner Contest 252(以下、ABC252) に参加しました。
結果
- 3完(A,B,C) 1WA
- 順位: 3924位
- パフォーマンス: 691
- レーティング: 788 → 779 (-9)
良かった点
- C問題でWAを出した後、WAが出るケースを見つけてACできたこと。
良くなかった点
- C問題でWAを出して、すぐにあきらめてD問題にいったこと。
もうちょっと粘ってもよかったかもという後悔をしている。 - D問題を解ききれなかったこと。なんかもうちょっとでACできそうなんだけどなぁという感触はあった。
今回はD問題を復習します。複数の方が解説していただいているので、わかる範囲で解説ACします。
目次
- D問題について
- まず気がつかないといけなかったこと
- 累積和を利用する
- DPで解いてみる
- 組み合わせ( \(_{n}C_{a}\) ) を利用する
D問題について
問題等は以下のリンクをご確認ください。
まず気がつかないといけなかったこと
どの解き方にせよ、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}\) を利用する方法もコンテスト中に思いついたのですが、余事象は思いつきませんでした。
何かのパターン数を数えるときは余事象も検討するということも忘れないようしよう。
どの解き方も全く知らない知識ではなかったので、発想できなかったのはやっぱり残念だったなぁ。
次にいかそう。