torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 569, Division 2, Level 2 : TheDeviceDiv2

概要

同一の長さの二つのビット列に対して、ビット毎にビット演算 ( OR, AND, XOR ) のいずれかを行う機械がある。
N 本のビット列が与えられるので、それらのビット列を用いて、この機械の全てのビットについてその動作を一意に決定できるかどうか示せ。

解法

1 1 と 1 0 のパターンを試すことで一意に決定することができます。
従って、各インデクスについて 0 と 1 の数を数え、0 が無いか 1 が 1 個以下のインデクスがあれば NO です。
なお、0 0 のパターンは全て 0 になります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class TheDeviceDiv2
{
public:
	string identify( vector <string> plates )
	{
		const int N = plates.size(), L = plates[0].size();

		if ( N == 1 )
		{
			return "NO";
		}

		REP( i, 0, L )
		{
			int c0 = 0, c1 = 0;

			REP( j, 0, N )
			{
				if ( plates[j][i] == '0' )
				{
					c0++;
				}
				else
				{
					c1++;
				}
			}

			if ( c0 < 1 || c1 < 2 )
			{
				return "NO";
			}
		}

		return "YES";
	}
};