AOJ0070
問題:Combination of Number Sequences
0以上の整数n,sが与えられ,
k1 + 2 × k2 + 3 × k3 + ... + n × kn = s
となるような組み合わせが何通りあるかを答える問題.
ただし,kは0から9まででそれぞれ1回しか使えない.
幅優先で探索+自明な枝刈り.10秒超でTLE+MLE
ノードをpair
自明な枝刈りが効きやすくするようにループを逆順にしたり.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; } }