Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2008-12-25

SRM404 Div1 Easy: RevealTriangle

| 18:04 | SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder SRM404 Div1 Easy: RevealTriangle - naoya_t@topcoder のブックマークコメント

覆面算的な問題、と思ったけどそう難しくない。逆三角形の下から解いて行ける。

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;
  }
};