torus711 のアレ

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

AtCoder Regular Contest #010, B : 超大型連休

解法

日付からインデックスを生成して一次元配列化して管理します。
予め、土日に当たる部分は休日フラグを立てておきます。
すると、あるインデックスを祝日にしたいとき、インデックスの先が平日になるまでインクリメントするだけで済みます。
後は適当に連続する休日を数えます。

コード

typedef vector<int> VI;

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

const int DAYS[] = { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

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

	VI csumDays( 1, 0 );
	partial_sum( DAYS, DAYS + 12, back_inserter( csumDays ) );

	vector<bool> holiday( csumDays.back() );

	REP( i, 0, holiday.size() )
	{
		if ( i % 7 == 0 || i % 7 == 6 )
		{
			holiday[i] = true;
		}
	}

	int n;
	cin >> n;

	REP( i, 0, n )
	{
		int m, d;
		char c;
		cin >> m >> c >> d;

		int idx = csumDays[ m - 1 ] + d - 1;

		while ( idx < holiday.size() && holiday[ idx ] )
		{
			idx++;
		}

		if ( idx < holiday.size() )
		{
			holiday[ idx ] = true;
		}
	}

	int res = 0, cur = 0;

	REP( i, 0, holiday.size() )
	{
		if ( holiday[i] )
		{
			cur ++;
		}
		else
		{
			res = max( res, cur );
			cur = 0;
		}
	}

	res = max( res, cur );

	cout << res << endl;

	return 0;
}