問題
http://community.topcoder.com/stat?c=problem_statement&pm=11754&rd=14725
長さ３からなる鎖がある。
鎖はビーズか数字のパーツからなる。
複数の鎖が与えられ、鎖をつなげたときに連続した数字が美しさの値になる。
このとき、最大となる美しさの値を求める。
解き方
シミュレーションの問題なので、いかにＣｈａｌｌｅｎｇｅケースを網羅するか、間違いのないように実装するか。
１）真ん中のみに数字がある場合は、その最大値と連結した鎖と比較する必要がある
２）左と右にある鎖について、左とも右とも取れるものを考慮する。
さらに２つではなく１つだけの場合もあるため、その場合も考慮する。
文字列１つ１つでif文を書いてもよいが、for文をうまく使うことで間違いが少なく簡略化することができる。
コード
class DengklekMakingChains {
public:
int maxBeauty(vector<string> c) {
int n=c.size();
int ans=0,single=0,a[60]={},b[60]={},added=0;
FORE(i,0,n){
if(c[i][0]!='.'&&c[i][1]!='.'&&c[i][2]!='.')FORE(j,0,3)ans+=c[i][j]-'0';
else {
if(c[i][0]=='.'&&c[i][1]!='.'&&c[i][2]=='.')single=max(single,c[i][1]-'0');
for(int j=0;j<3&&c[i][j]!='.';j++)a[i]+=c[i][j]-'0';
for(int j=2;j>=0&&c[i][j]!='.';j--)b[i]+=c[i][j]-'0';
}
}
FORE(i,0,n){
added=max(added,max(a[i],b[i]));
FORE(j,0,n)if(i!=j)added=max(added,a[i]+b[j]);
}
ans+=added;
return single>ans ? single : ans;
}
};
public:
int maxBeauty(vector<string> c) {
int n=c.size();
int ans=0,single=0,a[60]={},b[60]={},added=0;
FORE(i,0,n){
if(c[i][0]!='.'&&c[i][1]!='.'&&c[i][2]!='.')FORE(j,0,3)ans+=c[i][j]-'0';
else {
if(c[i][0]=='.'&&c[i][1]!='.'&&c[i][2]=='.')single=max(single,c[i][1]-'0');
for(int j=0;j<3&&c[i][j]!='.';j++)a[i]+=c[i][j]-'0';
for(int j=2;j>=0&&c[i][j]!='.';j--)b[i]+=c[i][j]-'0';
}
}
FORE(i,0,n){
added=max(added,max(a[i],b[i]));
FORE(j,0,n)if(i!=j)added=max(added,a[i]+b[j]);
}
ans+=added;
return single>ans ? single : ans;
}
};