1

このリンクにアクセスするにはログインが必要なため、ここに問題のステートメントを貼り付けて、トップコーダーのボール削除の問題を解決しようとしています。

問題文

N 個のボールがあり、N は奇数です。ボールには 0 から N-1 までの番号が付けられています。この順番で、左から右へ一列に並んでいます。

数字に加えて、各ボールには「左」または「右」という言葉が書かれています。簡単にするために、「左」の代わりに文字「<」を使用し、「右」の代わりに文字「>」を使用します。すべてのボールに文字列ラベルとしてラベルが付けられます。各 i について、ラベルの文字 i はボール i の単語を表します。

次の手順を繰り返します。

  • ボールの列のどちらの端にもないボールを選択します。
  • 選択したボールに「<」のラベルが付いている場合は、選択したボールとそのすぐ左にあるボールを削除します。それ以外の場合は、選択したボールとその右側のボールも削除します。
  • 残りのボールを並べ替えずに、それらを一緒に押して、前のステップで作成されたギャップを取り除きます。

列にボールが 1 つだけ残っている場合、プロセスは終了します。そのボールは生存者と呼ばれます。ボールの数字は、プロセス中に変化しないことに注意してください。

すべての可能な生存者を見つけます。メソッドは、正確に N 文字を含む文字列を返す必要があります。ボール i が生き残った場合、戻り値の文字 i は 'o' (小文字の oh) でなければなりません。それ以外の場合、対応する文字は「.」でなければなりません。(ピリオド)。

制約

  • ラベルには 3 ～ 49 文字が含まれます。
  • label には奇数の文字が含まれます。
  • ラベルの各文字は、'>' または '<' のいずれかになります。

例
"<<>" 戻り値: "..o"

最初は、3 つのボールがあります。行の端にあるボールを選択することはできないため、ボール 1 を選択する必要があります。ラベルが「<」であるため、ボール 0 と 1 を削除します。したがって、生き残ることができる唯一のボールはボール 2 です。1) ">>>< <" 戻り値: "o...o"

最初にボール 2 またはボール 3 を選択すると、次にボール 1 を選択する必要があり、生存者はボール 0 になります。最初にボール 1 を選択すると、次にボール 3 を選択する必要があり、生存者はボール 4 になります。

2) "<<><<" 戻り値: "....o"

3) "<><<><>" 戻り値: "o.....o"

4) ">>><<<>>>>><<<>" 戻り値: "o.....oo....o"

私はこの問題に対する動的プログラミングのアプローチを考えています。ブール配列を使用して削除された文字をマークし、次の左と次の右を見つけることを考えていますが、それではアプローチが非常に非効率的になり、再帰メソッドを書きます。動的プログラミング手法を実装するには、状態を維持する必要があります。しかし、私は状態として何を保持すべきかを理解することができません。私の考えでは、状態は現在の文字列と現在のインデックスの両方の組み合わせですが、状態の文字列を維持することは私には正しくないようです。

私が直面しているもう1つの問題は、この場合、方向を変更すると特定の方向がないことです。左から右に移動すると、右から左に移動する必要がある場合もあります。この問題への適切なアプローチを見つけるのを手伝ってください。

4

1 に答える 1

1

状態はブール値 -DP[left][right][isLeftBoundary][isRightBoundary]です。

これは、で始まる部分文字列leftと終わる部分文字列をright完全に削除できるかどうかを意味します。

isLeftBoundaryleftシンボルが文字列の左端にある場合は、単なるブール フラグです。

isRightBoundaryrightシンボルが文字列の右端にある場合は、単なるブール フラグです。

DP[0][i - 1][1][0]とDP[i + 1][N][0][1]がの場合true、その位置にボールiが留まることができることを意味します。

    int canDelete(int l, int r, int st, int en)
    {
        if (l > r) return 1; //we succeeded in removing the whole string

        if (DP[l][r][st][en] != -1)
           return DP[l][r][st][en];

        int ans = 0;

        //i is the last removed ball, which will eliminate the whole string[l, r]
        for (int i = l + st; i <= r - en; i++) 
        {
            if (inp[i] == '<') //it will remove a ball to the left, but which one?
            {
                for (int j = l; j < i; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, j - 1, st, 0) 
                      && canDelete(j + 1, i - 1, 0, 0) 
                      && canDelete(i + 1, r, 0, en))
                         ans = 1;       
                }
            }
            else
            if (inp[i] == '>') //it will remove a ball to the right, but which one?
            {
                for (int j = i + 1; j <= r; j++) //ball i will remove ball j
                {       
                     if (canDelete(l, i - 1, st, 0) 
                      && canDelete(i + 1, j - 1, 0, 0) 
                      && canDelete(j + 1, r, 0, en))
                         ans = 1;       
                }       
            }
        }

        return ans;
    }
于 2012-11-29T08:13:20.717 に答える