Face The Right Way (POJ No.3276)

2017.07.17
プログラミングor技術

「N頭の牛が並んでおり、それぞれ前/後どちらかを向いている。連続したK頭の方向転換ができる機械を何回か用いて、全頭の向きを前に揃えたい。最小の機械の使用回数と、そのときの最小のKを求めよ。」
という問題。

全ての機械長Kに対して、そのKで全部の牛が前向きにできるかを調べて、できるなら最小の操作回数とそのときの最小のKを更新していく。
操作回数の求め方は、左の牛から向きを揃えていけば良い。

ここで、普通に牛の向きを配列として表して反転させていると、計算量がO(N^3)になり間に合わないらしい…(試してないけど。Nが最大5000なのでN^3だと10^11以上できっと間に合わない。N^2だと10^7くらいで、多分TLEにならないと言われる10^7 ~ 10^8の中に収まる。)
なので牛の区間[i, i+K-1]にて反転したかどうかをisTurn[i]配列にもち、ある牛iが偶数回反転していれば最初と同じ向き、奇数回の反転ならば最初とは反対の向き…として考えればO(N^2)になる…んだそうです。
ある牛iが反転しているかどうかは、isTurn[i]を区間[i-K+1, i-1]で総和を取ればよくて、これが偶数かどうかで判断できます。

下はほぼ蟻本のコードと同じ。
考え方の解説は問題タイトルで検索すると出て来ます。

競技プログラミングってコメントあまりつけない上に、関数名や変数名を簡素に書くから意味が取りにくいことがありますね…。

#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <functional>
#include <iostream>

using namespace std;

#define MAX_N  5000
int N;
int dir_cow[MAX_N]={}; //前が0、後ろが1
int isTurn[MAX_N] = {}; //区間[i, i+K-1]の牛に機械を使用したかどうか。

//機械の使用回数を計算する
int calc_turnTimes(int k_lengthOfMachine) {
 memset(isTurn, 0, sizeof(isTurn));
 int turnTimes = 0;
 int sum = 0;  //たとえば、i番目の牛がどっち向いてるか知りたいなら何個の「i番目を含んでいる長さKの区間」があるか調べればよい。ので配列isTurnの区間[i-k+1, i]を足し算する
 //全牛について調べる
 for(int index_cow = 0; index_cow + k_lengthOfMachine <= N; index_cow++){
  //先頭のウシが後ろを向いている(今までの操作回数が偶数ならば、はじめと同じ向き。奇数ならば、はじめと反対の向きなので)
  if((dir_cow[index_cow] + sum) %2 != 0){
   turnTimes++;
   isTurn[index_cow] = 1;
  }
  //以下ではi番目の向きがどっちが調べるために配列isTurnの区間[i-k+1, i]を足し算する
  sum += isTurn[index_cow];
  // i-k+1より前のものを引き算する。
  if(index_cow - k_lengthOfMachine + 1 >= 0){
   sum -= isTurn[index_cow-k_lengthOfMachine+1];
  }
 }

 //操作が全部おわってなお、後ろ向きの牛が残ってないか調べる
 for(int i=N-k_lengthOfMachine+1; i<N; i++){
  //牛向きがいたら不可能として-1を返す
  if((dir_cow[i] + sum)%2 != 0){
   return -1;
  }
  //前と同じ理由でsumを計算しておく
  if(i-k_lengthOfMachine+1 >= 0){
   sum -= isTurn[i-k_lengthOfMachine+1];
  }
 }
 return turnTimes;
}

void solve(){
 cin >> N;
 string buff;
 cin >> buff;
 for(int i=0; i<N; i++){
  if(buff[i] == 'F') dir_cow[i] = 0;
  else if(buff[i] == 'B') dir_cow[i] = 1;
 }

 int K=1, M_minOfTurnTimes=N;
 //全てのKについて試す。
 for(int k_lengthOfMachine=1; k_lengthOfMachine <= N; k_lengthOfMachine++){
  int m = calc_turnTimes(k_lengthOfMachine);
  //最小操作回数と最小機械全長を更新
  if(m >= 0 && M_minOfTurnTimes > m){
   M_minOfTurnTimes = m;
   K = k_lengthOfMachine;
  }
 }
 printf("%d %dn", K, M_minOfTurnTimes);
}

int main(void) {
 solve();
 return 0;
}

コメント