2

この方法でレイアウトされた非負の整数で構成されるテーブルがあります。テーブルの各要素は、その左または上に表示されない最小値です。6x6 グリッドの例を次に示します。

0 1 2 3 4 5
1 0 3 2 5 4
2 3 0 1 6 7
3 2 1 0 7 6
4 5 6 7 0 1
5 4 7 6 1 0

最初の行と列は 0 1 2 3 4 5 で始まります... ご覧のとおり、座標 (x,x) は常に 0 です。その後の各タイルでは、同じ行または列にまだ存在しない最小の正の数を配置する必要があります。数独パズルと同じように、同じ行と列に数字が 2 回存在することはありません。

ここで、指定された座標 (y、x) に数値を出力する必要があります。たとえば、[2, 5] = 5

実用的な解決策を思いつきましたが、メモリと時間がかかりすぎて、これを行う別の方法があることを知っています。私の制限時間は 1 秒で、数字を見つける座標は (1000000, 1000000) まであります。

現時点での私のコードは次のとおりです。

#include <iostream>
#include <vector>

int main()
{
    int y, x, grid_size;
    std::vector< std::vector<int> > grid;

    std::cin >> y >> x; // input the coordinates we're looking for

    grid.resize(y, std::vector<int>(x, 0)); // resize the vector and initialize every tile to 0

    for(int i = 0; i < y; i++)
        for(int j = 0; j < x; j++)
        {
            int num = 1;

            if(i != j) { // to keep the zero-diagonal

                for(int h = 0; h < y; h++)
                    for(int k = 0; k < x; k++) { // scan the current row and column
                        if(grid[h][j] == num || grid[i][k] == num) { // if we encounter the current num
                            num++;                                   // on the same row or column, increment num
                            h = -1; // scan the same row and column again
                            break;
                        }
                    }

                grid[i][j] = num; // assign the smallest number possible to the current tile

            }
        }

    /*for(int i = 0; i < y; i++) {            // print the grid
        for(int j = 0; j < x; j++)            // for debugging
            std::cout << grid[i][j] << " ";   // reasons

        std::cout << std::endl;
    }*/

    std::cout << grid[y-1][x-1] << std::endl; // print the tile number at the requested coordinates
    //system("pause");
    return 0;
}

それで、私は何をすべきですか？これは私が思っているよりも簡単ですか？

4

1 に答える 1

5

To summarize your question: You have a table where each element is the minimum nonnegative integer that does not appear to its left or above. You need to find the element at position (x,y).

The result is surprisingly simple: If x and y are 0-based, then the element at (x,y) is x XOR y. This matches the table you have posted. I have verified it experimentally for a 200x200 table.

The proof:

It's easy to see that the same number won't appear twice on the same row or column, because if x1^y = x2^y then necessarily x1=x2.

To see that x^y is minimal: Let a be a number smaller than x^y. Let i be the index (from the right) of the leftmost bit where a differs from x^y. The ith bit of a must be 0 and the ith bit of x^y must be 1.

Therefore, either x or y must have 0 in the ith bit. Suppose WLOG it was x that had 0. Represent x and y as:

x = A0B
y = C1D

Where A,B,C,D are sequences of bits, and B and D are i bits long. Since the leftmost bits of a are the same as those in x^y:

a^x = C0E

Where E is a sequence of i bits. So we can see that a^x < y. The value that appered in the (a^x)th row on the same column was: (a^x)^x = a. So the value a must have already appeared in the same row (or column, if it was y that had 0 in the ith bit). This is true for any value smaller than x^y, so x^y is indeed the minimum possible value.

于 2013-01-07T14:31:33.307 に答える