TCO Algorithm Round 2B easy 解き直し
easy落ちなので解き直したgreedy解
ネスト深すぎィ!
考え方
'?'が出現した場合、'?'以外の文字にあたるまで出現行を下に辿って行く。
- 初めにあたったのが'+'だった場合、'?'が出現した行ですでにlampを点灯させていれば'?'を'+'に置き換える。
- 初めにあたったのが'-'だった場合、'?'が出現した行ですでにlampを消灯させていれば'?'を'-'に置き換える。
以下の図の場合1レベル目の手本と一致させるなら、少なくとも1文字目を点灯させる必要がある。
1レベル目の2文字目である'?'から下に辿って行くと'+'があり、1レベル目の2文字目を'+'に変更しても新たにコストはかからないので'+'に変更しておく。
よって1レベル目終了後のlampの状態は"++-"となる。
※紙に実際に解いていて気付いた、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; } };