CodeChef-CIEL8STR : Ciel and New Menu

問題概要

0~9の並んだ列が与えられる(長さN<10^6)。leading zeroでない部分文字列のうち、8の倍数がいくつあるか(重複あり)を数える問題。

解法

1,2,3桁はそれぞれ真面目にやる。4桁以上のは、下3桁が8の倍数であればよいので、下3桁を全部試してそれ以上は非ゼロな要素の個数だけ足してやればよい。

#include <cstdio>
#include <cstring>
using namespace std;

typedef long long int64;

const int MAX_L = 1e6;

char buf[MAX_L + 1];
int non_zero_accum[MAX_L + 1];

int64 solve(){
	int64 ans = 0;
	const int N = strlen(buf);

	//１けた
	for(int i=0; i<N; i++){
		if(buf[i] == '0' || buf[i] == '8'){
			ans++;
		}
	}

	//２けた
	for(int i=0; i+1<N; i++)if(buf[i]!='0'){
		int test = (buf[i]&15)*10 + (buf[i+1]&15);
		if(test%8 == 0){
			ans++;
		}
	}

	//３けた
	for(int i=0; i+2<N; i++)if(buf[i]!='0'){
		int test = (buf[i]&15)*100 + (buf[i+1]&15)*10 + (buf[i+2]&15);
		if(test%8 == 0){
			ans++;
		}
	}

	//３けた以上
	for(int i=0; i<N; i++){
		non_zero_accum[i+1] = non_zero_accum[i] + (buf[i]=='0' ? 0 : 1);
	}

	for(int i=1; i+2<N; i++){
		int test = (buf[i]&15)*100 + (buf[i+1]&15)*10 + (buf[i+2]&15);
		if(test % 8 == 0){
			ans += non_zero_accum[i];
		}
	}

	return ans;
}

int main(){
	scanf("%[^\n]%*c", buf);
	printf("%lld\n", solve());

	return 0;
}