2014 TCO Round 2B Easy - SwitchingGame (○)

October 28, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13110&rd=15996

・ONとOFFができるスイッチが複数与えられる。
・最初は全てOFFの状態。
・複数スイッチの状態が与えられ、順番にその状態に変化させていく。
・スイッチの状態はON,OFF,？の３つであり、？はON/OFFどちらでもよい。
・スイッチの状態変化は、好きなだけ＋に変化させる動作が１動作、
　好きなだけ－に変化させる動作が１動作、
　状態を一緒に合わせたあとボタンを押すのに１動作かかる。
・このとき、必要な動作回数の最小値を求める。

解き方

・前のスイッチの状態を持っておき、毎回変化数を記録しておけばよさそう。
・？については好きな状態でよい。
・つまり、そのあとに出てくるのが＋でプラスの動作が行われるのであれば＋にしてしまい、
　逆に出てくるのが－でマイナスの動作が行われるのであれば－にしてしまうのが
　最適な動作になる。

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class SwitchingGame {

public: int timeToWin(vector<string> states) {
int m=states[0].size();
int n=states.size();
int ret=n;

string prev="";
FORE(i,0,m)prev+='-';

FORE(i,0,n){
int plus=0,minus=0;
FORE(j,0,m){
if(prev[j]=='-' && states[i][j]=='+')plus=1;
if(prev[j]=='+' && states[i][j]=='-')minus=1;
}

FORE(j,0,m){
if(states[i][j]=='?'){
FORE(k,i+1,n)if(states[k][j]!='?'){
if(states[k][j]=='+' && plus)prev[j]='+';
else if(states[k][j]=='-' && minus)prev[j]='-';
break;
}
}
else prev[j]=states[i][j];
}

ret+=plus+minus;
}

return ret;
}

};

状態遷移