TopCoder SRM 375 Div1 Medium DateFieldCorrection

問題

タイプミスに対するペナルティを、キーボード上での最短距離と定義する。
与えられた文字列に対して、長さが等しく、ペナルティの和が最小になるような"日付"を求めよ。

候補が複数ある場合、もっとも早い日付を答えよ。
"日付"は、月 日の形式で表される文字列である。
ただし、月は"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"のいずれかであり、
日はleading zeronのない1〜その月の日数の数字である。
それぞれの月の日数は、31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31日である。

制約条件

解は必ず存在する。

方針

キー間の最短距離をワーシャルフロイドによりあらかじめ全部求めておく。
その後、一年の全ての日付に対して、ペナルティを計算し、最も少ない日を選べばよい。

ソースコード

const char *key[]={
	"1234567890",
	"qwertyuiop",
	"asdfghjkl",
	"zxcvbnm"
};
const char *name[]={
	"January", "February", "March", "April", "May", "June",
	"July", "August", "September", "October", "November", "December"
};
int day[]={31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int d[256][256];

class DateFieldCorrection {
	public:
	string correctDate(string input) 
	{
		rep(i,256)rep(j,256)d[i][j]=i==j?0:inf;
		rep(i,4){
			for(int j=0;key[i][j];j++){
				if(j)d[key[i][j]][key[i][j-1]]=1;
				if(i<3){
					if(j<strlen(key[i+1]))
						d[key[i][j]][key[i+1][j]]=1;
					if(j+1<strlen(key[i])&&j<strlen(key[i+1]))
						d[key[i][j+1]][key[i+1][j]]=1;
				}
				if(i==3&&j)d[key[i][j]][' ']=3;
			}
		}
		rep(i,256)rep(j,256)d[i][j]=min(d[i][j],d[j][i]);
		rep(k,256)rep(i,256)rep(j,256)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		string ans;
		int mn=inf;
		
		rep(i,12)rep(j,day[i]){
			stringstream ss; ss<<name[i]<<" "<<j+1;
			string s=ss.str();
			if(s.size()!=input.size())continue;
			int p=0;
			rep(k,s.size()){
				p+=d[tolower(s[k])][tolower(input[k])];
			}
			
			if(p<mn)mn=p, ans=s;
		}
		return ans;
	}
};