AOJ2026 Divisor is the Conqueror

問題リンク Divisor is the Conqueror

• 概要

1〜13の数字が書かれたカードをN枚持っている。
最初は手札のうち任意の1枚を場に出す。2枚目以降は、場に出ているカードの総和Sを割り切る数字が書かれたカードしか出せない。このルールの下でN枚のカード全てを場に出せる出し方をどれか1つ答えよ。そのような出し方ができない場合、"No"とせよ。
1 <= N <= 52
1〜13のカードはそれぞれ高々4枚までしか登場しない

• 解法

全探索+枝刈りで解きました。
大きな工夫は、1枚目のカードから決めていくのではなく、後ろのカードから決めていくことです。
初期状態の手札の数の合計をSとすると、最後に出すカードとして可能なものは (S-x)%x==0 を満たすカードxです。最後から2番目に出すカードで可能なものは (S-x-y)%y==0 を満たすy ・・・というように決定していくことができます。たぶん、1枚目のカードから決定していくやり方より探索の分岐が少ないから高速なのだと思います。

• ソース

import java.util.Scanner;

//Divisor is the Conqueror
public class AOJ2026 {

	int n;
	int[] c, res;
	
	boolean dfs(int k, int rest){
		if(k<0)return true;
		for(int i=1;i<14;i++){
			if(c[i]==0||(rest-i)%i!=0)continue;
			c[i]--; res[k] = i;
			if(dfs(k-1, rest-i))return true;
			c[i]++;
		}
		return false;
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			n = sc.nextInt();
			if(n==0)break;
			c = new int[14]; res = new int[n];
			int s = 0;
			for(int i=0;i<n;i++){
				int x = sc.nextInt();
				s += x;
				c[x]++;
			}
			if(dfs(n-1, s)){
				for(int i=0;i<n;i++)System.out.print(res[i]+(i==n-1?"\n":" "));
			}
			else System.out.println("No");
		}
	}
	
	public static void main(String[] args) {
		new AOJ2026().run();
	}
}