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がすんなり通ってくれたおかげでレートがかなり上がりました。最近練習していないのですぐに下がると思います。

AtCoder Regular Contest 028 22:38 AtCoder Regular Contest 028 - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - AtCoder Regular Contest 028 - nodchipのTopCoder日記 AtCoder Regular Contest 028 - nodchipのTopCoder日記 のブックマークコメント

A - 小石を取るゲーム

  • 割った余りで場合分け
  • ・・・
  • WA
  • ・・・
  • うぎゃああああああああああああああああああああああああああああああああああああ
  • 数字書き間違えたあああああああああああああああああああああああああああああああ
  • 落ち着いて書き直す
  • AC
  • ふぅ
int main() {
	std::ios::sync_with_stdio(false);

  int N, A, B;
  cin >> N >> A >> B;
  N %= A + B;
  if (0 < N && N <= A) {
    cout << "Ant" << endl;
  }
  else {
    cout << "Bug" << endl;
  }
}

B - 特別賞

  • 毎回ソートするのはTLE
  • priority_queueでK+1番目に若い人を随時削除していく感じにすればO(N log N)で行けそう
  • AC
int main() {
	std::ios::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  priority_queue<pair<int, int> > q;
  REP(i, N) {
    int x;
    cin >> x;
    q.push(MP(x, i + 1));

    if (q.size() > K) {
      q.pop();
    }
    if (q.size() == K) {
      cout << q.top().second << endl;
    }
  }
}

C - 高橋王国の分割統治

  • ある町に首都を置いたら、集合はその町の子ノードを根とする部分木と、元の根からある町以下を取り除いた部分木に別れるのか・・・
  • ならば、自分自身以下のノードの個数を各ノードに持たせれば線形で行ける
  • AC
int main() {
  std::ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<vector<int> > graph(N);
  for (int n = 1; n < N; ++n) {
    int p;
    cin >> p;
    graph[p].push_back(n);
  }

  vector<int> sizes(N);
  for (int n = N - 1; n >= 0; --n){
    int size = 1;
    for (const auto& child : graph[n]) {
      size += sizes[child];
    }
    sizes[n] = size;
  }

  REP(n, N) {
    int answer = N - sizes[n];
    for (const auto& child : graph[n]) {
      MAX_UPDATE(answer, sizes[child]);
    }

    cout << answer << endl;
  }
}

D - 注文の多い高橋商店

  • 10点は毎回DPしてk番目だけ固定にするのかな? O(NM^2Q)
  • 30点は前と後ろからDPして、K番目の隣の列の値を畳み込む感じ? O(NM^2 + QM)
  • TLE 30
  • 80点はどうするんだろう・・・
  • DPの漸化式の形が数列の部分和を取る形になっているから、各列について部分和を求める形にしておけば良さそう
  • O(NM + QM) かな?
  • TLE 80
  • あとは分からないや・・・
const int MAX_SIZE = 2048;

int main() {
  std::ios::sync_with_stdio(false);

  int N, M, Q;
  cin >> N >> M >> Q;
  vector<int> a;
  REP(n, N) {
    int value;
    cin >> value;
    a.push_back(value);
  }

  // [何番目+1の商品まで][何個選んだ] = 何通り
  vector<vector<g> > dp1(MAX_SIZE, vector<g>(MAX_SIZE));
  dp1[0][0] = 1;
  REP(n, N) {
    vector<g> sum;
    sum.push_back(0);
    REP(i, MAX_SIZE) {
      sum.push_back(sum.back() + dp1[n][i]);
    }

    REP(dst, MAX_SIZE) {
      dp1[n + 1][dst] = sum[dst + 1] - sum[MAX(0, dst - a[n])];
    }

    //REP(dst, MAX_SIZE) {
    //  for (int src = MAX(0, dst - a[n]); src <= dst; ++src) {
    //    dp1[n + 1][dst] += dp1[n][src];
    //  }
    //}
  }

  vector<vector<g> > dp2(MAX_SIZE, vector<g>(MAX_SIZE));
  dp2[N][0] = 1;
  for (int n = N - 1; n >= 0; --n) {
    vector<g> sum;
    sum.push_back(0);
    REP(i, MAX_SIZE) {
      sum.push_back(sum.back() + dp2[n + 1][i]);
    }

    REP(dst, MAX_SIZE) {
      dp2[n][dst] = sum[dst + 1] - sum[MAX(0, dst - a[n])];
    }
  }

  REP(q, Q) {
    int k, x;
    cin >> k >> x;

    g answer;
    for (int left = 0; left + x <= M; ++left) {
      int right = M - left - x;
      answer += dp1[k - 1][left] * dp2[k][right];
    }
    cout << answer.x << endl;
  }
}

結果

順位ユーザ名小石を取るゲーム特別賞 高橋王国の分割統治注文の多い高橋商店得点 / Total
12 nodchip 100 (1) 02:34 100 06:37100 16:08 80 (1) 52:56 380 (2) 62:56
トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20140830
 |