AOJ0070 Combination of Number Sequences

AOJ Volume0

問題リンク Combination of Number Sequences

  • 解法

AOJ0008のときにほのめかしたキャッシュを使わないと厳しい問題ですね。
単純に解こうとするとO(n!)です。
9!=3*10^5くらいならば時間的に余裕ですが最大ケースである10!だと厳しいです。
なのでn=10のときはキャッシュを使いました。
数式の後ろ3つの項をキャッシュ対象にしました。
選んだ3つは10桁のビットを使って1つの整数で扱います。選んだ数字が1,2,3ならば2^0+2^1+2^2 = 7、なので7という整数値で表します。
プログラムの先頭で
cach[i][j]：選んだ3つの数字iで和jが作れる数
を求めておきます。
n<10のとき、O(n!)で解き、n=10のときは先頭の7つを決めた後このキャッシュを使えばO(7!)+O(1)で解けます。

  • ソース
import java.util.Scanner;

//Combination of Number Sequences
public class AOJ0070 {

	static int n, s, c;
	static boolean[] used;
	static int[][] cach;
	
	static void dfs(int k, int sum){
		if(s < sum)return;
		if(n==10&&k==7){
			if(s-sum>218)return;
			int id = 0;
			for(int i=0;i<10;i++)if(!used[i])id|=1<<i;
			c+=cach[id][s-sum];
			return;
		}
		if(k==n){
			if(sum==s)c++;
			return;
		}
		for(int i=0;i<10;i++){
			if(!used[i]){
				used[i] = true;
				dfs(k+1, sum+(k+1)*i);
				used[i] = false;
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		cach = new int[1<<10][219];
		for(int i=0;i<10;i++){
			for(int j=0;j<10;j++){
				if(i==j)continue;
				for(int k=0;k<10;k++){
					if(k==i||j==k)continue;
					cach[(1<<i)|(1<<j)|(1<<k)][i*8+j*9+k*10]++;
				}
			}
		}
		while(sc.hasNext()){
			n = sc.nextInt();
			s = sc.nextInt();
			c = 0;
			used = new boolean[10];
			dfs(0,0);
			System.out.println(c);
		}
	}
}