Codeforces Beta Round #13 E. Holes

Codeforces

これで#13との因縁を清算できる・・・。というわけで今度はE問題です。

問題

  • 1番からN番までの番号を持つ穴が一列に並んでて，各穴は正整数のpower[i]をもつ。
  • 穴iに玉を入れると，玉は列から出るまで，穴i+power[i]への移動を続けていく
  • このルール上で，以下の2通りからなるM個の処理を行う問題
    • 処理0 : 穴aのpowerをbに変更する
    • 処理1 : 穴aに玉を入れたとき，列から出るまでの移動回数と最後に入った穴を答える
  • NもMも最大10万


解法

  • O(NM)かけると死にますが，改善点も思い浮かばないので今回もEditorial参照
  • 穴をsqrt(N)個ごとのブロックに分けてやるというアイディア
  • 今回の実装ではブロックごとに分けてやった上で，
    • 別ブロックへの移動か，別ブロックに移動するブロックに移動するとき
      • そのブロックへの移動回数としてjump[i]を1とし，next[i]は移動先の番号に
    • それ以外のとき(2回先のブロック内に収まる)
      • jump[i] = jump[ i+power[i] ]+1とし，next[i]はブロックを出る穴に。
  • という処理をpower更新ごとに行っている
  • サイズBに区切ると，処理0がO(B)，処理1がO(N/B)になる
  • O(M*(B+N/B))を最小化するBがsqrt(N)というわけか・・・
  • 勉強になるなぁ・・・と思っていたところ，卒論で似た議論をやった事を思い出し，涙した
#include <iostream>
#include <cmath>

using namespace std;

int power[100000], next[100000], jump[100000];

void update(int block, int N, int sqN){
    int first = block*sqN;
    int last  = min(N, first+sqN)-1;
    for(int i=last;i>=first;i--){
        int nextIdx = i+power[i];
        if(nextIdx <= last && next[nextIdx] <= last){
            jump[i] = jump[nextIdx]+1;
            next[i] = next[nextIdx];
        } else {
            jump[i] = 1;
            next[i]  = nextIdx;
        }
    }
}

int main(){
    int N, M, sqN;
    while(cin >> N >> M){
        int sqN = (int)sqrt((double)N);
        for(int i=0;i<N;i++) cin >> power[i];
        for(int i=N/sqN;i>=0;i--) update(i, N, sqN);
        for(int i=0;i<M;i++){
            int type, a; cin >> type >> a;
            if(type == 0){
                cin >> power[a-1];
                update((a-1)/sqN, N, sqN);
            } else {
                int cur = a-1, cnt = 0;
                while(true){
                    cnt += jump[cur];
                    if(next[cur] < N) cur = next[cur];
                    else              break;
                }
                printf("%d %d\n", cur+1, cnt);
            }
        }
    }
}