問題
キーボードで「”月” ”日”」を打ちたいが、タイプミスをしばしば起こしてしまう。
タイプミスはキーボードの隣り合う文字についてはコスト１、スペースとの間は３のコストで定義される。
タイプ後の文字が与えられるとき、最もコストの少ない、つまり打とうとしていた「”月” ”日”」を求める。ただし同じコストの場合は最も早い月日を返す。
解き方
実装の問題なので、いかにシンプルに考えて、シンプルに実装するか。
まず問題文にキーボード間のコストが図で載っているが、
これを以下に簡単に定義できるかが課題。
キーボードをみてみると、キーボードの行単位で考えることができそう。
各行に対し、隣り合う文字とのコストは１となる。
各行に対し、真下の行の文字とのコストは１となる。
各行に対し、真下の行の左下の文字とのコストは１となる。
一番下の行について、スペースとのコストは３となる。
また英数字は８ビットで表わせるので、int型の配列d[256][256]を定義し
配列番号はアルファベット、値は距離としてあげればコストをグラフで定義できる。
最後にワーシャルフロイドを回せば各文字間の最短距離が求められる。
最後にすべての月、日に対してアウトプット「”月”、”日”」の文字列を用意し
与えられた文字inputと文字列長が同じであればコストを計算すればよい。
最後に大文字と小文字の区別をなくすように、tolower関数を使うことに注意。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int d[256][256];
class DateFieldCorrection {
public:
int rec(string str1,string str2){
int ret=0;
FORE(i,0,str1.size())ret+=d[tolower(str1[i])][tolower(str2[i])];
return ret;
}
string correctDate(string input) {
string keys[]={"1234567890","qwertyuiop","asdfghjkl","zxcvbnm"};
string month[]={"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};
FORE(i,0,256)FORE(j,0,256)d[i][j]=((i==j) ? 0 : 1e+9);
FORE(i,0,4)for(int j=0;keys[i][j+1]!='\0';j++)
d[keys[i][j]][keys[i][j+1]]=min(d[keys[i][j]][keys[i][j+1]],1);
FORE(i,0,3)for(int j=0;keys[i][j]!='\0'&&keys[i+1][j]!='\0';j++)
d[keys[i][j]][keys[i+1][j]]=min(d[keys[i][j]][keys[i+1][j]],1);
FORE(i,0,3)for(int j=1;keys[i][j]!='\0'&&keys[i+1][j-1]!='\0';j++)
d[keys[i][j]][keys[i+1][j-1]]=min(d[keys[i][j]][keys[i+1][j-1]],1);
for(int j=1;keys[3][j]!='\0';j++)d[keys[3][j]][' ']=min(d[keys[3][j]][' '],3);
FORE(i,0,256)FORE(j,0,256)d[i][j]=min(d[i][j],d[j][i]);
FORE(k,0,256)FORE(i,0,256)FORE(j,0,256)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int best=1e+9;
string ret="";
FORE(i,0,12)FORE(j,1,day[i]+1){
char ch[100];
sprintf(ch,"%s %d",month[i].c_str(),j);
if(strlen(ch)==input.size()){
int cost=rec(ch,input);
if(cost<best){
best=cost;
ret=ch;
}
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int d[256][256];
class DateFieldCorrection {
public:
int rec(string str1,string str2){
int ret=0;
FORE(i,0,str1.size())ret+=d[tolower(str1[i])][tolower(str2[i])];
return ret;
}
string correctDate(string input) {
string keys[]={"1234567890","qwertyuiop","asdfghjkl","zxcvbnm"};
string month[]={"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};
FORE(i,0,256)FORE(j,0,256)d[i][j]=((i==j) ? 0 : 1e+9);
FORE(i,0,4)for(int j=0;keys[i][j+1]!='\0';j++)
d[keys[i][j]][keys[i][j+1]]=min(d[keys[i][j]][keys[i][j+1]],1);
FORE(i,0,3)for(int j=0;keys[i][j]!='\0'&&keys[i+1][j]!='\0';j++)
d[keys[i][j]][keys[i+1][j]]=min(d[keys[i][j]][keys[i+1][j]],1);
FORE(i,0,3)for(int j=1;keys[i][j]!='\0'&&keys[i+1][j-1]!='\0';j++)
d[keys[i][j]][keys[i+1][j-1]]=min(d[keys[i][j]][keys[i+1][j-1]],1);
for(int j=1;keys[3][j]!='\0';j++)d[keys[3][j]][' ']=min(d[keys[3][j]][' '],3);
FORE(i,0,256)FORE(j,0,256)d[i][j]=min(d[i][j],d[j][i]);
FORE(k,0,256)FORE(i,0,256)FORE(j,0,256)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
int best=1e+9;
string ret="";
FORE(i,0,12)FORE(j,1,day[i]+1){
char ch[100];
sprintf(ch,"%s %d",month[i].c_str(),j);
if(strlen(ch)==input.size()){
int cost=rec(ch,input);
if(cost<best){
best=cost;
ret=ch;
}
}
}
return ret;
}
};