torus711 のアレ

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

AtCoder Regular Contest #013, C : 笑いをとれるかな?

解法

各豆腐について、ハバネロを含む最小の直方体が残ると、どう切ってもハバネロを食べてしまいます。
すると、この直方体のみになるまでにどう切るか、という問題になります。
ところで、この直方体から豆腐の表面までの長さについて、一箇所を切っても他の部分には影響がありません。
この長さを Nim の山と見做すことで、問題を Nim に帰着できます。
従って、それぞれの豆腐について、切れる長さを計算して、これらの XOR をとると解けます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( it, c ) for ( auto it = c.begin(); it != c.end(); ++it )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

VI computeTofu()
{
	int x, y, z;
	cin >> x >> y >> z;

	int m;
	cin >> m;
	
	VI xs( m ), ys( m ), zs( m );
	REP( i, 0, m )
	{
		cin >> xs[i] >> ys[i] >> zs[i];
	}

	VI res;
	res.PB( *min_element( ALL( xs ) ) );
	res.PB( *min_element( ALL( ys ) ) );
	res.PB( *min_element( ALL( zs ) ) );
	res.PB( x - *max_element( ALL( xs ) ) - 1 );
	res.PB( y - *max_element( ALL( ys ) ) - 1 );
	res.PB( z - *max_element( ALL( zs ) ) - 1 );
	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI nums;
	REP( i, 0, n )
	{
		VI tmp( computeTofu( ) );
		nums.insert( nums.end(), ALL( tmp ) );
	}

	int res = 0;
	REP( i, 0, nums.size() )
	{
		res ^= nums[i];
	}

	cout << ( res != 0 ? "WIN" : "LOSE" ) << endl;
	
	return 0;
}