【数学?】表埋め問題【プログラム?】
【問】ある表はどのマスもその行で自分より左側、その列で自分より上側、のどちらにも現れない自然数の中で最小のものを書きこんである。 一番左上端に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
直感で規則性を激しく感じるが見いだせない。
が無数に並んでますが たいしてnの一般性もない。
しかしこれ、よく見てみると。
1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1
をnとみなしたら
が成り立ってますね。
どうやら2^m行、2^m列ごとに
がのように並ぶようです。
たしかに、AもBも中の大小関係や重複の条件が成り立っていてAとBの大きさが一緒で、どのAの要素もどのBの要素より小さいのなら も条件に合いそうです。
よって[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)でしたー