2008-12-25
SRM404 Div1 Easy: RevealTriangle
覆面算的な問題、と思ったけどそう難しくない。逆三角形の下から解いて行ける。
class RevealTriangle { public: vector<string> calcTriangle(vector<string> questionMarkTriangle) { int rows=questionMarkTriangle.size(); //1-50 vector<vector<int> > v(rows); rep(row,rows){ v[row].resize(rows-row); rep(i,rows-row){ int c = questionMarkTriangle[row][i]-'0'; v[row][i] = (c < 0||9<c)?-1:c; } } for(int row=rows-1;row>=0;row--){ int l=rows-row; string qmt= questionMarkTriangle[row]; rep(z,l){ rep(i,l) { if (v[row][i]<0) { if (i>0 && v[row][i-1]>=0) { v[row][i] = (10 + v[row+1][i-1] - v[row][i-1])%10; } else if (i+1<l && v[row][i+1]>=0) { v[row][i] = (10 + v[row+1][i] - v[row][i+1])%10; } } } } } vector<string> result(rows,""); rep(row,rows){ stringstream ss; rep(i,rows-row) ss << (char)(48+v[row][i]); result[row] = ss.str(); } return result; } };