問題
http://community.topcoder.com/stat?c=problem_statement&pm=8215&rd=12176
逆三角形からなる数字の配列が与えられる。
高さが４のとき、1行目は数字が４つ、2行めは３つ、、、４行めは数字が１つになる。
また、各行について１つは数字がわかっているがその他の数字は？となりわかっていない。
ある位置の数字は、その上にある数字と右上にある数字の和の一桁目の数になる。
このとき、？の数字をすべて復元して求める。
解き方
一番下の行は１つ、つまりすべての数字が分かっているため、
すべての数字を復元することができる。
また、復元については下から上へ順に行っていけばよい。
ある行について調べるとき、その下の行はすべてわかっていることから
？２
３
のように上側の数字が？になる。
このとき、（３＋１０ー２）％１０が？の数になるので
このようにすべての？を求めてあげればよい。
コード
class RevealTriangle {
public: vector<string> calcTriangle(vector<string> q) {
int n=q.size();
for(int i=n-2;i>=0;i--){
while(1){
if(q[i].find('?')==string::npos)break;
for(int j=0;j<n-i;j++){
int cnt= (q[i][j]=='?') + (q[i][j+1]=='?');
if(cnt==1){
int y=0;
if(q[i][j]!='?')y=q[i][j]-'0';
else y=q[i][j+1]-'0';
int x=(q[i+1][j]-'0'+10-y)%10;
if(q[i][j]=='?')q[i][j]=x+'0';
else q[i][j+1]=x+'0';
}
}
}
}
return q;
}
};
public: vector<string> calcTriangle(vector<string> q) {
int n=q.size();
for(int i=n-2;i>=0;i--){
while(1){
if(q[i].find('?')==string::npos)break;
for(int j=0;j<n-i;j++){
int cnt= (q[i][j]=='?') + (q[i][j+1]=='?');
if(cnt==1){
int y=0;
if(q[i][j]!='?')y=q[i][j]-'0';
else y=q[i][j+1]-'0';
int x=(q[i+1][j]-'0'+10-y)%10;
if(q[i][j]=='?')q[i][j]=x+'0';
else q[i][j+1]=x+'0';
}
}
}
}
return q;
}
};