TopCoder SRM 583, Division 2, Level 2 : IDNumberVerification

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12610&rd=15503

概要

ある国では 18 桁の住民コードを採用している。
住民コードと、有効な地域コードの一覧が与えられるので、住民コードが有効かどうか判定せよ。
無効な場合は "Invalid" 、有効な場合は住民の性別を返せ。

住民コードの正しさは次のように判定される。

• 最初の 6 桁：地域コード
  • reginCode に含まれない数字列だったら Invalid
• 次の 8 桁：誕生日コード
  • 1990/1/1 以降、2011/12/31 以前でなければ Invalid
  • 閏年を考慮する
• 次の 3 桁：任意の三桁
  • ただし、例外的に "000" は Invalid
  • この三桁が奇数なら "Male" 、偶数なら "Female"
• 最後の一桁：パリティ
  • を満たす x が 10 なら 'X' 、そうでないなら x

解法

実装するだけ。
コツとしては、段階ごとに分けて処理をすると楽だと思います。
細かい実装方法について述べると、

• 部分文字列は string::substr() を使う
• 日付部分の処理で整数 3 つにパースするときは、string::insert() で適当にスペースを挿入してから istringstream を使う
• パリティ計算では 2 の冪乗をビットシフトで計算する（整数のみでの処理になって絶対に誤差が出ないので安心）

といった感じの実装が楽だと思っています。

コード

typedef long long LL;
typedef istringstream ISS;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

const string INVALID = "Invalid";

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

class IDNumberVerification
{
public:
	string verify( string id, vector <string> regionCodes )
	{
		const int N = id.size();

		{ // region code
			if ( find( ALL( regionCodes ), id.substr( 0, 6 ) ) == regionCodes.end() )
			{
				return INVALID;
			}
		}

		{ // birthday code
			string birthday = id.substr( 6, 8 );
			birthday.insert( 6, " " );
			birthday.insert( 4, " " );
			int y, m, d;
			ISS iss( birthday );
			iss >> y >> m >> d;

			if ( y < 1900 || 2011 < y )
			{
				return INVALID;
			}
			if ( m < 1 || 12 < m )
			{
				return INVALID;
			}
			if ( d < 1 || DAYS[ isLeap( y ) ][ m - 1 ] < d )
			{
				return INVALID;
			}
		}

		{ // parity
			string str = id.substr( 0, 17 );
			LL res = 0;
			REP( i, 0, 17 )
			{
				( res += ( str[i] - '0' ) * ( 1ULL << ( 17 - i ) ) ) %= 11;
			}
			int parity = ( 12 - res ) % 11;
			if ( id[ id.size() - 1 ] != ( parity == 10 ? 'X' : parity + '0' ) )
			{
				return INVALID;
			}
		}

		string gender = id.substr( 6 + 8, 3 );
		if ( gender == "000" )
		{
			return INVALID;
		}
		int res;
		ISS iss( gender );
		iss >> res;
		return res % 2 ? "Male" : "Female";
	}

	bool isLeap( int y )
	{
		if ( !( y % 400 ) )
		{
			return true;
		}
		if ( !( y % 100 ) )
		{
			return false;
		}
		return !( y % 4 );
	}
};