問題
①２次元の１と０で表わされる配列が与えられる。
②各列ごとに、任意の２つのビットを入力するとＸＯＲ,OR,ANDいずれかの計算結果が返ってくるマシーンがある。
③マシーンは各列ごとにどの操作をするか決まっているが、どの操作が行われるかは明らかにされていない。
④このとき、与えられた配列に対して各列のマシーンがどの操作を行っているか判定することができれば”ＹＥＳ”、できなければ”ＮＯ”を返す。
解き方
どのような法則があるか、各操作ごとに例をいくつか出して導く。
各操作の結果について列挙する。
ＯＲ
００→０ ０１→１ １１→１
ＸＯＲ
００→0 ０１→１ １１→０
ＡＮＤ
００→０ ０１→０ １１→１
つまり、
ＯＲとＸＯＲ １１のビット列が必要
ＯＲとＡＮＤ ０１のビット列が必要
ＸＯＲとＡＮＤ ０１か１１のビット列が必要となる。
ここから、ＯＲ，ＸＯＲ，ＡＮＤの判断には、００１があればよいことがわかる。
これを全ての列に対して判定する。
コード
class TheDeviceDiv2 {
public: string identify(vector<string> plates) {
FORE(j,0,plates[0].size()){
int one=0,zero=0;
FORE(i,0,plates.size()){
if(plates[i][j]=='1')one++;
if(plates[i][j]=='0')zero++;
}
if(one<2 || zero<1)return "NO";
}
return "YES";
}
};
public: string identify(vector<string> plates) {
FORE(j,0,plates[0].size()){
int one=0,zero=0;
FORE(i,0,plates.size()){
if(plates[i][j]=='1')one++;
if(plates[i][j]=='0')zero++;
}
if(one<2 || zero<1)return "NO";
}
return "YES";
}
};