ABC127 Cell Distance

所感

思ったより簡単だったし本番中解けてもよかったね

問題概要

N行M列の盤面にK個のコマを置くことを考える。
配置のコストをすべての盤面上のコマ同士のマンハッタン距離で定義するとき、すべての置き方のコストの総和を求めよ。

取った方針

コマを置く2箇所を定めた時、残りのコマの置き方はBinom(NM-2, K-2) (Binomは二項係数)通り。
よって、そのコストをcと置くと、 c * Binom(NM-2, K-2)のコストがかかる。
よって、すべてのマス(x, y) について、残りのすべてのマスに対するマンハッタン距離の和sumを計算し、sum * Binom(N*M-2, K-2) の和を計算し、最後に2で割ったもの(この数え方では同じ組を二回数えることになるので) が答えになる。

1マスを決めたときの残りのすべてのマスに対するマンハッタン距離の和はx方向とy方向を独立に考えることで等差数列の和からO(1)で求まる。

例えば、以下の盤面で(1, 1)から他のマスへのマンハッタン距離の総和を求めることを考えます。0-indexedです

2 1 2 3  
1 0 1 2  
2 1 2 3  
3 2 3 4

各行のマンハッタン距離のx成分の和は1+0+1+2 で4です。
これはSum(0, 1) + Sum(0, 2)で表せます。(Sum(First, Last) は初項First, 末項Last, 公差1の等差数列の和です。)
これが4行分あるので、

(Sum(0, 1) + Sum(0, 2)) * 4

です。
同様にy成分も計算できます。結果、H * Wの盤面上で(x, y) から任意の他のマスへのマンハッタン距離の和はイカで表せ、O(1)で計算できます。

Sum(0, y) + sum(0, H - y - 1) * W + (Sum(0, x) * Sum(0, W - x - 1)) * H

マンハッタン距離を考えるときx軸方向とy軸方向を独立に考えることは典型らしいです。。。。

正しい方針

解説の方針はマンハッタン距離のx成分y成分それぞれがdである場合の数を数えているけどまあやってることは同じでしょう

得られた知見

・マンハッタン距離 -> x y 独立に考えるとよい

解くのに必要な要素

・平面を見たらx y 独立に考える奴

周辺調査によって得られた知見

・マンハッタン距離の和を最小にする値は中央値
・http://kagamiz.hatenablog.com/entry/2014/12/21/213931