3

インタビュー通りで以下の問題を解いてみました。スコアカードを数える（30点）

トーナメントでは、N 人のプレイヤーが 1 度だけ対戦します。各ゲームは、いずれかのプレイヤーが勝利します。関係はありません。トーナメント終了時に各プレイヤーのスコアを含むスコアカードを渡しました。プレーヤーのスコアは、プレーヤーがトーナメントで勝ったゲームの合計数です。ただし、一部のプレーヤーのスコアはスコアカードから消去されている可能性があります。入力スコアカードと一致するスコアカードはいくつありますか?

入力: 最初の行にはケース数 T が含まれます。T ケースが続きます。各ケースには、最初の行に数値 N が含まれ、2 行目に N の数値が続きます。i 番目の数字は、i 番目のプレーヤーのスコアである s_i を示します。i 番目のプレーヤーのスコアが消去されている場合は、-1 で表されます。

出力: 各ケースの答えを含む T 行を出力します。各結果をモジュロ 1000000007 で出力します。

Constraints:
1 <= T <= 20
1 <= N <= 40
-1 <= s_i < N

Sample Input:
5
3
-1 -1 2
3
-1 -1 -1
4
0 1 2 3
2 
1 1
4
-1 -1 -1 2

Sample Output:
2
7
1
0
12

説明: 最初のケースでは、0、1、2 または 1、0、2 の 2 つのスコアカードが可能です。2 番目のケースでは、有効なスコアカードは 1,1,1、0,1,2、0,2,1、1,0,2、1,2,0、2,0,1、2,1,0 です。 . 3 番目のケースでは、有効なスコアカードは {0,1,2,3} のみです。4 番目のケースでは、有効なスコアカードがありません。両方のプレイヤーのスコアが 1 になることはありません。

私はジェネリック関数のアプローチを考え出そうとしましたが、動的プログラミングを使用してこの問題を突き止めようとしています。この問題の再帰関係をどのように考えることができますか?.

4

5 に答える 5

1

所見:

シーケンス s[1]、s[2]、...、s[n] が一貫したスコアカードになるには、これらのプロパティが保持されている必要があります。

  1. s[i1] + s[i2] + .. + s[ik] >= k * (k — 1) / 2、ここで i1 < i2 < .. < ik (つまり、長さ k のすべてのサブシーケンス)
  2. s[1] + s[2] + .. + s[n] = n * (n — 1) / 2

まず、1 つの条件だけを使用して、消去されていないスコアをチェックする必要があります。次に、動的計画法を使用して消去されたスコアを配置します。

消去されたスコア a[i] ではなく、消去されたスコア b[i] としましょう。

合計{i = 1 .. l} a[i] + 合計{i = 1 .. k} b[i] >= (k + l) * (k + l - 1) / 2

合計{i = 1 .. l} a[i] + 合計{i = 1 .. k} b[i] >= 0 + 1 + .. + (k + l - 1)

合計{i = 1 .. l} (a[i] - (k + i - 1)) + 合計{i = 1 .. k} b[i] >= 0 + 1 + .. + (k - 1 )

したがって、すべての k、合計の最小値について事前に計算できます{i = 1 .. l} (a[i] - (k + i - 1))/

動的計画法:

状態:

dp[k][score][sum]: 最初の k 個の最小消去スコアがわかり、それらの値は $score$ を超えず、sum はそれらの合計です。

トランジション:

  1. スキップ スコア、dp[k][スコア][合計] += dp[k][スコア + 1][合計];

  2. $i$ 値のスコア $score$ dp[k][score][sum] += C[m — k][i] * dp[k + i][score + 1][sum + i*score] 、ここで m 個の消去されたスコア、C[n][k] = 組み合わせ。

私のコード

于 2014-08-01T08:13:58.587 に答える
1

上記の問題に対するDPソリューションは次のとおりです

    public static int[][] table;  // stores the result of the overlapping sub problems
private static int N;

public static void main(String args[]) {
    Scanner scanner = new Scanner(System.in);
    int testCases = scanner.nextInt();
    for (int i = 0; i < testCases; i++) {
        N = scanner.nextInt();
        int[] scores = new int[N];
        for (int j = 0; j < N; j++) {
            scores[j] = scanner.nextInt();
        }
        long result = process(scores) % 1000000007L;
        System.out.println(result );

    }

}

private static long process(int[] scores) {
    int sum = 0; 
    int amongPlayers = 0; //count no of players whose score has been erased(-1)
    for (int i = 0; i < N; i++) {
        if (scores[i] != -1) {
            sum += scores[i];
        } else {
            amongPlayers++; 
        }
    }

    int noGames = (N * (N -1)) /2;  // total number of games



    if (sum < noGames) {
        int distribute = noGames - sum;  // score needed to be distributed;
        table = new int[distribute + 1 ][amongPlayers + 1];
        for (int m = 0; m <= distribute; m++) {
            for (int n = 0; n <= amongPlayers; n++) {
                table[m][n] = -1;
            }
        }
        return distribute(distribute, amongPlayers); // distrubute scores among players whose score is erased(-1)
    }
    else if(sum == noGames){
        return 1;
    }

    return 0;
}

/**
 * Dynamic programming recursive calls
 * @param distribute
 * @param amongPlayers
 * @return
 */
private static int distribute(int distribute, int amongPlayers) {
    if(distribute == 0 && amongPlayers == 0)
        return 1;

    if (amongPlayers <= 0)
        return 0;

    if(distribute == 0)
        return 1;

    int result = 0;
    if (table[distribute][amongPlayers - 1] == -1) {
        int zeroResult = distribute(distribute, amongPlayers - 1);
        table[distribute][amongPlayers - 1] = zeroResult;
    }
    result += table[distribute][amongPlayers - 1];

    for (int i = 1; i < N ; i++) { // A person could win maximum of N-1 games
        if (distribute - i >= 0) {
            if (table[distribute - i][amongPlayers - 1] == -1) {
                int localResult = distribute(distribute - i,
                        amongPlayers - 1);
                table[distribute - i][amongPlayers - 1] = localResult;
            }
            result += table[distribute - i][amongPlayers - 1];
        }
    }

    return result;
}
于 2013-04-22T06:50:41.343 に答える
0

私もこの課題を解決しようとしていますが、次のようにする必要があると思います。

プレイヤーの数 (=N)、未知のカードの数 (「-1」を数える)、既知のカードの合計 (「-1」以外のすべてのカードを数える) が与えられます。可能なゲームの合計数は 1 +2 +3 + ... + (players-1): 最初のプレーヤーには (players-1) の対戦相手がいて、2 番目のプレーヤーには (players-2) などがあります。

これで、可能なスコア カードの合計を再帰的に計算できます。

(プレイヤー、未知のカード、既知のカードの合計) をキーとして、可能なスコア カードの合計を値として、空のハッシュマップを初期化します。

すべてのカードが定義されている場合、答えは 0 (すべてのカードの合計が可能なゲームの総数と等しい場合) または 1 (すべてのカードの合計が可能なゲームの総数と等しくない場合) のいずれかになります。

すべてのカードが定義されていない場合は、for ループを実行し、未知のカード 1 枚を 0、1、2 ... (players-1) に設定して、ハッシュマップから結果を読み取ろうとします。ハッシュマップにない場合は、メソッド自体を呼び出し、結果をマップに保存します。

再帰コードは次のようになります。

def recursion(players: Int, games: Int, unknownCards: Int, knownScore: Int): Int = {
  unknownCards match {
    case 0 if knownScore != games => 0
    case 0 if knownScore == games => 1
    case _ =>
      map.get(players, unknownCards, knownScore) getOrElse {
        var sum = 0
        for (i <- 0 until players) sum += main(players, games, unknownCards - 1, knownScore + i)
        sum %= 1000000007
        map.put((players, unknownCards, knownScore), sum)
        sum
      }
  }
}
于 2013-01-01T20:46:53.287 に答える
0

勝利の合計は (NC 2)

入力で与えられた既知の値を引きます。残りの合計 (NC 2) - x を S とします。入力の -1 の数を Q とします。

問題は、0 から N-1 (可能な最大スコア) の範囲の Q 変数の積分解の数を見つけることになり、その合計は S になります。

DP[q][s] が、合計が s である q 変数の積分解の数を表すとします。

次に、

DP[q][s] = Sum (i=0 to N-1) DP[q-1][s-i]

DP[Q][S] は解を与える

編集:
観察: x 人が残っている場合、合計勝利数は少なくとも x*(x-1)/2 である必要があります (互いに対戦した場合)。したがって、いつでも q 人の場合、s は (Nq)(Nq-1)/2 = M を超えることはできません

s が M より大きい場合、DP[q][s] は 0 に等しくなければならないという制約がもう 1 つ必要です。

于 2012-09-22T05:53:43.627 に答える