TopCoder SRM 631 Div2 Hard TaroCoins

950ptとはいえ楽すぎなような。900ptでもいいかも。
http://community.topcoder.com/stat?c=problem_statement&pm=12856

問題

2^K(K=0,1,2...)円の硬貨が2枚ずつある。
ここでN円の支払いをするときの硬貨の支払い方は何通りあるか答えよ。
同一金額の硬貨は同じものとみなす。

解法

上の価値の硬貨から順に0,1,2枚ずつ支払っていくメモ化再帰で良い。
この際、単純にメモ化再帰すると3倍3倍で状態が増えて発散するが、2^K円以下の硬貨で支払える金額はと2^K円の硬貨4枚分未満である。
よって、2^K円硬貨4枚で払えないような金額のケースはさっさとあきらめればよい。

そうすると各桁でメモ化再帰を続けないといけない状態はせいぜい4通り（(N%(2^K))、(N%(2^K))+1*(2^K)、(N%(2^K))+2*(2^K)、(N%(2^K))+3*(2^K)）なので状態はそんなに増えない。

class TaroCoins {
	public:
	
	map<pair<ll,int>,ll> M;
	ll dpdp(ll N,int bit) {
		
		if(N==0) return 1;
		if(N<0 || bit<0 || N>4LL<<bit) return 0;
		if(M.count(make_pair(N,bit))) return M[make_pair(N,bit)];
		return M[make_pair(N,bit)]=dpdp(N,bit-1)+dpdp(N-(1LL<<bit),bit-1)+dpdp(N-(2LL<<bit),bit-1);
	}
	
	long long getNumber(long long N) {
		M.clear();
		return dpdp(N,59);
	}
}

まとめ

Div2 Mediumよりあっさりかも。