Hatena::Grouptopcoder

cou929のTopCoder日記

2010-06-26

SRM 473 div2 (過去問)

13:34

またもやアルゴリズム問題をやるのは久々です. やはりしばらくやらないと, 全然できなくなってしまいます. そろそろ再開させたいところです.

Easy - OnTheFarmDivTwo

鶴亀算を解くだけの問題. 探索範囲が小さいので, コンピュータらしく全探索でさくっとやりました.

class OnTheFarmDivTwo {
public:
  vector <int> animals(int heads, int legs) {
    vector <int> ret;
    int i;

    for (i=0; i<=heads; i++) {
      if (i * 2 + (heads - i) * 4 == legs) {
        ret.push_back(i);
        ret.push_back(heads-i);
        break;
      }
    }

    return ret;
  }
};

Medium - SequenceOfCommands

2次元平面上を動くコマンドが与えられる. コマンドを無限に繰り返したとき, 軌跡がループしているかどうかを判定せよ.

シミュレーションしてループを検出します. ループの検出には, コマンドの1ターンごとに, 初期位置に帰ってきているかどうかを調べます. 何ターンのコマンドをシミュレートするかについては, このコマンド体系では90度単位でしか曲がれないので, 最大4ターンまで調べればいいことになります.

つまらないバグで時間を費やしてしまいました. 今回のようにif文を列挙する場合は, ありえない値をハンドリングする(switch分のdefaultにあたる部分)ようにすれば, コードの間違いを発見しやすいのではないかと思いました.

class SequenceOfCommands {
public:
  string whatHappens(vector <string> commands) {
    string ret = "unbounded";
    int curx = 0, cury = 0;
    int dir = 0;  // N:0, E:1, S:2, W:3
    string command;
    int i, j;
    vector <pair <int, int> > path;
    
    for (i=0; i<commands.size(); i++)
      command += commands[i];

    for (i=0; i<4; i++) {
      for (j=0; j<command.size(); j++) {
        if (command[j] == 'S') {
          if (dir == 0)
            cury++;
          else if (dir == 1)
            curx++;
          else if (dir == 2)
            cury--;
          else if (dir == 3)
            curx--;
        } else if (command[j] == 'R') {
          dir = (dir + 1) % 4;
        } else if (command[j] == 'L') {
          if (--dir < 0)
            dir = 3;
        }
      }
      if (curx == 0 && cury == 0) {
        ret = "bounded";
        break;
      }
    }

    return ret;
  }
};

MarineideMarineide2012/07/10 10:43You've imrpesesd us all with that posting!

jzaxfxwjzaxfxw2012/07/12 13:042FEYpn <a href="http://tjkastiekpwv.com/">tjkastiekpwv</a>