競技プログラミング 知識集積所

ABC476 F - Chebyshev Cafe

チェス盤喫茶

問題ページ解答例別解

考え方

各マスの人口に規則性があるように見えて、$\bmod$ 計算が入るせいで有効な規則はない。
こんな指定になっているのは、ただ入力を軽量化するためなのだと思われる。
そのため、各マスの人口を愚直に求めてからスタート。

まず、計算量が多少遅くてもいい前提で考えると、これは以下のように $O(N^4)$ で解ける。

あるマス $(i,j)$ に $C$ 人いたとする。
この人たちが各マスのカフェに行くコストの寄与は、$N^2-1$ 回で配りきれる。
これを $N^2$ 回行う。

これは、二次元imos法を用いることで、$O(N^3)$ に高速化される。
すなわち、コストの寄与を配る計算を、以下のように高速化する。

ただし、実際にはマスの座標は $0$ から $N-1$ までしかない。
そのため、負の数の座標は $0$ と読み替えて、$N$ 以上の座標が含まれるものは無視する。

これで $O(N^3)$ になったが、これでもまだ間に合わない。
そこで、累積和を用いてさらに高速化する。

同じ斜め列上にある値は、今のところ $O(N)$ 個の値を $O(N)$ ヶ所に愚直に配っている。
しかし、各値からの寄与範囲をうまく考えれば、斜め方向の累積和を用いて $O(N)$ で処理できる。
＼向きと／向き、どちらも $O(N)$ の処理を $O(N)$ 回なので、全体計算量は $O(N^2)$。
これで間に合う。

そこから先は、問題の指定通りに $\mathrm{XOR}$ を求めていくだけ。
ここも計算量は $O(N^2)$ なので、全体計算量は $O(N^2)$。

考え方は単純だが、実装が大変なので、ここまでわかってようやく道のりの $2$ 割という感じである。
残り $8$ 割の実装力勝負。

入力例1での動作

入力を受け取る。

n: 4
m: 19
a: {2, 3, 1, 1}
b: {3, 4, 4, 10}

各マスの人口を求めると、次のようになる。

{6, 8, 8, 1}
{9, 12, 12, 11}
{3, 4, 4, 10}
{3, 4, 4, 10}

各人口からの寄与を、＼向き・／向きの斜めごとにまとめて差分配列へ加算する。
すべてのマスについて加算し終わった時点の差分配列は、次のようになる。

{220, -44,   3,  45}
{-21, -15,  -7,   1}
{ 13,   6, -12, -11}
{ 43,  13,   2, -18}

これに横方向、縦方向の順で累積和を取ると、各カフェへ集まる場合の交通費合計 $f(i,j)$ が得られる。

f:
  {220, 176, 179, 224}
  {199, 140, 136, 182}
  {212, 159, 143, 178}
  {255, 215, 201, 218}

実装では 0-indexed なので、各マスについて f[i][j]+i*n+j を求めると次のようになる。

  {220, 177, 181, 227}
  {203, 145, 142, 189}
  {220, 168, 153, 189}
  {267, 228, 215, 233}

これらすべての XOR を取ると、答えは $467$ となる。

注意点

$(0,0)$ を通る＼向きの処理に注意。
＼向きの処理をするとき、$(0,0)$ への寄与として両座標が $0$ 以下である分の合計をする。
このとき、普通に $(0,0)$ に反映させたい値まで巻き込まれてしまう。
うっかり $(0,0)$ 分を $2$ 重に計上しないように気を付けなければならない。

$f(i,j)$ や途中計算の値は、int 型からはみ出る。
long long 型を用いること。

別解

値を配るのではなく、もらう方針で考えると別の解き方もできる。（公式解説のsounannsyaさん解）

まず、$2\times\max(|a|,|b|) = |a+b|+|a-b|$ という公式を用いて、式から $\max$ を消す。
つまり、交通費の $2$ 倍は、$|s_r+s_c-t_r-t_c|+|s_r-s_c-t_r+t_c|$ である。

$(t_r,t_c)$ を決めたときに、全 $(s_r,s_c)$ からの寄与を合計したい。
これを、前後にわけて考える。

$|s_r+s_c-t_r-t_c|$ については、$t_r+t_c$ の値ごとに求めておけば、$2N-1$ 個の値を求めるだけで済む。
$C$ の値を $s_r+s_c$ の値ごとに事前集計すれば、$(2N-1)\times(2N-1)$ 通りの $O(N^2)$ で求まる。
もしくは、累積和と差分更新を使って $O(N)$ でやってもよい。
（別解コードでは、その方針を取っている）

$|s_r-s_c-t_r+t_c|$ も同様。
ここまでくれば、それらを用いて $f(i,j)$ を求めるのは $O(1)$ でできるので、あとは単純な処理だけ。
絶対値を足した後で $2$ で割るのを忘れないように注意。

計算量は $O(N^2)$ である。