Avendia20

日記 (2018 年 3 月 4 日)

ABC089 に出てきました。 結果は、 4 問正解 1000 点で 1159 人中 331 位でした。 レートは 948 (緑) に微増しました。

さて、 ABC089 の D 問題についてまとめましょう。 問題はこちらです。 魔法少女になります。

愚直にやると、 i 回目の実技試験において、 特定の数字が書かれているマスの検索を (Ri−Li)/D 回行う必要があります。 検索も何も工夫しなければ O(HW) かかり、 検索回数も最大で O(HW) です。 この操作を Q 回やるので、 全体の計算量は最大で O(H2W2Q) です。 なんか無理そうです。

そこで A をそのまま保持するのではなく、 各数に対してそれが書かれるマスの座標を保持するようにしましょう。 このようにすることで検索の手間が省けるので、 計算量が O(HWQ) になります。 これでもまだ微妙に遅く、 実際 TLE します。 ということで、 さらなる高速化をする必要があります。

x が書かれているマスから x+D が書かれているマスに駒を動かすのに必要な魔力を M(x) とおくと、 i 回目の実技試験で消費する魔力は、 M(Li)+M(Li+D)+M(Li+2D)+⋯+M(Ri−D) で求まります。 ここで、 各 x に対して mx=x%D とおき、 Macc(x)=M(m)+M(m+D)+M(m+2D)+⋯+M(x−D) と定めれば、 先程の消費魔力は Macc(Ri)−Macc(Li) と書けます。 したがって、 Macc(x) をあらかじめ計算しておけば、 各実技試験での消費魔力は O(1) で求めることができます。 Macc(x) の計算は O(HW) でできるので、 全体の計算量は O(HW+Q) となり、 高速化できました。

このように、 特定の和を何度も計算するような場合は、 適当な始点から累積した和をあらかじめ計算しておくことで、 その累積和の差を計算するだけで求めたい部分和を計算することができます。

ということで、 全てのテストケースに通るプログラムが以下のような感じです。

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 分を無に帰しました。 つらいです。