Hatena::Grouptopcoder

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

 | 

2015-08-16

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

A - 点数変換

  • 最大値と最小値の差を調整するためにPを計算
  • そのあと平均を計算するためにQを計算
  • コーナーケースは全員が同じ点数かつB>0のとき
int main() {
	std::ios::sync_with_stdio(false);

  int N;
  double A, B;
  cin >> N >> A >> B;
  vector<double> S;
  REP(n, N) {
    double s;
    cin >> s;
    S.push_back(s);
  }

  double min = *min_element(ALL(S));
  double max = *max_element(ALL(S));
  if (max - min < EPS && B > 0) {
    cout << -1 << endl;
    return 0;
  }

  double P = B / (max - min);
  double Q = -accumulate(ALL(S), 0.0) * P / N + A;
  printf("%.20f %.20f\n", P, Q);
}

B - 難易度

  • DP苦手
  • これは蟻本に載っている累積和をとっておくとオーダーがひとつ下がるやつだと思う
  • とりあえず書いてみる
  • サンプルが合わない
  • 累積和取らないバージョンも書いてみる
  • なかなかサンプルが合わない
  • やっと合った…
  • 元のコードは初期化がバグっていたらしい
  • サンプル通った
  • 提出
  • AC
  • DP本当に苦手
typedef G<1000000007> GG;

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

  int N;
  cin >> N;
  vector<int> D;
  REP(n, N) {
    int d;
    cin >> d;
    D.push_back(d);
  }
  sort(ALL(D));

  //static GG dp[4][128 * 1024];
  //REP(i, 128 * 1024) {
  //  dp[0][i] = 1;
  //}

  //REP(i, 3) {
  //  REP(j, N) {
  //    REP(k, j) {
  //      if (D[k] * 2 <= D[j]) {
  //        dp[i + 1][j] += dp[i][k];
  //      }
  //    }
  //  }
  //}
  //cout << accumulate(dp[3], dp[3] + 128 * 1024, GG()).x << endl;

  vector<GG> dp(N, 1);
  vector<GG> acc(1);
  REP(n, N) {
    acc.push_back(dp[n] + acc.back());
  }

  REP(i, 3) {
    vector<GG> nextDp;
    for (const auto& d : D) {
      int index = distance(D.begin(), upper_bound(ALL(D), d / 2));
      nextDp.push_back(acc[index]);
    }
    vector<GG> nextAcc(1);
    REP(n, N) {
      nextAcc.push_back(nextDp[n] + nextAcc.back());
    }

    swap(dp, nextDp);
    swap(acc, nextAcc);
  }
  cout << acc.back().x << endl;
}

C - 転倒距離

  • 分かりませんでした

D - 引っ越し

  • 10点は全部試すだけ
  • TLE 10
  • 100点は分かりませんでした
int main() {
	std::ios::sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<int> P;
  REP(m, M) {
    int p;
    cin >> p;
    P.push_back(p);
  }
  P.resize(N);
  sort(ALL(P));

  int answer = 0;
  do {
    int sum = 0;
    for (int j = 0; j < N; ++j) {
      for (int i = 0; i < j; ++i) {
        sum += P[i] * P[j] * (j - i);
      }
    }
    MAX_UPDATE(answer, sum);
  } while (next_permutation(ALL(P)));
  cout << answer << endl;
}

結果

順位ユーザ名点数変換難易度転倒距離引っ越し得点 / Total
24nodchip100 06:19100 (1) 56:54-10 38:13210 (1) 61:54

目標の3完には届きませんでした。

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