Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-02-08

FindingSquareInTable (SRM434 DIV1 Easy)

| 13:53 | FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - FindingSquareInTable (SRM434 DIV1 Easy) - TopCoder煮ブログ

本番では混乱したまま書き始めてうまく行かなかった問題。開始座標と増分の4重ループで素直に書けた。なんと…。

上位の人のソースを読んだ感想。

  • for のループを横に連ねてタブの階層を減らしたほうがよさそうだ。
  • perfect square かの判別は (int)sqrt(1.0*n) を2乗して n と比較すればよい。
    • 自分は sqrt して modf したけど一時変数がいるのがかっこ悪いし誤差が怖い。

以下、自分のソース。

class FindingSquareInTable {
public:
  int findMaximalSquare(vector <string> table) {
    int N = table.size();
    int M = table[0].size();

    int ret = -1;
    for(int x0 = 0; x0 < M; x0++){
      for(int y0 = 0; y0 < N; y0++){
        for(int xd = -9; xd <= 9; xd++){
          for(int yd = -9; yd <= 9; yd++){
            int x = x0;
            int y = y0;

            int num = 0;
            while(x >= 0 && y >= 0 && x < M && y < N){
              num *= 10;
              num += table[y][x] - '0';
              double tmp;
              if(modf(sqrt((double)num), &tmp) == 0.0){
                ret = max(ret, num);
              }

              if(xd == 0 && yd == 0) break;
              x += xd; y+= yd;
            }
          }
        }
      }
    }
    return ret;
  }
};

nishiohirokazunishiohirokazu2009/02/08 18:43mod系がダメな理由の一つはnが0になりうるって点かと。