Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2014-08-30

Single Round Match 631 02:57 Single Round Match 631 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Single Round Match 631 - nodchipのTopCoder日記 Single Round Match 631 - nodchipのTopCoder日記 のブックマークコメント

今回はKawagiEditorに乗り換えてから初めての本格的なSRMでした。

Easy 250 TaroJiroGrid

  • 多分中央2行を白または黒に塗れば条件を満たせると思う
  • とういことは答えの最大値は2かな
  • なら反復深化で良さそう
  • Passed System Test
class TaroJiroGrid {
public:
  bool check(const vector <string>& grid) {
    int N = grid.size();
    REP(c, N) {
      char last = 0;
      int counter = 0;
      REP(r, N) {
        if (grid[r][c] == last) {
          if (++counter > N / 2) {
            return false;
          }
        }
        else {
          last = grid[r][c];
          counter = 1;
        }
      }
    }
    return true;
  }
  bool id(int remain, const vector <string>& grid, int next) {
    if (remain == 0) {
      return check(grid);
    }

    int N = grid.size();
    for (int row = next; row < N; ++row) {
      vector<string> g = grid;
      g[row] = string(N, 'W');
      if (id(remain - 1, g, row + 1)) {
        return true;
      }

      g = grid;
      g[row] = string(N, 'B');
      if (id(remain - 1, g, row + 1)) {
        return true;
      }
    }
  }
	int getNumber(vector <string> grid) {
    int N = grid.size();
    REP(depth, N + 1) {
      if (id(depth, grid, 0)) {
        return depth;
      }
    }
    return -1;
  }
};

Medium 500 CatsOnTheLineDiv1

  • 難しい・・・
  • DPっぽい気がするけどDP解けないから貪欲でできないかどうか考えてみる
  • とりあえず良さそうな戦略は
    • ねこさまはなるべく1箇所に1匹だけ配置する
    • なるべく左から1匹ずつ配置する
    • どうしてもダメな場合はなるべくぎゅうぎゅう詰めにする
    • 固める場所はなるべく右端にする
    • ギュウギュウ詰めのところになるべく更に詰める
  • ・・・
  • ねこさまごめんなさい
  • とりあえず書いてみる
  • やけにシンプル・・・
  • 出してみる
  • Passed System Test
  • 通った・・・
class CatsOnTheLineDiv1 {
public:
	int getNumber(vector <int> position, vector <int> count, int time) {
    int N = position.size();
    vector<pair<int, int> > cats;
    REP(i, N) {
      cats.push_back(MP(position[i], count[i]));
    }
    sort(ALL(cats));

    int answer = 0;
    int nextLineStart = INT_MIN;
    int lastPile = INT_MIN;
    REP(i, position.size()) {
      int pos = cats[i].first;
      int cnt = cats[i].second;
      int left = pos - time;
      int right = pos + time;

      if (left <= lastPile) {
        continue;
      }

      nextLineStart = MAX(nextLineStart, left);
      if (right - nextLineStart + 1 >= cnt) {
        nextLineStart = nextLineStart + cnt;
      }
      else {
        ++answer;
        lastPile = right;
      }
    }

    return answer;
	}
};

結果

oox 594.4 42位 1854->1965

Mediumがすんなり通ってくれたおかげでレートがかなり上がりました。最近練習していないのですぐに下がると思います。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140830
 |