SRM527 Div2 Hard(950) P8XCoinChangeAnother

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;
}};