ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC127 E - Cell Distance

問題
提出コード

解法

ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、K-2個の残りの駒を配置する種類数そのものになります。ということで、これは_{MN-2}C_{K-2}回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任意の2つの駒について、マンハッタン距離の総和を求めてあげれば_{MN-2}C_{K-2}をかけるだけで答えを求めることができます。
では、2つの駒についてのマンハッタン距離を求めていきます。これは、4パターンに分けることができ、

  1. 同じ行で違う列にあるパターン

  2. 同じ列で違う行にあるパターン

  3. 駒が左上と右下にあるパターン

  4. 駒が右上と左下にあるパターン

です。それぞれ下の図のようなパターンです。

f:id:emtubasa:20190526141152p:plain

f:id:emtubasa:20190526141221p:plain

f:id:emtubasa:20190526141238p:plain

f:id:emtubasa:20190526141253p:plain

さて、マスの左上を座標(0,0)として、座標(i,j)に駒を置いたときの、(a,b) (a \leq i,b \leq j)にある駒とのマンハッタン距離の総和を求めることを考えます。具体例として、下の図のように(3,4)のマスにある駒について考えます。

f:id:emtubasa:20190526141842p:plain

それぞれのマスに、(行の違いから生じる距離)+(列の違いから生じる距離)を書き込んでみると、

f:id:emtubasa:20190526142301p:plain

このようになります。行の違いによる距離は0からiまでのi+1通り、列の違いによる距離は0からjまでのj+1通りあり、全ての組み合わせが存在しているので、結局距離の総和は、
\displaystyle \sum_{p=0}^{i}\sum_{q=0}^{j}(p+q)
となり、式変形をしていくと、
\displaystyle \sum_{q=0}^{j}\sum_{p=0}^{i}p + \sum_{p=0}^{i}\sum_{q=0}^{j}q
から、
\displaystyle \sum_{q=0}^{j}\frac{i(i+1)}{2} + \sum_{p=0}^{i}\frac{j(j+1)}{2}
となり、最終的に

  • \frac{i(i+1)(j+1)}{2} + \frac{j(j+1)(i+1)}{2}

となります。これによって求められるのは、先ほどの4パターンのうち、4つめのパターン以外です。ということで、まずは任意のマスについて、この計算を行うことで、1~3のパターンの計算をすることができます。
さて、4つめのパターンについて考えるのですが、実は一つ前で計算したマス目を上下反転してあげると、駒は右上にいき、1,2,4のパターンについての計算を行うことができることがわかります。
これは、座標を丁寧に計算してあげると、
\frac{(M-i-1)(M-i)(j+1)}{2} + \frac{j(j+1)(M-i)}{2}で計算できることがわかります。

f:id:emtubasa:20190526144047p:plain

余分なのは1,2のパターン(上の図の黄色、水色にあたる部分)であり、
それぞれ、\frac{j(j+1)}{2},\frac{(M-i-1)(M-i)}{2}
で計算することができるので、先ほどの式からこの値を引いてあげると、4つめのパターンは以下の式で計算できることがわかります。

  • \frac{(M-i-1)(M-i)j}{2} + \frac{j(j+1)(M-i-1)}{2}

ということで、任意の座標(i,j)に対して、

  • \frac{i(i+1)(j+1)}{2} + \frac{j(j+1)(i+1)}{2} + \frac{(M-i-1)(M-i)j}{2} + \frac{j(j+1)(M-i-1)}{2}

を計算し、その総和を取った後、_{MN-2}C_{K-2}をかけてあげると、O(MN)で答えが求まります。

感想

上下反転させたときの座標、MN-2-2抜け、等々細かいバグをいろいろ踏みました。
考察自体は割とはやめに終わったので悔しいですね…