cou929のTopCoder日記

SRM382 div2 (過去問)

11:47

以前同じ問題を解いていたんですがもう一度.

Easy - ContiguousSubsequences

問題文は省略. ループカウンタ用の変数を間違えないようにiやjでなくべつの名前をつけてやってみたんですが, 変数の名前間違いはおこらなかったものの, やはりループの境界条件を考えるのに手間取って時間がかかってしまいました. また平均が0の場合がありえることを考慮できていなかったので, システムテストに落ちてしまいました. 問題のConstraintsと関数の定義域・値域をちゃんと確認する癖をつける必要がありそうです.

class ContiguousSubsequences {
public:
  vector <int> findMaxAverage(vector <int> a, int K) {
    vector <int> ret(2, 0);
    double avg = -1;

    for (int len=a.size(); len>=K; len--) {
      for (int pos=0; pos<=a.size()-len; pos++) {
        int sum = 0;
        for (int i=pos; i<pos+len; i++)
          sum += a[i];
        if (avg < (double)sum/(double)len) {
          avg = (double)sum/(double)len;
          ret[0] = pos, ret[1] = pos + len - 1;
        }
      }
    }

    return ret;
  }
};

Medium - CollectingRiders

問題文は省略. for文をコピペしたところで, 変数名を書きなおすのを忘れていて, そのバグ取りで時間を使ってしまいました. やはりコードのコピペは危険なので, こういう部分のタイプ量削減には, エディタの補完機能やマクロで対応すべきです. また到達可能・不可能の判定(-1を返すかどうか)を考える際にすこし混乱してしまって, 時間をくってしまいました. 最終的には, -1を返すようなケースでは解がかならず定数INFを超えるようにしました.

class CollectingRiders {
public:
  int minimalMoves(vector <string> board) {
    const int INF = 100000;
    int ret = INF;
    int steps[board.size()][board[0].size()];
    int dirx[8] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int diry[8] = {-1, 1, 2, 2, 1, -1, -2 ,-2};

    for (int row=0; row<board.size(); row++)
      for (int col=0; col<board[0].size(); col++) {
        queue <pair <int, int> > q;
        for (int i=0; i<board.size(); i++)
          for (int j=0; j<board[0].size(); j++)
            steps[i][j] = INF;
        q.push(make_pair(row, col));
        steps[row][col] = 0;

        while (!q.empty()) {
          pair <int, int> cur = q.front();
          q.pop();
          int cur_row = cur.first, cur_col = cur.second;

          for (int i=0; i<8; i++) {
            int next_row = cur_row + dirx[i], next_col = cur_col + diry[i];
            if (0 <= next_row && next_row < board.size() && 0 <= next_col && next_col < board[0].size() && steps[next_row][next_col] == INF) {
              steps[next_row][next_col] = steps[cur_row][cur_col] + 1;
              q.push(make_pair(next_row, next_col));
            }
          }
        }

        int number_of_step = 0;
        for (int i=0; i<board.size(); i++)
          for (int j=0; j<board[0].size(); j++)
            if (board[i][j] != '.')
              number_of_step += (steps[i][j] == INF) ? INF : ceil((double)steps[i][j] / (double)(board[i][j] - '0'));

        ret = min(ret, number_of_step);
      }

    if (ret >= INF) ret = -1;

    return ret;
  }
};