たくさんの数式 / Many Formulas [AtCoder Beginner Contest 045 C]

atcoder.jp

文字列Sの全ての部分集合を数値として足し合わせた総和を求めよ、という問題です。

実装方針は明確だけれども実装方法が難解というパターンです。再帰関数を使っても解けると思うのですが、あいにく再帰関数は苦手なのでビット全探索を使います。

ビット全探索はビットの立っている位置で部分集合を全探索するアルゴリズムです。例えば、要素数3の集合の部分集合をビット全探索で列挙するには、十進数の 0 ~ 2^3-1 に対応する二進数を用います。

・000（0 = 空集合 ）
・001（1）
・010（2）
・011（3）
・100（4）
・101（5）
・110（6）
・111（7 = 2^要素数-1 ）

とこのようにして要素数3の集合の部分集合を全て列挙することができます。今回の問題ではこのアルゴリズムを利用して「＋」の挿入位置を全パターン列挙し、得られた文字列を実際に計算することで答えを求めていきます。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		String s = sc.next();
		int n = s.length() - 1;
		
		long ans = 0L;
		for (int i=0; i<Math.pow(2,n); i++) {
			
			//ビット全探索で文字列Sに"+"を挿入していく
			StringBuilder sb = new StringBuilder(s);
			for (int j=n-1; j>=0; j--) {
				if ((1&i>>j) == 1) {
					sb.insert(j+1,"+");
				}
			}
			
			//"+"入りの文字列をsplitして足し合わせる
			String[] ar = sb.toString().split("\\+",0);
			for (int j=0; j<ar.length; j++) {
				ans += Long.parseLong(ar[j]);
			}

		}
		
		System.out.println(ans);
		
	}
}

StringBuilder で insert するときは、後ろから挿入していくと挿入位置がズレないので便利です。また、split で "+" や "-" など正規表現に用いられる特定の文字を扱う際には、正規表現と区別するために "\\" を直前に指定する必要があるので、注意が必要です。