読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1204 : Pipeline Scheduling

問題リンク : Pipeline Scheduling | Aizu Online Judge

問題概要:
5*n (n < 20)の長方形が与えられる
これは、1回の処理をする際に使用するユニットの状態を文字で表したものである
入力の要素が'X'となっているならばその時間にそのユニットを使用する
'.'はその時間にそのユニットを使用しないことを表す
この処理を衝突がおきないようにして10回行った時にかかる最小の時間をもとめよ

解法:
再帰で全て試した

まず最初に、0秒で処理を行った状態に対してその後1秒からn+1秒の間についてそれぞれ処理を行えるか行えないのかを確認し、その情報を保存しておく(今回はnが20未満なのでビットを使った)

例えば、次のようなインプットの時
4
.X.X
...X
..X.
....
X...

0秒で処理を行った状態に対して、
1秒から次の処理をできるか?

2秒から次の処理をできるか?

3秒、4秒は衝突することなく置くことができる
これらの情報を、ビットで表現すると 10100 となる(0秒にはもうすでに処理をしているので再度おくことはできない)

後は再帰で全ての状態を試してみる

rec(処理できない時間を表したビット、今何回処理を行ったか、これまでにかかった時間) という関数をつくった

ここで、0秒からn秒までの間で引数としてもってきたビットが立っていない場所(ビットが0の場所)は処理ができるのでその秒数だけ左にシフトし、最初につくった情報と論理和をとってまた再帰する)

処理を行った回数が10を超えたものの時間の中で最小のものを答えとして出力して終わり


コード:

int n;
string pip[5];
int state;
int ans;
int maxim;

void create_state()
{
  state = 1;
  REP(i,1,n)
    {
      rep(j,n)
	{
	  if(i+j >= n)break;
	  rep(k,5)
	    {
	      if(pip[k][j] == 'X' && pip[k][i+j] == 'X')
		{
		  state |= (1<<i);
		  goto Next;
		}
	    }
	}
    Next:;
    }
}

void create_maxim()
{
  maxim = 0;
  rep(i,5)rep(j,n)if(pip[i][j] == 'X')maxim = max(maxim,j);
}

void rec(int now_state,int cnt,int value)
{
  if(value>=ans)return;
  if(cnt >= 10)
    {
      ans = min(ans,value);
      return;
    }

  rep(i,n+1)
    {
      if((now_state >> i) & 1)continue;
      int next_state = (now_state >> i) | state;

      rec(next_state,cnt+1,value+i);
    }

}

int main()
{
  while(cin >> n,n)
    {
      ans = inf;
      rep(i,5)cin >> pip[i];
      create_state();
      create_maxim();
      rec(state,1,maxim);
      cout << ans+1 << endl;
    }
  return 0;
}