Submission #1005441

---

Source Code Expand

//・「高橋君は同じ種類の硬貨を9枚までしか持てない」としても最適性を失わない。
//
//f(k) = {({A}の部分和 / (10^k)) % 10}の最大値, とするとΣf(k)が答え。
//(注意：X / (10^k)が分かってても, (X+Y) / (10^k)は分からないので、{({A}の部分和 / (10^k)) % 10}自体を持って探索するのは無理そう。）

//例えば、8 * 10^k <= {A}の部分和 % (10^(k+1)) < 9 * 10^kを満たす{A}の部分和が存在するなら「10^k円玉を8枚使う場合」が存在する。
//例えば、1000円玉を8枚使う場合、支払う金額は「*8???円」となっている。(金額→枚数, ではなく, 枚数→金額を考えるのがミソ）
//
//よって, 各整数1 <= k < 17, 0 <= d < 10について、{A}の部分和 % (10^(k+1))を、10^k * d以上 10^k * (d + 1)未満にできるか「高速に」判定できればよい。
//(その判定結果をis_ok(k, d)とおくと、f(k) = is_ok(k, d)がtrueになるdの最大値, だから）
//
//これを解くには、dp[番号][今までの和]というDPがヒントになるが、これでは解けないので、逆算を考える。
//
//実は
//{X_1,…,X_N}の部分和を[L, R)にできる⇔{X2,…,X_N}の部分和を[L, R) or [L - X1, R - X1)にできる, が成り立ち, これを今回の問題で使うなら
//{X_1,…,X_N}の部分和(mod M)を[L, R)にできる ⇔ {X2,…,X_N}の部分和(mod M)を[L, R) or [(L - X1) mod M, (R - X1) mod M)にできる
//
//今回は[L, R)がM / 10以上なので、dp[i][j] = {{A_i, …, A_N}の部分和がjになればOKな状態} (trueならそうなってて, falseならそうなってない)
//とおくと、dp[i][j] = trueとなるjは、10個以下の「互いに重ならない」区間で表すことができる。
//
//例えば、部分和を{8000～9999}にすればOKな場合を考える。
//値500を選んだら、残り部分和  = {7500 ～ 9499}にすればよく, 無視すれば、残り要素和 = {8000～9999}にすればよくなる。
//つまり、値500の(取る, 取らない)を決めたときに、残り部分和は{7500～9999}の範囲に収めればよい。
//値2530を選んだら、残り部分和 = 5470 ～ 7469にすればよく、無視すれば = {8000～9999}…
//結局、残り部分和 を「5470～7469, 8000～9999」の範囲に収めればよい。
//
//オートマトンの同形判定とか知ってるとこういうDPは立てやすいし、DPを立てる前後の話は素朴。
//「なんでこういう式を立てたのか？」, 「もう一つ方針があるけど、どっちが良さそう？ (同値な3つの条件から1つを選んで解くあれ）」を考えるだけで解ける。
//(思い込みはよくないということが分かる良問）(chokudai（敬称略）は天才）
//でも実装きつかったw

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

int n;
int a[20000];
int power[18];

bool is_ok(int k, int d) {
	static int low[20001][15];
	static int high[20001][15];
	static int seg_cnt[20001];
	static int b[20000];
	int i, j;
	
	for (i = 0; i < n; i++) { b[i] = a[i] % power[k + 1]; }
	for (i = 0; i < n; i++) { b[i] = power[k + 1] - b[i]; }
	
	low[0][0] = d * power[k];
	high[0][0] = (d + 1) * power[k] - 1;
	seg_cnt[0] = 1;
	
	//cout << "k = " << k << " " << " d = " << d << endl;
	
	for (i = 0; i < n; i++) {
		static int nlow[30], nhigh[30];
		
		for (j = 0; j < seg_cnt[i]; j++) {
			int p = (low[i][j] + b[i]) % power[k + 1];
			int q = (high[i][j] + b[i]) % power[k + 1];
			
			if (p > q || p == 0 || q == 0) {
				return true;
			}
			
			else {
				nlow[2 * j]      = p;
				nhigh[2 * j]     = q;
			}
			
			nlow[2 * j + 1]  = low[i][j];
			nhigh[2 * j + 1] = high[i][j];
		}
		
		//2 * seg_cnt個の（同じ長さの）閉区間をマージする
		static pair<int, int> seg[30];
		for (j = 0; j < seg_cnt[i] * 2; j++) { seg[j] = pair<int, int>(nlow[j], nhigh[j]); }
		sort(seg, seg + seg_cnt[i] * 2);
		
		int id = 0;
		seg_cnt[i + 1] = 0;

		for (j = 0; j < seg_cnt[i] * 2; j++) {
			//cout << "seg ; " << seg[j].first << " " << seg[j].second << ", ";
			if (seg[j].first - seg[id].second >= 2) {
				low[i + 1][seg_cnt[i + 1]] = seg[id].first;
				high[i + 1][seg_cnt[i + 1]] = seg[j-1].second;
				seg_cnt[i + 1]++;
				id = j;
			}
		}
		//cout << endl;
		low[i + 1][seg_cnt[i + 1]] = seg[id].first;
		high[i + 1][seg_cnt[i + 1]] = seg[j-1].second;
		seg_cnt[i + 1]++;
	}
	
	/*for (i = 0; i <= n; i++) {
		for (j = 0; j < seg_cnt[i]; j++) {
			cout << "[" << low[i][j] << ", " << high[i][j] << "]";
			if (j + 1 < seg_cnt[i]) { cout << " or "; }
		}
		cout << endl;
	}*/
		
	for (i = 0; i < seg_cnt[n]; i++) {
		if (low[n][i] <= 0 && 0 <= high[n][i]) {
			return true;
		}
	}
	return false;
}

signed main() {
	power[0] = 1;
	for (int i = 1; i < 18; i++) { power[i] = power[i - 1] * 10; }
	
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> a[i]; }
	
	int ans = 0;
	for (int i = 0; i < 17; i++) {
		for (int d = 9; d >= 1; d--) {
			if (is_ok(i, d)) {
				ans += d;
				break;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result