1

これは、プログラミング コンテストで、2 人用ゲームの状態をどのように通過するかを「見つけた」問題です。

問題は次のとおりです。A と B の 2 人のプレイヤーの間で、A が常に最初に開始し、与えられたマトリックスからいくつかの文字を選択し、与えられた辞書から単語を作成する代替ゲームがプレイされます。その後、これらの手紙は破棄されます。次のプレイヤーは残りの文字から選択します。最後に一言も言えなかった方が負け。それぞれが最適にプレーします。

社説から 私はここに引用します

    To iterate over all non-empty subsets of the given 
    set when they represented using bitmasks:

    submask = mask
    while submask > 0
        // do the job with the submask
        submask = (submask - 1) AND mask

私が見た解決策の1つで

    int solve(int state)
    {
        if(dp[state]!=-1)
            return(dp[state]);

        int res=1;
        int nstate=state;
        while(1)
        {
            if(valid[nstate])
                res=solve(state&(~nstate));
            if(res==0)
                break;
            nstate=((nstate-1)&state);
            if(nstate==0)
                break;
        }
        if(res==0)
            dp[state]=1;
        else
            dp[state]=0;
        return(dp[state]);
    }

このコードには ~ との別の AND があります。

ここで実際に「状態」が何であるか理解できません。これと、どのようにしてすべての状態を通過できるのでしょうか? これを説明してください。

4

1 に答える 1

2

状態の説明

状態は残りの文字のセットです。

まだある文字は 1 に、なくなった文字は 0 に置き換えます。

これにより、変数マスクに保持されている数値である 2 進数が生成されます。

たとえば、ゲーム開始時に文字 ABCDEFGH があり、ある時点で文字 B と D しか残っていなかったとします。

数値 0x50 は、この現在の状態を表します。

ABCDEFGH  at start
-B-D----  at current point in game
01010000  replace with 1's for letters we still have
0x50      treat as a binary number

ビットいじり

どちらのソリューションも bit twiddle を使用しますnstate=((nstate-1)&state)。

nstate=state で開始すると、このコードは状態のすべてのサブセットを生成します。

これは何を意味するのでしょうか？さて、現在の文字が B と D の状態があるとします。この状態のすべての可能性のある空でないサブセットは {B,D},{B},{D} です。

これらは、2 進数 01010000,01000000,00010000 で表されます。

そして、これらが実際に次の Python コードを実行することによって生成されていることがわかります。

state=0b01010000
nstate=state
while nstate:
    print bin(nstate)
    nstate=(nstate-1)&state

出力を与えます：

0b01010000
0b01000000
0b00010000

なぜこれが機能するのですか？

大まかに言えば、コードはnstate = nstate-1可能なすべての 2 進数をカウントダウンするために使用し& state、気にしないビットに変更がある部分をスキップします (カウントされるのを待つのではなく、すぐにゼロに設定することにより)。ゼロまで）。

于 2013-02-25T21:35:02.670 に答える