AOJ0070

問題:Combination of Number Sequences
0以上の整数n,sが与えられ,
k1 + 2 × k2 + 3 × k3 + ... + n × kn = s
となるような組み合わせが何通りあるかを答える問題.
ただし,kは0から9まででそれぞれ1回しか使えない.

幅優先で探索+自明な枝刈り.10秒超でTLE+MLE
ノードをpair>で管理していたのをint*3にしたり,
自明な枝刈りが効きやすくするようにループを逆順にしたり.8秒強でTLE+MLE
幅優先じゃなくて深さ優先の方が同時に保持するノード数が少ないと思ったので,
queue → stackにしてみる.4秒強でTLEのみ.
さらに自明な枝刈りを3行ほど追加.1秒切りAC.←(一番効いた)
楽しかった!

もっと頭のいい解き方があると思うけどなぁ..

#include <iostream>
#include <stack>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
struct Node{
	int nkr;
	int cnt;
	int bit;
};
int main(){
	int n,s;
	while(cin >> n >> s){
		int ret = 0;
		stack<Node> q;
		if(s == 0){cout<<0<<endl;continue;}
		rep(i,10){
			Node m;
			m.nkr = s-i*n;
			m.bit = 1<<i;
			m.cnt = n-1;
			q.push(m);
		}
		while(!q.empty()){
			Node m = q.top();
			q.pop();
			rep(i,10){
				if(!(m.bit & (1<<i) )){
					Node o = m;
					o.nkr -= i*o.cnt--;
					o.bit += (1<<i);
					if(!o.cnt && !o.nkr){ret++;}
					if( !o.cnt || o.nkr<0 || 
					  o.cnt==1 && o.nkr> 9 || 
					  o.cnt==2 && o.nkr>(2*9+8) ||
					  o.cnt==3 && o.nkr>(3*9+2*8+7))continue;
					q.push(o);
				}
			}
		}
		cout<< ret << endl;
	}
}