TopCoder SRM 583 Div2 Medium IDNumberVerification

珍しくDiv2MediumがDiv1Easyと違う問題だ。
http://community.topcoder.com/stat?c=problem_statement&pm=12610

問題

18桁のIDと、6桁の地名番号の配列が与えられる。
IDが以下の通り構成されるとき、そのIDは有効と言える。

• IDの先頭6桁は、地名番号の配列のいずれかと一致する
• IDの次8ケタは、YYYYMMDDの形で日付を表す。この日付は一般的なカレンダーで存在する日付である。
• IDの次の3ケタが000の場合、そのIDは無効。それ以外の場合、奇数なら男性、偶数なら女性である。
• IDの最後の18桁目はチェックサムである。(1ケタ目<<17)+(2ケタ目<<16)+…+(18ケタ目<<0)を11で割ったとき、その余りが1となるように18桁目が設定される。

与えられたIDが有効ならばその性別を、無効なら無効と答えよ。

解法

TopCoderとしては珍しい問題。AtCoderのB位で出てきそう。
題意にそって粛々と解くだけ。
閏年の判定に注意。自分も１度ミスした。

class IDNumberVerification {
	public:
	int validdate(int y,int m,int d) {
		int md[12]={31,28,31,30,31,30,31,31,30,31,30,31};
		
		if(y<1900 || y>2011) return 0;
		if(m<1 || m>12) return 0;
		if((y%400==0) || ((y%100!=0) && (y%4==0))) md[1]++;
		if(d<1 || d>md[m-1]) return 0;
		return 1;
	}
	
	string verify(string id, vector <string> regionCodes) {
		int i;
		
		FOR(i,regionCodes.size()) if(id.substr(0,6)==regionCodes[i]) break;
		if(i==regionCodes.size()) return "Invalid";
		int y=(id[6]-'0')*1000+(id[7]-'0')*100+(id[8]-'0')*10+(id[9]-'0');
		int m=(id[10]-'0')*10+(id[11]-'0');
		int d=(id[12]-'0')*10+(id[13]-'0');
		if(!validdate(y,m,d)) return "Invalid";
		if(id.substr(14,3)=="000") return "Invalid";
		int c=(id[17]=='X')?10:(id[17]-'0');
		FOR(i,17) c+=(id[i]-'0')<<(17-i);
		if(c%11!=1) return "Invalid";
		if((id[16]-'0')%2) return "Male";
		return "Female";
	}

};

まとめ

面倒なだけで面白みはないな…。