Codeforces #229 Div2. C. Inna and Candy Boxes

Codeforces #229に参加。Div2回なのでリラックスしてチャレンジ。
綺麗に５問で５回WA出してしまったが、最終的には全問正解、初めて20位と1ページ目に入った。
http://codeforces.com/contest/390/problem/C

問題

1～Nの箱が１列に並んでおり、それぞれの箱には１個飴が入っているか、もしくは飴が入っていない。
ここで数Kが与えられたとき、以下のクエリに答えよ。
なお、クエリの度に飴は初期状態に戻る。

• 数L,Rが与えられるとき、L+K-1、L+2K-1、L+3K-1、…、Rの箱だけ飴が入っていて、他のL～Rの間の箱には飴が入っているようにしたい。取り除くまたは追加すべき飴の数を答えよ。
  • なお、L～Rの区間はKの倍数であり、(R-L+1)はKで割り切れる。

解法

L～Rの箱は以下の２種類に分けられる。

1. 飴を追加しないといけないのは、L+K-1、L+2K-1、L+3K-1、…、Rのうち飴のない箱である。
2. 飴を取り除かないといけないのはL～Rのうち上記を除いた箱である。

上記２値の合計が各クエリに対する回答である。
よってこの２値を高速に求めるデータ構造を考えればよい。

まず、L～Rの間の飴の数を高速に数えるため飴の数の部分和を取っておく。
次に、、L+K-1、L+2K-1、L+3K-1、…、Rの間の飴の数を高速に数えるため、箱番号iに対してi%Kでグループ分けし、それぞれの部分和を取っておく。

クエリに対し、後者の部分和から種類１の飴の数がわかり、さらに前者の部分和との差を取れば種類２の飴の数がわかる。

int N,K,W,L;
string S;
int sum[10][100010];
int sum2[100010];

void solve() {
	int f,i,j,k,l,x,y;

	cin>>N>>K>>W;
	cin>>S;
	L=S.size();
	FOR(i,L) {
		sum[i%K][1+i/K] = sum[i%K][i/K] + (S[i]=='1');
		sum2[i+1] = sum2[i] + (S[i]=='1');
	}
	
	FOR(i,W) {
		cin>>x>>y;
		x--;y--;
		int numc=sum2[y+1]-sum2[x];
		int tc = sum[y%K][1+y/K]-sum[y%K][(x+K-1)/K];
		int lc = numc-tc;
		_P("%d\n",lc + (y-x+1)/K - tc);
	}
}

まとめ

さっくり解けたのはいいけど、本番配列の添え字を微妙に間違えて1WAしてしまった。