1

これは Topcoder SRM 566 Div2 のアルゴリズムの問​​題です。

問題はここで見ることができます。

トップコーダーアカウントを持っていない人のために、問題を以下に説明します:

Penguin Pals（ペンギンパルズ）は、以下の手順でペンギン同士をマッチングするマッチングサービスです。

  1. 各ペンギンには、「青と赤のどちらが好きですか?」という 1 つの質問がされます。
  2. すべてのペンギンは、等間隔で円の上に立つように配置されています。
  3. 主催者は、いくつかのペアのペンギンを結ぶ直線をいくつか描きます。各ペンギンは、最大 1 つの他のペンギンとしか接続できません。ペンギンが違う色を好む場合、2 匹のペンギンを接続することはできません。
  4. 他のペンギンに接続されている各ペンギンは、一致するものを見つけるために線をたどります。

上記のシステムの唯一の問題は、2 本の線が交差するとペンギンが衝突してしまうことでした。したがって、新しい追加ルールが採用されました。2 つの線が交差してはなりません。Penguin Pals には、いくつかのペンギンが円上に配置されています (上記の手順のステップ 2 の後)。作成できるペンギンのペアの最大数を知る必要があります。

円形配置で i 番目の文字が i 番目のペンギン (0 から始まるインデックス) の好みの色を表す文字列の色が与えられます。i 番目のペンギンが赤を好む場合、i 番目の文字は 'R' であり、i 番目のペンギンが青を好む場合は 'B' です。形成できる一致したペアの最大数を返します。

例：

"RRBRBRBB"

リターン: 3

"BBBB"

リターン: 2

「RRRBRBRBRBRB」

リターン: 5

私のアプローチ:

長さ n の文字列 s を呼び出します。(0 番目と n-1 番目のインデックスは連続していることに注意してください)。

次のような再帰関数 recurse(string s,int i,int j) を使用しました。

int recurse(string s,int i,int j)
{
     if(i>=j)
           return 0;
     if(s[i]==s[j])
        return(1+recurse(s,i+1,j-1));
     else return max(recurse(s,i,j-1),recurse(s,i+1,j));
}

i=0 と j=n-1 から始めます。どちらも等しい場合は連続するため、(i+1,j-1) で関数を呼び出します。そうでない場合は、両方の可能性を考慮して関数 recurse を呼び出します。 (s,i,j-1) および recurse(s,i+1,j) であり、これら 2 つの最大値を取ります。

考えられるすべての開始ペアに対してこの関数を呼び出しました。

入力「RRRBRRBB」の場合。

入力を使用して関数 recurse() を呼び出しました。

  1. s="RRRBRRBB" i=0 j=n-1
  2. s="RRBRRBBR" i=0 j=n-1 (文字列を左に移動し、以前の左端が右端になりました)
  3. s="RBRRBBRR" i=0 j=n-1 (同じ操作)

すべてのケースがカバーされるまで続きます。

しかし、私は WA を取得しましたが、なぜそれが機能しないのか、私のアプローチの欠陥を特定できませんでした。

4

2 に答える 2

3

ソリューションを修正するには、再帰呼び出しごとに次のことを行う必要があります。

s="RRRBRRBB" i=0 j=n-1
s="RRBRRBBR" i=0 j=n-1 (Moved the string left and the earlier leftmost is now the rightmost)
s="RBRRBBRR" i=0 j=n-1 (the same operation)
and so on until all the cases are covered.

しかし、私はこの場合TLEを感じます。

解決策: これは単純な問題です。

1) s[i] == s[(i+1) % n] である文字列からすべてのペアを削除し、カウントを計算します。(i は 0 から n-1 まで)。

2) 文字列が "RBRBRBRB...RB" または "BRBRBRBRBR...BR" に変換されなくなるまで #1 を繰り返します。この特別なケーシングの結果 (長さ / 2) - 1;

于 2013-01-15T13:43:35.707 に答える
1

予想される解決策がSRM566の問題セット分析ページに記載されていることは、おそらく言及する価値があります。

于 2013-02-23T16:59:14.803 に答える