Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-17SRM371, SRM372 (Practice)

SRM 372 RoundOfEleven

|  SRM 372 RoundOfEleven - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 372 RoundOfEleven - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8005

  • どの桁をいくつ動かすか選択しながらDPする
    • k(0-indexed)桁目でx数字を増やすと、mod 11が (10^k*x) % 11 ずれる
    • あらかじめ (10^k) % 11 の値を求めておけば計算の手間が減らせそうだ
  • 状態は dp[桁数][残り使えるお金][mod11]
import java.util.Arrays;

public class RoundOfEleven {
	
	
	int len;
	String strn;
	long[][][] memo;
	int[] pow11;
	
	public long dfs(int digits, int leftmoney, int mod) {
		if (leftmoney < 0) {
			return 0;
		}
		if (digits == len) {
			if (mod == 0) {
				return leftmoney;
			}
			return 0;
		}
		if (memo[digits][leftmoney][mod] >= 0) {
			return memo[digits][leftmoney][mod];
		}
		
		
		long total = 0;
		int digit = strn.charAt(len-digits-1) - '0';
		for (int i = 0 ; i <= 9 ; i++) {
			int change = Math.abs(digit - i);
			int tomod = (mod + (pow11[digits] * (i - digit) + 1100)) % 11;
			total += dfs(digits+1, leftmoney-change, tomod);
		}
		memo[digits][leftmoney][mod] = total;
		
		return total;
	}

	public long maxIncome(int n, int money) {
		memo = new long[100][501][12];
		pow11 = new int[100];
		pow11[0] = 1;
		for (int i = 1 ; i < 100 ; i++) {
			pow11[i] = (pow11[i-1] * 10) % 11;
		}
		
		
		for (int i = 0 ; i < 100 ; i++) {
			for (int j = 0 ; j < 501 ; j++) {
				Arrays.fill(memo[i][j], -1);
			}
		}
		strn = String.valueOf(n);
		len = strn.length();
		
		return dfs(0, money, n % 11);
	}
}