yukicoder : No.286 Modulo Discount Store

放送で「３問目の方が簡単かも…」と言ってくれたおかげで、他の人がそっちに流れて２問目でFA取れた。
http://yukicoder.me/problems/528

問題

N個の商品があり、それぞれ定価はM[i]円である。
各商品を１個ずつ任意の順で買いたい。

各商品を買う際、(それまで買った商品の合計金額 mod 1000)の分の金額だけ値引きしてくれる。
ただし商品の価格はマイナスにはならない。

全商品を１個ずつ買うまでの最小金額はいくらか。

解法

Nが小さいので、購入済みかどうかでBitDPしていけば良い。

int N;
int M[20];
int dp[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>M[i];
	FOR(i,1<<N) dp[i]=1<<20;
	
	dp[0]=0;
	for(int mask=0;mask<(1<<N)-1;mask++) {
		int tot=0;
		FOR(i,N) if(mask&(1<<i)) tot+=M[i];
		tot %= 1000;
		FOR(i,N) if((mask&(1<<i))==0) dp[mask | (1<<i)] = min(dp[mask | (1<<i)],dp[mask]+max(0,M[i]-tot));
	}
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

この店は、定価の合計金額が1000円未満であれば、最初に購入した商品分だけお金を払えばよいのか。
えらい太っ腹な店だ。