はまやんはまやんはまやん

hamayanhamayan's blog

March [AtCoder Beginner Contest 089 C]

https://beta.atcoder.jp/contests/abc089/tasks/abc089_c

解法

https://beta.atcoder.jp/contests/abc089/submissions/2157591

N個の文字列があるが、1文字目以降は特に問題ではない。
最初の文字毎に個数を予め数えておこう。
「m[c] := 最初がcで始まる文字の個数」
 
これを使って、MARCHから始める文字列を3つ取り出す。
MARCHから3つ選ぶ組合せを全探索する。
下の実装では3重ループで実装しているが、色々な実装方法があるだろう。
(全列挙しても、そんなにないのでいいかも)
 
あとは、文字の個数の積の総和が答えになる。

int N; string S[101010];
map<char, ll> m;
string march = "MARCH";
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) m[S[i][0]]++;
 
    ll ans = 0;
    rep(a, 0, 5) rep(b, a + 1, 5) rep(c, b + 1, 5) ans += m[march[a]] * m[march[b]] * m[march[c]];
    cout << ans << endl;
}