nodchipのTopCoder日記

■ AtCoder Regular Contest 043 06:01

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
24	nodchip	100 06:19	100 (1) 56:54	-	10 38:13	210 (1) 61:54

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

ツイートする