SRM 372 500pt: RoundOfEleven - komiyamの日記

問題概要

10桁以下の整数が与えられる。各桁の数字を1増やすか減らすのに1単位のコストがかかる。コストの総和が一定量以下となるようにして11の倍数をたくさん作りたい。このとき、Σ(初期コスト-必要なコスト)を求める問題。

考えたこと

10進数で11の倍数かどうかは偶数桁の和と奇数桁の和の差が11の倍数かどうかで判定できる。これは10≡-1 (mod 11)であることから簡単に示される。
なので偶数桁と奇数桁に分けて考えればよさげ。でもちょっと面倒くさいか？
偶数桁だけ集めたら、各桁の合計値も必要なコストも高々50以下なのでどうとでもなりそう。
一番素朴にやろうとしたら、dp[i番目まで見た][合計値][必要なコスト]=そういう場合の数、としてDPで行けそう。
書いた。投げた。通らない。
最後に偶数桁と奇数桁をマージするとき必要なコストの上限が50のままだった。二つの和だから100くらいにしなきゃダメだった。
無事通った。

practiceで通ったコード

#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = 55;
const int MAX_LOG = 7;

int result[2][MAX_LOG][MAX_N][MAX_N]; //(偶奇、合計値、総コスト)

struct RoundOfEleven {

	int64 maxIncome(int n, int money){
		//10未満のときは大丈夫？

		//偶数桁の数字と奇数桁の数字に分割する
		vector<int> odd, even;
		for(int i=0; n > 0; i++, n/=10){
			if(i&1){
				odd.push_back(n%10);
			}
			else{
				even.push_back(n%10);
			}
		}

		//偶奇でそれぞれ何通りできるか計算する
		func(odd, 0);
		func(even, 1);

		int64 ret = 0;
		for(int i=0; i<50; i++)for(int j=0; j<50; j++)if((i-j)%11 == 0){
			//kは使用した金額の合計
			for(int k=0; k<min(money, 100); k++){
				int64 income = money - k;
				for(int a=0; a<=k; a++)if(a<=50 && k-a<=50){
					ret += income * result[0][odd.size()][i][a]*result[1][even.size()][j][k-a];
				}
			}
		}

		return ret;
	}

	void func(const vector<int>& nums, const int sign){
		const int N = nums.size();
		int (*dp)[MAX_N][MAX_N] = result[sign];
		dp[0][0][0] = 1;

		for(int i=0; i<N; i++){
			for(int cur=0; cur<50; cur++){ //合計値の上限は5*9=45
				for(int cost=0; cost<50; cost++)if(dp[i][cur][cost]!=0){ //総コストの上限も5*9=45

					for(int k=0; k<=9; k++){ //iつめの数字を何に置き換えるか
						int add = abs(nums[i] - k);
						if(cur+k < 50 && cost + add < 50){
							dp[i+1][cur+k][cost+add] += dp[i][cur][cost];
						}
					}
				}
			}
		}

	}


};

別の解き方1

DPとかしなくても偶数桁(奇数桁)だけ取り出したら作れる数はたかだか10^5しかないのだから全て列挙できる。この方法は半分全列挙と言われるアレ。ただし今回の場合は計算量は落ちる。

	void func2(const vector<int>& nums, int array[MAX_N][MAX_N]){
		const int N = nums.size();

		//つくることのできる数の上界を求める
		int max_d = 1;
		for(int i=0; i<N; i++){
			max_d *= 10;
		}

		//つくることのできる数を総当たりで試す
		for(int i=0; i<max_d; i++){

			//桁に現れる数を集める
			vector<int> digs;
			for(int d=i, k=0; k<N; k++, d/=10){
				digs.push_back(d%10);
			}

			//その数を作るためのコストとかを求める
			int cost = 0, sum = accumulate(digs.begin(), digs.end(), 0);
			for(int k=0; k<N; k++){
				cost += abs(digs[k]-nums[k]);
			}

			array[sum][cost]++;
		}
	}

別の解き方2

基本的には最初に書いたコードと大差ない。DPで、偶数と奇数に分ける必要はなく、奇数桁のときはマイナスの符号をつけてやれば良い。
あと、実装上の工夫として、配列の一部をポインタで置き換えるようなことをしてindexに負の数突っ込めるようにしたけど、このときうっかりmemsetでの初期化を間違えてしまった。これは注意しないとハマりそう。

int dp[2][102][102];

	int64 maxIncome(int n, int money){

		//桁に現れる数字を集める
		vector<int> nums;
		for(int m=n; m; m/=10){
			nums.push_back(m%10);
		}
		const int N = nums.size();

		//配列を使いまわしてDP
		int (*cur)[102] = dp[0]+51, (*next)[102] = dp[1]+51;
		cur[0][0] = 1;
		for(int i=0; i<N; i++){
			for(int sum=-45; sum<=45; sum++){
				for(int cost=0; cost<=100; cost++)if(cur[sum][cost] > 0){
					for(int k=0; k<=9; k++){
						int add_cost = abs(nums[i] - k);
						int add_num = ((i&1)?k:-k);
						next[sum+add_num][cost+add_cost] += cur[sum][cost];
					}
				}
			}
			swap(cur,next);
			memset(next-51, 0, sizeof(dp[0])); //初期化の仕方に注意!!
		}

		int64 ret = 0;
		for(int sum=-45; sum<=45; sum++)if(sum%11 == 0){
			for(int cost=0; cost<= min(100, money); cost++){
				ret += (int64)(money - cost) * cur[sum][cost];
			}
		}

		return ret;
	}
};