Submission #1005252

---

Source Code Expand

//高橋君は10^k円玉を10枚以上持つ必要がない -> {1円玉10枚で払える金額集合 < 1円玉9枚, 10円玉1枚で払える金額集合}
//高橋君は「同じ種類の硬貨」を9枚までしか持つことができない！としても, 硬貨の枚数の最小性は失われない。
//
//すると、商品{A_{p1}, A_{p2}, …, A_{pk}}を買った時に払う「10^k円玉の枚数」も確定する。（(合計金額 / 10^k) % 10)
//商品集合の組み合わせ2^n通りにおいて, 10^k円玉を7枚払う場合はあるが8枚払う場合がないとき、10^k円玉は7枚持っていく
//のが最適になる。（7枚は持ってく必要があるが, 8枚持って行っても8枚目は絶対に使わないため）
//
//したがって、「(部分和 / 10^k) % 10」の最大値f(k)を各kについて求め、それを合計したものが「答え」となる。
//
//（注：ここで早とちりして、f(k)は「k桁目の和 mod 10のMax」と思ってはいけない。
// 例えば、N = 2, {15, 16}では、{1円玉6枚, 10円玉2枚}ではなくて、{1円玉6枚, 10円玉3枚}が必要になる。
//（注：ここで焦って, f(k)は「(k桁目の和 + ((商品価格 % 10^k)のN個和) / 10^k) mod 10のMax」と思ってはいけない。
// 例えば, N = 2, {55, 45}では、{1円玉5枚, 10円玉6枚, 100円玉1枚」もいらなくて、{1円玉5枚, 10円玉5枚, 100円玉1枚}
//が必要になる。
//
//というわけで、f(k)は簡単な桁DPでは求まらないのであった。がーん。
//
//(ここまでは発想よりも、考えたこと（とか問題文）を整理する力が求められている気がする）
//(N <= 20解法は、冷静に考えて、サンプルから察することができた）

#include <iostream>
#define int long long
using namespace std;

int n;
int a[25];
int power[17];

signed main() {
	int i, j;
	
	power[0] = 1;
	for (i = 1; i < 17; i++) { power[i] = power[i-1] * 10; }
	
	cin >> n;
	for (i = 0; i < n; i++) { cin >> a[i]; }
	
	int ans[17] = {0};
	
	for (i = 0; i < (1 << n); i++) {
		int ssum = 0;
		for (j = 0; j < n; j++) {
			if ((i >> j) & 1) {
				ssum += a[j];
			}
		}
		
		for (j = 0; j < 17; j++) {
			ans[j] = max(ans[j], (ssum / power[j]) % 10);
		}
	}
	
	int _ans = 0;
	for (i = 0; i < 17; i++) { _ans += ans[i]; }
	cout << _ans << endl;
	return 0;
}

Submission Info

Judge Result