Hatena::Grouptopcoder

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

 | 

2014-08-30

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
 |