6

M 個の 2 進数の配列があり、それぞれの状態は「0」または「1」です。数値の状態を変更するには、いくつかの手順を実行できます。各手順では、正確に N 個の連続した数値の状態を変更できます。もちろん、数値 M、N、およびメンバーを含む配列が与えられると、すべての 2 進数を 1 つの状態 (1 または 0) に変換するために必要な最小ステップ数を計算しようとしています。

M = 6 および N = 3 で、配列が 1 0 0 1 0 0 の場合、解は 2 になります。配列を 111000 に変換し、最後の 3 つの (N) 0 を 1 に反転します。

4

2 に答える 2

6

私が質問を正しく理解していれば、少し考えただけで、動的プログラミングでさえ必要ないことがわかるでしょう。解決策はまったく簡単です。

これは私が理解している質問です: 0 と 1 の配列 a[1]..a[M] が与えられ、S kという形式の操作が許可されます。ここで、S kは N 個の要素 a を反転することを意味します。 [k]、a[k+1]、...a[k+N-1]。これは明らかに 1≤k≤M-N+1 に対してのみ定義されています。

これらの一連の操作 S kを実行することにより、すべて 0 またはすべて 1 の状態に到達する必要があります。両方を別々に解き、小さい方の数を取ります。したがって、それらをすべて 0 にしたいとします (他の場合、すべて 1 は対称です)。

重要な考え方は、操作 S kを 2 回以上実行したくない(2 回実行することは、まったく実行しないことと同じです) ということと、操作の順序は重要ではないということです。したがって、問題は、実行する操作のサブセットを決定することだけであり、これは簡単に決定できます。[1] を見てください。0 の場合、 S 1を実行しないことがわかります。それ以外の場合は、S 1を実行する必要があることがわかっているため(これは a[1] を反転する唯一の操作であるため)、実行します — これにより、すべてのビットが a[1] から a[N] に切り替わります。次に a[2] を見てください (この操作の後)。1か0かでS2をするかどうかがわかるか否か。などなど — 実行する操作の数 (およびどれ) を線形時間で決定できます。

編集: C++ タグがあるため、疑似コードを C++ コードに置き換えました。醜いコードで申し訳ありません。「コンテスト モード」のときは、コンテストの習慣に戻ります。:-)

#include <iostream>
using namespace std;
const int INF = 20000000;
#define FOR(i,n) for(int i=0,_n=n; i<_n; ++i)

int flips(int a[], int M, int N, int want) {
  int s[M]; FOR(i,M) s[i] = 0;
  int sum=0, ans=0;
  FOR(i,M) {
    s[i] = (a[i]+sum)%2 != want;
    sum += s[i] - (i>=N-1?s[i-N+1]:0);
    ans += s[i];
    if(i>M-N and s[i]!=0) return INF;
  }
  return ans;
}

int main() {
  int M = 6, N = 3;
  int a[] = {1, 0, 0, 1, 0, 0};
  printf("Need %d flips to 0 and and %d flips to 1\n",
         flips(a, M, N, 0), flips(a, M, N, 1));
}
于 2010-02-25T22:22:07.437 に答える
3

ShreevatsaR が提案したアルゴリズムをコード化しましたが、M で実際の線形時間になるようにキューの改善を追加しました。

int solve(vector<bool> bits, int N)
{
  queue<int> flips;
  int moves = 0;

  for (int i = 0; i < bits.size(); ++i)
  {
    if (!flips.empty() && flips.front() <= i - N)
      flips.pop();

    if ((bits[i] ^ (flips.size() % 2 == 0)) == 1)
    {
      if (i > bits.size() - N)
        return -1; // IMPOSSIBLE

      moves++;
      flips.push(i);
    } 
  }

  return moves;
}

オリジナルと反転したオリジナルでそれを実行し、最小値を取ります (-1 でない場合)。両方とも -1 の場合、それは不可能です。

そのコードをコンパイルもテストもしていませんが、動作するはずです。

于 2010-02-25T23:07:47.327 に答える