atcoder ABC106

Cは簡単な発想で解ける問題であり、D問題は左と右の場所について二次元配列で持つという発想に至らなかった。やはり条件で駅の数が500*500しかないことに気づいて利用するという流れが大事である。
https://atcoder.jp/contests/abc106

C問題

1は1、2は22のように1年後iがi乗増えて行くので、10兆年後K番目の数字は何か答える問題。明らかに一番左の数が1以外ならk番目の数はその数になるので、一番左が1だった時の場合を考える。この場合、K番目まで全部1なら10兆年後もK番目は1であるが一つでも1以外の数字があればその数字がk番目になる。よって、k番目までについて1かどうか判定することで答えが導ける。

D問題

明らかに、各クエリに対し全探索していてはTLEになってしまう。なので、各線のLとRを二次元配列として持っておき累積和をとることで答えを時間以内に出すことができる。ここで、累積和について2つの方法がある。

一般的な累積和

数列a[] = {1,2,3,4,5}
が与えられた時、以下のようにすることで、i番目までの数値の和を求めることができる

int[]a ={1,2,3,4,5};
int[] sum = new int[5] 
for(int i = 1;i <= 4;i++){
    sum[i] = sum[i-1]+a[i-1];   
}

結果

1 3 6 10 15

累積和を用いることで、x番目からy番目までの和をO(1)で求められる。

int x = 2;
int y = 4;
sum[y]-sum[x];

結果

9

二次元累積和

今回の問題では使わなくてもACできるが、実用的なテクニックである。まず二次元累積和の概要としては、累積和S_ijは0からi,jまでにあるaの和を表す。詳しい導出は参考urlを見て欲しいが、大事なことは、この累積和の作成の手順である。これは以下のように実装できる。

int[][] a = new int[5][5];
int[][] sum = new int[6][6];
for(int i = 1;i <= 5;i++){
   for(int j = 1;j <= 5;j++){
      s[i][j] = a[i-1][j-1] + s[i-1][j]+s[i][j-1]+s[i-1][j-1]
    }
}

#参考url
https://tqk.hatenablog.jp/entry/ABC106-2