2

左上隅に数値 0 を持つ 2 次元配列があります。次に、配列の残りの部分が数値で満たされるため、各インデックスには、同じ行にも列にも存在しない最小の正の整数が含まれます。

例：

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17
  1  0  3  2  5  4  7  6  9  8 11 10 13 12 15 14 17 16
  2  3  0  1  6  7  4  5 10 11  8  9 14 15 12 13 18 19
  3  2  1  0  7  6  5  4 11 10  9  8 15 14 13 12 19 18
  4  5  6  7  0  1  2  3 12 13 14 15  8  9 10 11 20 21
  5  4  7  6  1  0  3  2 13 12 15 14  9  8 11 10 21 20
  6  7  4  5  2  3  0  1 14 15 12 13 10 11  8  9 22 23
  7  6  5  4  3  2  1  0 15 14 13 12 11 10  9  8 23 22
  8  9 10 11 12 13 14 15  0  1  2  3  4  5  6  7 24 25
  9  8 11 10 13 12 15 14  1  0  3  2  5  4  7  6 25 24
 10 11  8  9 14 15 12 13  2  3  0  1  6  7  4  5 26 27
 11 10  9  8 15 14 13 12  3  2  1  0  7  6  5  4 27 26
 12 13 14 15  8  9 10 11  4  5  6  7  0  1  2  3 28 29
 13 12 15 14  9  8 11 10  5  4  7  6  1  0  3  2 29 28
 14 15 12 13 10 11  8  9  6  7  4  5  2  3  0  1 30 31
 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0 31 30
 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  0  1
 17 16 19 18 21 20 23 22 25 24 27 26 29 28 31 30  1  0

このような配列の行と列が与えられた場合、比較的新しいデスクトップ PC (行と列が 100 万未満) で、指定されたインデックスの数値を 1 秒以内に見つけることができる必要があります。これまでの私のブルートフォースの試みは無駄だったので、これは明らかに私がやりたい方法ではありません. おそらく、配列内の先行するすべての数値を計算する必要のない、線形時間 (?) で問題の数値を見つける方法が必要です。

4

1 に答える 1

2

観察によると、演算子はビット単位ですXOR(各オペランドを 2 進数として表し、対応するビットを XOR し、2 進数として読み取ります)。

XORであることを証明します。

一方の引数を固定した XOR は、もう一方の引数の全単射であるため、「同じ行にも同じ列にも存在しない」が満たされます。

これで、「最小」の部分、つまりいずれかのオペランドを減らすと、より低い値がすでに発生していることを証明するだけで十分です。

foreach A >= 0, B >= 0, F >= 0:
  (A xor B > F) => (exists D: D xor B = F) or (exists E: A xor E = F)

または同等に

foreach 0 <= A, 0 <= B, 0 <= F < (A XOR B)
  (exists D: D xor B = F) or (exists E: A xor E = F)

XOR の最小性を証明しているので、演算子についてはもはや心配していないことに注意してください。

定義C = A xor B

の場合A = 0、B = 0最小性が満たされます。

ここで、AとBが同じ大きさ (同じビット長) の場合、両方の最上位ビットをクリアしても変化しませんC。最上位ビットをクリアすると、行列の原点に向かう変換になります。したがって、変換後に小さい値が上または左に存在する場合、それは変換前と同じ相対位置にあります。

AB反例になるには、大きさが異なる必要があります。XOR（および検討中の演算子）は対称であるため、A > B.

Fが よりも大きい場合A、それは小さくないため、反例ではありません。

Fと同じ大きさの場合、 とAの最上位ビットをクリアAしFます。これは表の翻訳です。値は変更されますが、順序は変更されないため、移動後に小さい値が上または左に存在する場合、それは移動前と同じ相対的な位置にあります。

Fの大きさが よりも小さい場合、ピジョンホールの原理と XOR の性質により、 よりも大きさが小さいAが存在します。DAD xor B = F

要約: XOR が解に課せられた条件を満たすという証明は、XOR の対称性、その大きさ保存特性、およびその全単射特性から得られます。A xor Bを減らすよりも小さい各要素を見つけることができA、Bそれらがすべてゼロまたは異なる大きさになるまで課題を見つけることができます (その時点で、鳩の巣の原理を適用して、実際に対処しなくても課題に対処できることを証明します)。

于 2012-12-19T00:17:18.930 に答える