algorithm - Interviewstreet - 順列ゲーム

Question

Alice と Bob は次のゲームをプレイします。

1) まず、最初の N 個の数字の順列を選択します。

2) 交互にプレイし、アリスが最初にプレイします。

3) 順番に、順列から残りの数字を 1 つ削除できます。

4) 残りの数字が増加するシーケンスを形成すると、ゲームは終了します。最後のターン（その後、シーケンスが増加する）をプレイした人がゲームに勝ちます。

両方が最適にプレーすると仮定すると、どちらがゲームに勝つでしょうか?

入力: 最初の行にはテスト ケースの数 T が含まれます。T 個のテスト ケースが続きます。各ケースには、1 行目に整数 N が含まれ、2 行目に整数 1..N の順列が続きます。

出力: T 行をテスト ケースごとに 1 行出力します。アリスがゲームに勝った場合は「アリス」、それ以外の場合は「ボブ」が含まれます。

サンプル入力:

2

3

1 3 2

5

5 3 2 1 4

サンプル出力:

アリス

ボブ

制約:

1 <= T <= 100

2 <= N <= 15

順列は、最初は増加するシーケンスではありません。

上記の問題を解決しようとしています。私は遠くまで派生しましたが、ある時点で立ち往生しています。さらに先に進むのを手伝ってください。

上記の問題では、長さ 2 の順列では、プレーヤー 1 が常に勝ちます。

長さ 3 の順列では、文字列が厳密に増加または減少している場合、プレーヤー 2 が勝ちます。

長さ 4 の順列の場合、プレーヤー 1 が文字を削除することによって文字列を厳密に増加または減少させることができれば、プレーヤー 1 が勝ち、そうでない場合はプレーヤー 2 が勝ちます。

したがって、結論は次のとおりです。

現在のプレーヤーが文字列を厳密に増加させることができれば、彼/彼女は勝ちます。（些細なケース）

彼/彼女がそれを厳密に減少させることができれば、勝者はそのシーケンスの要素の数によって決定されます。そのシーケンスに偶数の要素がある場合、現在のプレーヤーが負け、そうでない場合は勝ちます。

しかし、結果の文字列が増加も減少もしていない場合はどうすればよいでしょうか??

Answer 1

これは典型的なゲームの問題です。残りの数字を示す 2^15 の可能な位置があります。残りの数字から、誰の番かを導き出すことができます。これで、次のように定義されたグラフが得られました。頂点は残りの数の可能な集合であり、2 つの頂点 u と v を接続するエッジがあります。set u を set v に変更する動きがある場合 (つまり、set vはちょうど 1 つ少ない数です)。

これで、誰が勝者であるかをすぐに知っているポジションについてすでに指摘しました。このポジションは負けとしてマークされます。他のすべてのポジションについては、次の方法で勝ちか負けかを判断します: 負けポジションに接続するエッジがある場合、そのポジションは勝ちです。つまり、あとはメモ化機能を備えた DFS のようなものを使用するだけで、どのポジションが勝ち、どのポジションが負けているかを判断できます。グラフは比較的小さい (2^15 頂点) ため、このソリューションは十分に高速です。

お役に立てれば。

Answer 2

もちろん、これは N が小さい場合は「力ずく」で行うことができますが、反転と順列の符号に関するより簡単な答えを疑うことはありませんか?

最初は「符号が-1ならアリス勝ち、そうでなければ負け」みたいな答えを疑っていたのですが、そうではありません。

しかし、アルゴリズムだけでなく、このゲームで紙とペンのパフォーマンスを同等に向上させる問題の表現を提案したいと思います。

反転は、a[i]>a[j] のようなインデックス i<j のペアです。( i, j) 頂点 1,...,N を持つ無向グラフの辺を考えてみましょう。各プレイヤーはこのグラフから頂点を削除し、エッジが残っていなければ勝ちです。

の場合5 3 2 1 4、結果のグラフは

   5--3
  /|\ |
 / | \|
4  1--2

アリスはすぐに、「5」を削除するとボブが 2 を削除できることに気付きます。その後、反転は残っておらず、ボブが勝ちます。

Answer 3

このゲームは再帰的に解くことができます。

アリスが最初のピックと i をピックするたびに、i より大きい残りのすべての数字から 1 を引きます。これで同じゲームができましたが、数字は 1 から N-1 です。

あなたのシーケンスが

1,3,5,4,2

最初の一手で、アリスは任意の数字を選ぶことができます。case1: 彼女は 1 を選び、ボブが 3,5,4,2 (2,4,3,1 に等しい) で勝てない場合、アリスは勝つことができます。

case2: 彼女は最初に 3 つを選びます。ボブが 1,5,4,2 (1,4,3,2 に等しい) で勝てない場合、アリスは勝つことができます。

case3: 彼女は最初に 5 を選びます。ボブが1,3,4,2で勝てなくてもアリスは勝てる

あなたはアイデアを得る。

したがって、可能な最初の推測ごとにサイズ N-1 の順列を使用して、サイズ N の順列の解を求める再帰関数を作成できます。再帰の基本的なケースは、順序どおりのシーケンスがある場合です。

再帰の各ステップで、人はすべての可能性を試し、勝つものを選びます。

同じシーケンスに到達できる移動の組み合わせは多数あるため、再帰にはサブの問題が重複しています。これは、動的プログラミングを使用するか、単に関数を「メモ化」して、効率を大幅に向上できることを意味します。

1 つの順列を逆にしても同じ結果が得られるなど、順列の多くのグループは同等であるため、さらに高速化するために順列に対称性を使用できます。

幸運を。

Answer 4

@tiwo、@ rup COnsidering 5 3 2 1 4は、最初にアリスが5を削除し、ボブが2を削除した後、シーケンスは3 1 4であり、昇順ではありません。その後、アリスは1を削除する機会を得て、シーケンスは次のようになります。昇順アリスが答えになるはずです。あなたが与えたグラフでは、1と3が反転しているので、3と1の間にエッジがあるはずです。

問題の答えは実際のBOBなので、どこが間違っているのか教えてください

Answer 5

ミニマックスアルゴリズムで解決できます。ここにJavaのコードがあります

import java.io.*;  
import java.util.*;  
import java.text.*;  
import java.math.*;  
import java.util.regex.*;  

public class Solution {  

    public static Scanner sc = new Scanner(System.in);  
    public static void main(String[] args) {  
        int t = ni();  
        for(int i=0; i<t; i++){  
            int n = ni();  
            Map<Long, Boolean> map = new HashMap<Long, Boolean>();  
            int[] numbers = new int[n];  
            for(int j=0; j<n; j++){  
                numbers[j] = ni();  
            }  
            if(aliceWin(numbers, map)) System.out.println("Alice");  
            else System.out.println("Bob");  
        }  
    }  

    public static boolean aliceWin(int[] a, Map<Long, Boolean> map){  
        long h = hashCode(a); int temp;   
        if(map.containsKey(h)) return true;  

        for(int i=0; i<a.length; i++){  
            if(a[i]>0){  
                temp = a[i] ;  
                a[i] = 0;  
                if(isIncreasing(a)){  
                    map.put(h, true);  
                    a[i] = temp;  
                    return true;  
                }  
                if(!aliceWin(a, map)) {  
                    map.put(h, true);  
                    a[i] = temp;  
                    return true;  
                }  
                a[i] = temp;  
            }  
        }  
        return false;  
    }  

    public static long hashCode(int[] a){  
        long result = 0;  
        for(int i=0; i<a.length; i++){  
            result = (result << 4) + a[i];  
        }  
        return result;  
    }  
    public static boolean isIncreasing(int[] a){  
        int last = 0;  
        for(int i=0; i<a.length; i++){  
            if (a[i] > 0){  
                if(last > a[i]) return false;  
                last = a[i];  
            }  
        }  
        return true;  
    }  
    public static int ni(){  
        return sc.nextInt();  
    }  

    public static void print(Object... args){          
        System.out.println(Arrays.deepToString(args));  
    }  
}  

ブログから: hackerrank-permutation-game

Answer 6

グラフを作成するコードを次に示しますが、グラフで reverse() を呼び出し、ベース内のすべてのノードに接続するソース ノードを作成し、アリスが勝つ方法があるかどうかを確認するためにソースに戻る必要があります。

input_ = """2

3

1 3 2

5

5 3 2 1 4""".splitlines()

perms = [map(int,perm.split()) for perm in input_ if len(perm)>1]
"[['1', '3', '2'], ['5', '3', '2', '1', '4']]"

if networkx is None:
    import networkx
from itertools import combinations

def build_graph(perm):
    base = set()
    G = networkx.DiGraph()
    for r in range(1,len(perm)+1):
        for combo in combinations(perm,r):
            combo = list(combo)
            if combo == sorted(combo):
                base.add(tuple(combo))
                continue
            for i in range(r):
                G.add_edge(tuple(combo),tuple(combo[:i]+combo[i+1:])) #you may want to reverse the graph later to point from base to source.
    return G,base


def solve(G,base):
    #dfs,
    pass

for perm in perms:
    G,base = build_graph(perms[0])
    print solve(G,base)

Answer 7

各ステップで、次のプレーヤーによる単一の変更を行うことを確認することはできますか?

5 3 2 1 4 のように、アリスが 3 2 1 4 を行う場合、ボブは 1 ターンで何かを排除しても勝つことはできません... 同様に、アリスが 2 1 4 を行う場合、それはソートされません..彼は 3 1 4 を行いますが、ソートされません..彼は 3 2 4 をしましたが、それはソートされていません.. 5 3 2 1 4 -> 3 2 1 4 は有効な手です!!

今度はボブの番です..彼は同じことをチェックします..しかし、しばらくすると..上記のようにあなたが動くことができる数字はありません..だからあなたはランダムな動きをしなければなりませんそして誰が勝つと、シーケンスを単一の要素にするステップの数によって簡単に計算できます!!

Answer 8

私に（ほとんどあなた自身の言葉を使って）：

彼/彼女が最初の動きでそれを厳密に増加させることができれば、彼/彼女は勝ちます (些細なケース)。それ以外の場合、勝者はそのシーケンスの要素の数によって決定されます。

2 番目のケースを例に取ります。

グラフ ソリューションは問題ないと思いますが、プレイヤーが最適な方法でプレイしていることを忘れています。したがって、それらのいくつかは最適ではない選択から派生するため、すべての異なるパスをチェックする必要はありません。