基本方針

ラベル \(1,2,\ldots,N^2\) それぞれについてそのラベルが付いているマス \((x_1,y_1),\ldots,(x_k,y_k)\) を考え、これらのうち \(1\) つが始点で \(1\) つが終点であるような経路を数えられれば良いです。

解法1(このまま適用するとTLEとなります)

各ラベルのマス \((x_1,y_1),\ldots,(x_k,y_k)\) のうち、始点となるマスと終点となるマスを全探索します。始点と終点を決めた場合の経路数はコンビネーションを用いて表せることが知られており(「場合の数 最短経路」等と検索すれば出ます)、コンビネーションの前計算をしておくことで各 \(\mathrm O (1)\) で求められます。
この解法の計算量を解析します。ラベル \(i\) のマスの個数を \(n_i\) とすると、全探索のステップ数は \(\sum{n_i^2}\) となります。最悪の場合はすべてのマスが同じラベルの場合で、これを考えると計算量は \(\mathrm O (N^4)\) となります。これではTLに間に合いません。

解法2(このまま適用するとTLEとなります)

ラベルごとに次のような動的計画法を考えます。

\(\mathrm {dp}_{i,j}\) : ある現在考えているラベルのマスが始点、終点がマス \((i,j)\) であるような経路の個数

そして、dpテーブルの現在考えているラベルのマスに対応する部分に \(1\) を、それ以外に \(0\) を代入した状態から遷移を行い、最後にdpテーブルの現在考えているラベルのマスに対応する部分の総和を求めればそのラベルのマスを始点・終点とする経路数が求められます。
この解法の計算量は、dpの計算量が \(\mathrm O(N^2)\) 、ラベルの種類数が最悪 \(N^2\) なので \(\mathrm O(N^4)\) となります。これではTLに間に合いません。

ACが得られる解法

各ラベルについて、そのラベルが付けられているマスの個数が \(N\) 以下のものについては解法1を、\(N\) より多いものについては解法2を適用すると十分高速になります。実際、以下の解析により計算量が \(\mathrm O(N^3)\) になることがいえます。

• 解法1で触れた全探索のステップ数が \(\sum {n_i^2}\) ですが、場合分けによって \(n_i\leq N\) という条件が追加されたので \(\sum{n_i^2} \leq N\sum{n_i}\) となります。また、\(\sum n_i \leq N^2\) なので \( N\sum{n_i} \leq N^3\) となり、解法1が適用される部分の計算量は \(\mathrm O(N^3)\) といえます。
• 解法2が適用されるラベルは高々 \(N\) 個です。(さもなければ、そのラベルのマスが \(N\) 個より多いラベルが \(N\) 個より多く存在することになりますが、これはマスの個数が \(N^2\) 個であることに矛盾します) \(\mathrm O(N^2)\) のdpが高々 \(N\) 回なので解法2が適用される部分の計算量も\(\mathrm O(N^3)\) といえます