dohatsutsu’s diary

日記を書いています。

【No.015】「JOIOIの塔 貪欲法」

Tower of JOIOI | Aizu Online Judge

この問題を解いた後、JOIのページに行くと想定解が二分探索で、O(N long N)でした。

僕の解法は貪欲法でO(N)でした。

 今回はその簡単な解説を行いたいと思います。

 

 

 

つくりたいものがJOIのみだった場合、以下のようなコードになるはずです。

#include<bits/stdc++.h>
using namespace std;
int n,J,JO,JOI;
char str[1000001];
int main(){
  scanf("%d",&n);
  scanf("%s",str); 
  for(int i=0;i<n;i++){
    if(str[i]=='J'){
      J++; // Jをつくる
    }else if(str[i]=='O'){
      if(J>0){ // Jが作られていたら、それを1つ使ってJOを作る。
        J--; // 残っていなかったらこのOは決して使われない。
        JO++;
      }
    }else if(str[i]=='I'){
      if(JO>0){ // JOが作られていたら、それを1つ使ってJOIを作る。
        JO--; // 残っていなかったら、このIは決して使われない。
        JOI++;
      }
    }
  }
  cout<<JOI<<endl;
  return 0;
}

 

しかし、今回はIOIでもよいため、工夫が必要になります。

 

'J'を読んだときは'I'を作るようにします。

 

'O'を読んだときは、'I'が余っていれば'IO'を作ります。'I'が余っていないときは、すでに完成している  'IOI' を分解して  'IO'　を2つ作るようにします。

 

Iを読んだときは、'IO'が余っていたらそれを使って'IOI'を作るようにします。

※ただし、分解によって作られたIOはなるべく使わず、普通に作られた'IO'を優先的に使うようにする。

 余っていなかった場合は'I'を作るようにします。

 

（分解することによって作ったのにも関わらず余ってしまった'IO'をくっつけて元に戻すようすることを最後に行います)

 

#include<bits/stdc++.h>
using namespace std;
int n,I,IO,IOI,cnt;
char str[1000001];
int main(){
  scanf("%d",&n);
  scanf("%s",str); 
  for(int i=0;i<n;i++){
    if(str[i]=='J'){
      I++; // Iを作る
    }else if(str[i]=='O'){
      if(I>0){
        I--; // Iを1つ使ってIOを作る
        IO++;
      }else if(IOI>0){
        IOI--; // Iが残っていないときはIOIを分解してIOを2つ作る
        IO+=2;
        cnt+=2; // この方法によって作られたIOの数を数えておく
      }
    }else if(str[i]=='I'){
      if(IO>0){
        IO--; //IOを使ってIOIを作る。
        if(IO<cnt)cnt--;//使用したIOが分解によって作られたものかどうかを判定
        IOI++;
      }else{
        I++;　// Iを作る
      }
    }
  }
  cout<<IOI+cnt/2<<endl;　// +cnt/2 は分解しすぎたIOIをもとに戻す処理
  return 0;
}