torus711 のアレ

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

TopCoder SRM 583, Division 2, Level 2 : IDNumberVerification

概要

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

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

  • 最初の 6 桁:地域コード
    • reginCode に含まれない数字列だったら Invalid
  • 次の 8 桁:誕生日コード
    • 1990/1/1 以降、2011/12/31 以前でなければ Invalid
    • 閏年を考慮する
  • 次の 3 桁:任意の三桁
    • ただし、例外的に "000" は Invalid
    • この三桁が奇数なら "Male" 、偶数なら "Female"
  • 最後の一桁:パリティ
    • x = \sum_{i = 0}^{16} id_i \times 2^{ 17 - i } = 1 を満たす 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 );
	}
};