読者です 読者をやめる 読者になる 読者になる

JOI2011-2012予選 問6 ジグザグ数 (Zig-Zag Numbers)のソース

さすがに遅いので書き足した。たしかに500倍くらい速くなった。与えられるAをジグザグ数か判定することによって多倍長回避。60行くらいでシンプル(ただそれでもreading-hard)

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

int M;
int memo[512][16][512][4][2];
string limit;

int f(int pos , int digit , int mod , int up , int free){
	if(pos == -1) return (mod == 0);
	if(memo[pos][digit][mod][up][free] != -1) return memo[pos][digit][mod][up][free];
	int ans = 0;
	if(up != 2){
		if(up){
			for(int i = digit+1 ; i <= (free?9:limit[pos]) ; i++){
				ans += f(pos-1,i,(mod*10+i)%M,up^1,free||(i < limit[pos]));
			}
		}else{
			for(int i = (free?digit-1:min((int)limit[pos],digit-1)) ; i >= 0 ; i--){
				ans += f(pos-1,i,(mod*10+i)%M,up^1,free||(i < limit[pos]));
			}
		}
	}else{ // leading-zero
		ans += f(pos-1,0,(mod*10+0)%M,2,free||(0 < limit[pos])); // <- keep zeroflag.
		for(int i = 1 ; i <= (free?9:limit[pos]) ; i++){
			ans += f(pos-1,i,(mod*10+i)%M,0,free||(i < limit[pos]));
			if(pos != 0) ans += f(pos-1,i,(mod*10+i)%M,1,free||(i < limit[pos]));
		}
	}
	ans %= 10000;
	return memo[pos][digit][mod][up][free] = ans;
}

int solve(string n){
	memset(memo,-1,sizeof(memo));
	limit = "0" + n;
	reverse(limit.begin(),limit.end());
	for(int i = 0 ; i < limit.size() ; i++) limit[i] -= '0';
	return f(limit.size()-1,0,0,2,0) - 1;
}

int zig(string s){
	if(s.size() == 1) return true;
	if(s[0] == s[1]) return false;
	if(s.size() == 2) return s[0] != s[1];
	int up = s[0] > s[1];
	for(int i = 2 ; i < s.size() ; i ++){
		if( s[i-1] == s[i] || (up && s[i-1] >= s[i]) || (!up && s[i-1] <= s[i]) ) return false;
		up^=1;
	}
	return true;
}

int main(){
	string A,B;
	cin >> A >> B >> M;
	
	cout << ( solve(B) - solve(A) + zig(A) + 100000) % 10000 << endl;
}

実行時間と結果 (g++ -O2オプションでコンパイル)

$ g++ y6.cpp -O2
$ ./a.exe < ./2012-yo-t6-in1.txt
5511

real    0m0.189s
user    0m0.093s
sys     0m0.077s
$ ./a.exe < ./2012-yo-t6-in2.txt
4165

real    0m0.171s
user    0m0.108s
sys     0m0.062s
$ ./a.exe < ./2012-yo-t6-in3.txt
8033

real    0m1.219s
user    0m1.140s
sys     0m0.108s
$ ./a.exe < ./2012-yo-t6-in4.txt
1536

real    0m0.561s
user    0m0.531s
sys     0m0.046s
$ ./a.exe < ./2012-yo-t6-in5.txt
9492

real    0m0.685s
user    0m0.546s
sys     0m0.108s

まあAOJは通りそうな感じ。