ABC127 E - Cell Distance
解法
ある位置に置かれた2つの駒のマンハッタン距離が何回加算されるかを考えると、個の残りの駒を配置する種類数そのものになります。ということで、これは回です。任意の位置にある2つの駒について、同じ回数だけ加算されるので、あとは任意の2つの駒について、マンハッタン距離の総和を求めてあげればをかけるだけで答えを求めることができます。
では、2つの駒についてのマンハッタン距離を求めていきます。これは、4パターンに分けることができ、
同じ行で違う列にあるパターン
同じ列で違う行にあるパターン
駒が左上と右下にあるパターン
駒が右上と左下にあるパターン
です。それぞれ下の図のようなパターンです。
さて、マスの左上を座標として、座標に駒を置いたときの、にある駒とのマンハッタン距離の総和を求めることを考えます。具体例として、下の図のようにのマスにある駒について考えます。
それぞれのマスに、(行の違いから生じる距離)+(列の違いから生じる距離)を書き込んでみると、
このようになります。行の違いによる距離はからまでの通り、列の違いによる距離はからまでの通りあり、全ての組み合わせが存在しているので、結局距離の総和は、
となり、式変形をしていくと、
から、
となり、最終的に
となります。これによって求められるのは、先ほどの4パターンのうち、4つめのパターン以外です。ということで、まずは任意のマスについて、この計算を行うことで、1~3のパターンの計算をすることができます。
さて、4つめのパターンについて考えるのですが、実は一つ前で計算したマス目を上下反転してあげると、駒は右上にいき、1,2,4のパターンについての計算を行うことができることがわかります。
これは、座標を丁寧に計算してあげると、
で計算できることがわかります。
余分なのは1,2のパターン(上の図の黄色、水色にあたる部分)であり、
それぞれ、
で計算することができるので、先ほどの式からこの値を引いてあげると、4つめのパターンは以下の式で計算できることがわかります。
ということで、任意の座標に対して、
を計算し、その総和を取った後、をかけてあげると、で答えが求まります。
感想
上下反転させたときの座標、の抜け、等々細かいバグをいろいろ踏みました。
考察自体は割とはやめに終わったので悔しいですね…