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; }