POJ-2886 : Who Gets the Most Candies?

問題概要

n(<5*10^5)人の子供が円上に並んでいる。k番目の子供からスタートして、その子を取り除く。この際p番目に取り除くのならpの約数の個数だけ飴を渡す。次はA[k]だけ進んだ所にいる子供をターゲットにする。誰がもっとも多く飴を貰えるか判定する問題。

解法

約数の個数については前処理で篩っぽく計算できる。どの子が取り除かれるかについてはBITで計算する(割と典型手法)。

acceptされたコード

const int MAX_N = int(5e5);

int N, K;
int as[MAX_N];
char names[MAX_N][11];
int F[MAX_N + 1];

void calcF(int n) {
	fill(F, F + n + 1, 1);
	for (int i = 2; i <= n; ++i) if (F[i] == 1) {
		for (int j = i; j <= n; j += i) {
			int k = 0;
			for (int m = j; m % i == 0; m /= i, ++k) ;
			F[j] *= k + 1;
		}
	}
}

void init() {
	scanf("%d%d", &N, &K);
	--K;
	for (int i = 0; i < N; ++i) {
		scanf(" %s %d", names[i], as+i);
	}
}

void solve() {
	calcF(N);
	BinaryIndexedTree bitree;
	bitree.init(N);
	for (int i = 0; i < N; ++i) {
		bitree.add(i, 1);
	}

	int maxi = -1, key = -1;
	for (int i = 0; i < N; ++i) {
		if (updateMax(maxi, F[i+1])) {
			key = K;
		}
		bitree.add(K, -1);
		if (i < N - 1) {
			const int res = N - 1 - i;
			int id = bitree.getSum(K) + as[K] + (as[K] > 0 ? -1 : 0);
			id = (id % res  + res) % res;
			K = bitree.getOverSumIndex(id);
		}
	}

	printf("%s %d\n", names[key], maxi);
}

int main() {
	init();
	solve();
	return 0;
}