AOJ2182 Eleven Lover

問題リンク Eleven Lover

• 概要

'0'〜'9'の文字からなる文字列Sが与えられる。Sの連続部分文字列で、それが11の倍数で正の数であるものがいくつあるかを答えよ。ただし、0が先頭に続いているものはカウントしないこと。
以下のことが保証されている

S

<= 80000

答えは32bit signed integerにおさまる

• 解法

DPです。
ある整数が11の倍数かどうかは、左から1桁ずつ見れば分かります(過去に ここ で説明したことがあります)。
dp[i][j]: 左からi桁目までを考えたとき、MOD 11がjであるものの個数
という表を埋めれば解けます。dp[i][0]の総和が答えとなります。
i桁目の数字をxiとしたとき、dp[i][xi]が1増えると思いますが、0 leadings な数字はカウントしてはいけないので、xi==0のときに限り+1をスキップしないとダメです。

• ソース

import java.util.Arrays;
import java.util.Scanner;

//Eleven Lover
public class AOJ2182 {

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			char[] s = sc.next().toCharArray();
			if(s.length==1&&s[0]=='0')break;
			int[][] dp = new int[2][11];
			int x = 0, res = 0;
			for(int i=0;i<s.length;i++,x=1-x){
				int r = s[i]-'0';
				Arrays.fill(dp[x], 0);
				for(int j=0;j<11;j++){
					dp[x][(10*j+r)%11]+=dp[1-x][j];
				}
				if(r!=0)dp[x][r]++;
				res+=dp[x][0];
			}
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ2182().run();
	}
}