SRM527 Div2 Hard(950) P8XCoinChangeAnother
ans[]を辞書順最小の解、ans[i]≧2とすると、j≧i+2についてans[j]=0。なぜならば、ans[j]>0となるjが存在したとすると、ans[i]-=2, ans[i+1]+=1, ans[j-1]+=2, ans[j]-=1として、より辞書順の小さい解が作れてしまう。すなわち、ansの中で2以上の要素は連続していて、それ以降の要素は0。
coins_sumのビットに応じて、ansのそれぞれの要素の0, 1を決定していき、最後の2つの要素は連立方程式を解いて求める。ans[i]が2以上になる条件は、ans[i]を0か1にすると、coins_countの残りを全てi+1番目のコインにしたとしても、coins_sumの残りよりも大きくなってしまうこと。連立方程式が非負の解を持たないなら、条件を満たすコインの集合は作れない。
#include <vector> using namespace std; class P8XCoinChangeAnother{public: vector<long long> solve( int N, long long coins_sum, long long coins_count ) { vector<long long> ans(N); int i; for ( i=0; i<N-2; i++ ) { long long t = coins_sum>>i&1; if ( (coins_sum>>(i+1)) < coins_count-t ) break; ans[i] = t; coins_sum -= t<<i; coins_count -= t; } long long t0 = 2*coins_count - (coins_sum>>i); long long t1 = (coins_sum>>i) - coins_count; if ( t0<0 || t1<0 || N==1 && t1!=0 ) return vector<long long>(); ans[i] = t0; if ( t1!=0 ) ans[i+1] = t1; return ans; }};