WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #176 Div2 D "Shifting"

ACしてるソースコードをカンニング

こうやって素直に変換するんじゃなくて
f:id:Ekaing:20130324173531j:plain

こうすればええんちゃうんか!
f:id:Ekaing:20130324173618j:plain

こうすれば青線のとこだけ数値を変更すればよく、
f( p, k )における計算量は、pの長さをnとすると、
n / kとなる。

全体の計算量は?

nを最大の100万として
k = 2 の時は50万回
k = 3 の時は33万回
k = 4 の時は25万回
k = 5 の時は20万回
...

int main(){
    int n = 1000000;
    int cnt = 0;
    for( int k = 2; k <= n; k++ ){
        cnt += n / k + (n % k ? 1 : 0);
    }
    
    cout << cnt << endl;
}

f:id:Ekaing:20130324174241j:plain

( ^ V ^ )


ソースコード

int a[ 2000100 ];

int main(){
    int n;
    scanf( "%d", &n );
    
    // 初期の順列を作成
    for( int i = 1; i <= n; i++ ){
        a[i] = i;
    }

    // f(p, k) kを2~nまで試す
    for( int k = 2, shift = 1; k <= n; k++, shift++ ){
        // 割り切れない場合
        if( n % k ){
            a[n + shift] = a[n + shift - n % k];
        }
        // 後ろに下がるものだけ順次動かす
        for( int i = n / k; i >= 1; i-- ){
            a[k * i + shift] = a[k * (i - 1) + shift];
        }
    }

    // 出力
    for( int i = n; i < n + n; i++ ){
        printf( "%d ", a[i] );
    }
}