March [AtCoder Beginner Contest 089 C]

atcoder.jp

M,A,R,C,H の5つから3つを選ぶ組み合わせは 5C3 から 10通り です。解説には「たかだか10通りなのだから全て試せばよい」とありますが、ちょっと面倒くさいので、ついさっき記事を書いたビット全探索で解いてみることにしました。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int n = sc.nextInt();
		long[] ar = new long[5];
		for (int i=0; i<n; i++) {
			String s = sc.next();
			if (s.charAt(0) == 'M') ar[0]++;
			else if (s.charAt(0) == 'A') ar[1]++;
			else if (s.charAt(0) == 'R') ar[2]++;
			else if (s.charAt(0) == 'C') ar[3]++;
			else if (s.charAt(0) == 'H') ar[4]++;
		}
		
		long ans = 0L;
		for (int i=0; i<Math.pow(2,5); i++) {
			
			//立っているビットの数が3以外ならcontinue
			String s = String.valueOf(Integer.toBinaryString(i));
			int bitNum = 0;
			for (int j=0; j<s.length(); j++) {
				if (s.charAt(j) == '1') bitNum++;
			}
			if (bitNum != 3) continue;
			
			//列挙された3つの要素をかけ合わせる
			long temp = 1L;
			for (int j=0; j<5; j++) {
				if ((1&i>>j) == 1) {
					temp *= ar[j];
				}
			}
			ans += temp;
			
		}
		
		System.out.println(ans);
		
	}
}

5つから3つを選ぶ組み合わせとは、要素数5の集合から個数3の部分集合を選ぶということに等しいです。よって、ビット全探索で要素数5（M,A,R,C,H）の部分集合を全列挙しつつ、個数3の部分集合だけ抜き出し、その3つの要素をかけ合わせることで答えを求めていきます。

今回のように要素数が5では、手動の全列挙もビット全探索による全列挙もたいして変わりませんが、これが要素数8や9になったら、さすがに手動で全列挙するのは厳しいので、今回のように何らかのアルゴリズムを使用すべきなんでしょうね。