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

あったこといろいろ

ほぼ自分用備忘録です。

TCO Algorithm Round 2B easy 解き直し

easy落ちなので解き直したgreedy解
ネスト深すぎィ!

考え方

'?'が出現した場合、'?'以外の文字にあたるまで出現行を下に辿って行く。

  • 初めにあたったのが'+'だった場合、'?'が出現した行ですでにlampを点灯させていれば'?'を'+'に置き換える。
  • 初めにあたったのが'-'だった場合、'?'が出現した行ですでにlampを消灯させていれば'?'を'-'に置き換える。


以下の図の場合1レベル目の手本と一致させるなら、少なくとも1文字目を点灯させる必要がある。
1レベル目の2文字目である'?'から下に辿って行くと'+'があり、1レベル目の2文字目を'+'に変更しても新たにコストはかからないので'+'に変更しておく。
よって1レベル目終了後のlampの状態は"++-"となる。

f:id:Yazaten:20140608104906p:plain

※紙に実際に解いていて気付いた、greedyの証明は略。

#include <string>
#include <vector>

using namespace std;
typedef long long ll;


class SwitchingGame{
public:
	string now="";
	ll len;
	ll sum=0;
	
	bool checkSame(string s){ 
    	for(int i=0;i<len;i++){ 
    		if(s[i]==now[i] || s[i]=='?'){} 
    		else{
    			return false; 
			}
		} 
		return true;
	} 
	
	int timeToWin(vector <string> states){
		len=states[0].size();
		for(int i=0;i<len;i++)now+='-';
		
		for(int i=0;i<states.size();i++){
			sum++;
//cout<<i<<" "<<now<<endl;
			if( checkSame(states[i]) ){}
			else{
				bool up=false,down=false;
				
				for(int j=0;j<len;j++){
					if(states[i][j]=='+' && now[j]=='-'){
						up=true;
//cout<<"will up"<<i<<j<<states[i]<<now<<endl;
						now[j]='+';
					}		
					else if(states[i][j]=='-' && now[j]=='+'){
						down=true;
//cout<<"will down"<<i<<j<<states[i]<<now<<endl;
						now[j]='-';
					}
				}
				
				if(up){
					sum++;
//cout<<"use up"<<endl;
					for(int j=0;j<len;j++){
						if(states[i][j]=='?'){
							for(int k=i+1;k<states.size();k++){
								if(states[k][j]!='?'){
									if(states[k][j]=='+'){
										now[j]='+';
										break;
									}
									else break;
								}
							}
						}
					}
				}
				if(down){
					sum++;
//cout<<"use down"<<endl;
					for(int j=0;j<len;j++){
						if(states[i][j]=='?'){
							for(int k=i+1;k<states.size();k++){
								if(states[k][j]!='?'){
									if(states[k][j]=='-'){
										now[j]='-';
										break;
									}
									else break;
								}
							}
						}
					}
				}
			}
		}
		return sum;
	}
};