【数学?】表埋め問題【プログラム?】

【問】ある表はどのマスもその行で自分より左側、その列で自分より上側、のどちらにも現れない自然数の中で最小のものを書きこんである。 一番左上端に1を書き込んだ時N行M列目の数字を求める関数をプログラムとかなんかで組め。※O(logN*logM)より小さくすべし

この問題、とりあえずプログラムを組んで解いてみたい。
方針としては n*mの表を実際に書いて、右下を出力する感じで行きたいと思います。
いちいち全てのマスで左と上を確認していたら、O(n^2m^2)で制限オーバーなので、少し工夫が必要。
表を実際に眺めて規則性を見つける。

 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 2  1  4  3  6  5  8  7 10  9 12 11 14 13 16 15
 3  4  1  2  7  8  5  6 11 12  9 10 15 16 13 14
 4  3  2  1  8  7  6  5 12 11 10  9 16 15 14 13
 5  6  7  8  1  2  3  4 13 14 15 16  9 10 11 12
 6  5  8  7  2  1  4  3 14 13 16 15 10  9 12 11
 7  8  5  6  3  4  1  2 15 16 13 14 11 12  9 10
 8  7  6  5  4  3  2  1 16 15 14 13 12 11 10  9
 9 10 11 12 13 14 15 16  1  2  3  4  5  6  7  8
10  9 12 11 14 13 16 15  2  1  4  3  6  5  8  7
11 12  9 10 15 16 13 14  3  4  1  2  7  8  5  6
12 11 10  9 16 15 14 13  4  3  2  1  8  7  6  5
13 14 15 16  9 10 11 12  5  6  7  8  1  2  3  4
14 13 16 15 10  9 12 11  6  5  8  7  2  1  4  3
15 16 13 14 11 12  9 10  7  8  5  6  3  4  1  2
16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

直感で規則性を激しく感じるが見いだせない。
\begin{Bmatrix}n & n+1 \\n+1 & n\end{Bmatrix}
が無数に並んでますが たいしてnの一般性もない。
しかしこれ、よく見てみると。

 1  2   3  4
 2  1   4  3

 3  4   1  2
 4  3   2  1

\begin{matrix}1 & 2 \\2 & 1\end{matrix}をnとみなしたら
\begin{Bmatrix}n & n+2 \\n+2 & n\end{Bmatrix}
が成り立ってますね。

どうやら2^m行、2^m列ごとに
\begin{pmatrix}1 & \ldots & 2^m \\\vdots&\ddots &\vdots\\2^m & \ldots & 1\end{pmatrix}
\begin{Bmatrix}n & n+2^m \\n+2^m & n\end{Bmatrix}のように並ぶようです。
たしかに、AもBも中の大小関係や重複の条件が成り立っていてAとBの大きさが一緒で、どのAの要素もどのBの要素より小さいのなら \begin{pmatrix}A&B\\B&A\end{pmatrix}も条件に合いそうです。
よって[tex:(X,Y) (X

def solve(a,b,c=0):
	if a==b:
		return c+1
	if a<b:
		t=b;b=a;a=t
	e=0
	while(a>2**e):
		e+=1
	if 2**(e-1)<b:
		return solve(a-2**(e-1),b-2**(e-1),c)
	return solve(a-2**(e-1),b,c+2**(e-1))	

これでオーダーはlogN*logMぐらいになったはず。
ということで、今回のはちょっと規則性に気づけば解ける問題でしたー。


しかーし、この問題もっと奥が深く、さらにオーダーを小さくすることができるのです!!
だが、このブログはそれを書くのにスペースが少なすぎる。

※追記 よく考えたらO(logN)でしたー