日記 (2018 年 3 月 4 日)
ABC089 に出てきました。 結果は、 4 問正解 1000 点で 1159 人中 331 位でした。 レートは 948 (緑) に微増しました。
さて、 ABC089 の D 問題についてまとめましょう。 問題はこちらです。 魔法少女になります。
愚直にやると、
そこで
このように、 特定の和を何度も計算するような場合は、 適当な始点から累積した和をあらかじめ計算しておくことで、 その累積和の差を計算するだけで求めたい部分和を計算することができます。
ということで、 全てのテストケースに通るプログラムが以下のような感じです。
public void run() {
BetterScanner scanner = new BetterScanner(System.in);
int h = scanner.nextInt();
int w = scanner.nextInt();
int d = scanner.nextInt();
// 各数に対してそれが書かれる座標を保持
int[][] poss = new int[2][h * w];
for (int i = 0 ; i < h ; i ++) {
for (int j = 0 ; j < w ; j ++) {
int num = scanner.nextInt() - 1;
poss[0][num] = i;
poss[1][num] = j;
}
}
// 累積和を計算
long[] accs = new long[h * w];
for (int k = 0 ; k < d ; k ++) {
long acc = 0;
for (int num = k + d ; num < h * w ; num += d) {
int diffX = poss[0][num - d] - poss[0][num];
int diffY = poss[1][num - d] - poss[1][num];
if (diffX < 0) {
diffX = -diffX;
}
if (diffY < 0) {
diffY = -diffY;
}
acc += diffX + diffY;
accs[num] = acc;
}
}
int q = scanner.nextInt();
StringBuilder output = new StringBuilder();
for (int k = 0 ; k < q ; k ++) {
int l = scanner.nextInt() - 1;
int r = scanner.nextInt() - 1;
long result = accs[r] - accs[l];
output.append(result).append("\n");
}
System.out.println(output.toString());
}
ちなみに本番では、 最初の 2 重ループの順番を逆にしていて、 実時間とペナルティ合わせて 45 分を無に帰しました。 つらいです。