AtCoder ABC #182 : F - Valid payments

典型っぽいのにちょっと悩んでしまった。
https://atcoder.jp/contests/abc182/tasks/abc182_f

問題

この国にはN種類のコインがある。
上位のコインは下位のコインの倍数の価値がある。

ここで、金額Xの商品を購入するためにYだけ支払い、Y-Xのお釣りを得るとする。
支払いとお釣りは最小枚数のコインでわたし、かつ支払いとお釣りで同種のコインが行き来しないようにする場合、あり得るYは何通りか。

解法

下のコインから順に金額を合わせていくことを考える。
f(i,Z) := i番目のコインZ枚分の商品を、i番目以降のコインだけで買うときの問題文の条件を満たす組み合わせ数
とする。0-indexで考えるとf(0,X)が求める解である。

• i=N-1、すなわち最上位のコインを考えるときは、支払い方はZ枚そのコインで払うの一択。
• i＜N-1の時、i枚目のコインの価値と(i+1)枚目のコインの価値の比率をpとする。
  • Z%p==0なら、i枚目のコインは支払いにもお釣りにも表れないのでf(i,Z) = f(i+1,Z/p)
  • Z%p＞0なら、i枚目のコインは支払いに使う場合とお釣りに使う場合を考えf(i,Z) = f(i+1,floor(Z/p))+f(i+1,ceil(Z/p))

あとはfをメモ化再帰でもすればよい。

int N;
ll A[51];
ll X;
ll ret;
map<ll,ll> memo[55];

ll dfs(int cur,ll lef) {
	if(cur==N-1) {
		return 1;
	}
	
	if(memo[cur].count(lef)) return memo[cur][lef];
	ll ret=0;
	
	ll step=A[cur+1]/A[cur];
	ll a=lef%step;
	
	if(a==0) {
		ret+=dfs(cur+1,lef/step);
	}
	else {
		ret+=dfs(cur+1,lef/step);
		ret+=dfs(cur+1,lef/step+1);
	}
	return memo[cur][lef]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X;
	FOR(i,N) cin>>A[i];
	
	cout<<dfs(0,X)<<endl;
}

まとめ

yukicoderでコイン支払い系の問題何度か見た気がするのに、時間をかけすぎた。