Posted at

ABC089 C - March(300点)


問題概要

問題のリンク

$N$人の人がいる。

以下の条件を満たすように3人選ぶ。


  • 全ての人の名前が $M$,$A$,$R$,$C$,$H$ のどれかから始まっている

  • 同じ文字から始まる名前を持つ人が複数いない

この時何通りの選び方があるか。ただし選ぶ順番は関係ない。


制約条件


  • $1≤N≤10^5$

  • $S_i$ は英大文字からなる

  • $1≤|S_i|≤10$

  • $S_i≠S_j(i≠j)$


考えたこと

先頭の文字が重ならないように選ぶ選び方を考える。

例えば、M,A,R,C,Hから名前が始まる人がそれぞれ1人ずついる場合、以下の選び方で全てであり10通りになる。

image.png

上の図が基本モデルとなる。

まず名前の先頭の文字がM,A,R,C,Hである人の数を数え上げて配列に詰めていく。

重複があってはいけない、かつ選ぶ順番は関係ないので、M,A,R,C,Hを上の図のように組み合わせていき、乗算をしていく。

この時計算量は$O(N)$となるので、問題なくAC。


解答


c.cs

using System;

using System.Linq;

class Program
{
static void Main(string[] args) {
int n = int.Parse(Console.ReadLine());
long[] l = new long[5] {0,0,0,0,0};
for(int i = 0; i < n; i ++) {
string s = Console.ReadLine();
if(s[0]=='M') l[0] ++;
if(s[0]=='A') l[1] ++;
if(s[0]=='R') l[2] ++;
if(s[0]=='C') l[3] ++;
if(s[0]=='H') l[4] ++;
}
Console.WriteLine(solve(l));
}
static long solve(long[] l) {
long count = 0;
for(int i = 0; i < l.Length-2; i ++) {
for(int j = i+1; j <= l.Length-2; j ++) {
count += l[i] * l[j] * (l.Where((x,y) => y > j).Sum());
}
}
return count;
}
}