yukicoder : No.158 奇妙なお使い

状態が膨らむ無駄解法を繰り返して手間取った。
http://yukicoder.me/problems/125

問題

初期状態でA君が持つ1000円札・100円玉・1円玉の数が与えられる。

BさんのところでDb円ちょうど払うと、(総額Db円以下の)B(1000)枚の1000円札・B(100)枚の100円玉・B(1)枚の1円玉がおつりとして得られる。
CさんのところでDc円ちょうど払うと、(総額Dc円以下の)C(1000)枚の1000円札・C(100)枚の100円玉・C(1)枚の1円玉がおつりとして得られる。

お金を払う行為は最大何回行えるか。

解法

お金を払うと所持金は常に減少するので、お金が大きい順に状態を総当たりしていけば良い。
同じ金額を持っているなら細かい硬貨を持っている方が融通が利くので、大きな紙幣・硬貨から使うようにすればよい。

int A[3],B[2][3];
int D[2];
int ma;
typedef tuple<int,int,int> S;
set<S> V[10001];
map<S,int> M;

int val(S v){ return get<0>(v)*1000+get<1>(v)*100+get<2>(v);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A[0]>>A[1]>>A[2];
	FOR(i,2) cin>>D[i]>>B[i][0]>>B[i][1]>>B[i][2];
	
	S f = tie(A[0],A[1],A[2]);
	M[f]=0;
	V[val(f)].insert(f);
	
	for(i=10000;i>=0;i--) {
		ITR(it,V[i]) {
			ma=max(ma,M[*it]);
			FOR(j,2) {
				S k=*it;
				
				x=D[j];
				r=min(x/1000,get<0>(k)); x -= r*1000; get<0>(k)-=r;
				r=min(x/100,get<1>(k));  x -= r*100 ; get<1>(k)-=r;
				r=min(x,get<2>(k));      x -= r;      get<2>(k)-=r;
				if(x==0) {
					get<0>(k) += B[j][0];
					get<1>(k) += B[j][1];
					get<2>(k) += B[j][2];
					M[k]=max(M[k],M[*it]+1);
					V[val(k)].insert(k);
				}
			}
		}
	}
	
	cout<<ma<<endl;
}

まとめ

最初pairのpairを使ってたらコードがややこしくなったのでtupleで書き直した。