ABC 89 C-March

問題概要

  • N人の人がいて、i番目の人の名前は\(S_i\)
  • この中から、以下の条件を満たすように3人を選ぶ
    • 全ての人の名前がM, A, R, C, H のどれかから始まる
    • 同じ文字から始まる名前を持つ人が複数いない
  • これらの条件を満たすように3人を選ぶ方法の総数を求めよ。ただし、選ぶ順番は考えない。
  • 答えが32bit整数型に収まらない場合に注意せよ。

制約

  • 1 ≤ N ≤ 105
  • \(S_i\)は英大文字からなる
  • 1 ≤ \(S_i\) ≤ 10
  • \(S_i \neq S_j, (i \neq j)\)

問題へのリンクはこちら

考えたこと

  • 5つの文字から3つの文字を選ぶ方法はたかだか10通り
  • それぞれの文字が何回出たかを管理するための配列を用意して、上で選んだ３つの配列の個数の積を足し合わせる
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll backet[5] = {0};

int main() {
  int n; cin >> n;
  // どの３つが選択されたかを表す配列３つ
  int p[10] = {0,0,0,0,0,0,1,1,1,2};
  int q[10] = {1,1,1,2,2,3,2,2,3,3};
  int r[10] =  {2,3,4,2,4,4,3,4,4,4};
  
  for(int i = 0; i < n; ++i) {
    string s; cin >> s;
    if(s[0] == 'M') bucket[0]++;
    else if(s[0] == 'A') bucket[1]++;
    else if(s[0] == 'R') bucket[2]++;
    else if(s[0] == 'C') bucket[3]++;
    else if(s[0] == 'H') bucket[4]++;
  }
  ll ans = 0;
  for(int i = 0; i < 10; ++i) {
    ans += bucket[p[d]] * bucket[q[d]] * bucket[r[d]];
  }
  cout << ans << endl;
  
  return 0;
}