kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

「M-SOLUTIONS プロコンオープン」に参加しました

投稿日:

コンテストページはこちら

結果

3完 [A(100), B(200), D(500)] 68:17 ペナルティ: 0
・順位: 725位 (Rated)
・パフォーマンス: 1498
・Rating変化: 1305 -> 1326 (+21) [Rating最高値]

各問題の解法

A問題 (100点)

提出詳細
N角形の内角の和は、180×(N-2) (度) です。
計算量 O(1)

int N;
cin >> N;
cout << (N - 2) * 180 << endl;

B問題 (200点)

提出詳細
入力で与えられた試合の勝利数 + 残った試合数(すべて勝った場合) が8以上の場合、YESを出力する
計算量 O(|k|)

string s;
cin >> s;
int cnt = 0;
for (int i = 0; i < (int)s.size(); i++) {
  if (s[i] == 'o') cnt++;
}
cout << (cnt + 15 - s.size() >= 8 ? "YES" : "NO") << endl;

D問題 (500点)

提出詳細
頂点を決めて、BFSで大きい順に数字を入れていくと最大値となる。
計算量 O(N^2)

int N;
cin >> N;
vector<vector<int>> graph(N, vector<int>());
for (int i = 0; i < N - 1; i++) {
  int a, b;
  cin >> a >> b;
  if (a > b) std::swap(a, b);
  graph[a - 1].push_back(b - 1);
  graph[b - 1].push_back(a - 1);
}

priority_queue<int> c;
for (int i = 0; i < N; i++) {
  int ci;
  cin >> ci;
  c.push(ci);
}

queue<int> q;
q.push(0);
vector<int> ans(N, -1);
ans[0] = c.top();
c.pop();
long long score = 0;
while (!q.empty()) {
  int p = q.front();
  q.pop();
  for (int x : graph[p]) {
    if (ans[x] > -1) continue;
    ans[x] = c.top();
    c.pop();
    score += std::min(ans[p], ans[x]);
    q.push(x);
  }
}
cout << score << endl;
for (int i = 0; i < N - 1; i++) {
  cout << ans[i] << " ";
}
cout << ans[N - 1] << endl;

感想

Cから解いて結局解けなかったので時間を無駄にしてしまいました。逆元も使いこなせるようになりたいです。

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。

CAPTCHA


関連記事

no image

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 53:22 ペナルティ: 1 (-> 58:22) ・順位: 321位 (Rat …

no image

「AtCoder Beginner Contest 128」に参加しました

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 72:50 ペナルティ: 4 (-> 92:00) ・順位: 896位 (Rated) ・パフォ …

no image

「AtCoder Beginner Contest 138」に参加しました

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 20:16 ペナルティ: 0 ・順位: 84位 (Rated内39位) [ABC …

no image

JOI 2020 / 2021 本選 参加記

JOI (第20回日本情報オリンピック)の本選に参加しました.146 点(100 – 0 – 12 – 34)で本選落ちでした. ARC や AGC にも OI に …

no image

「第3回 RCO日本橋ハーフマラソン 予選」に参加しました

コンテストページはこちら 結果:133位(A: 147位、B: 108位) A: 286,823点、B: 493,349点 予選突破はできませんでした。(ほぼ確実) 各問題の考察 A問題 (画像:in …