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 Grand Contest 033」に参加しました

コンテストページはこちら 結果 2完 [A(300), B(600)] 139:48 ペナルティ: 7 (139:48 -> 174:48) ・順位: 817位 (Rated) ・パフォーマンス: 1 …

no image

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

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

no image

競技プログラミングから身を引くことにしました

お詫び 競プロについては、既に復帰しています。記事を書いたからには心情の変化等をお伝えするべきかと思いますが、余裕ができてからにさせていただければと考えています。今後ともよろしくお願いします。 また、 …

no image

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

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 57:43 ペナルティ: 0 ・順位: 751位 (Rated) ・パフォーマンス: 1466 …

no image

「Tenka1 Programmer Beginner Contest 2019」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:53 ペナルティ: 0 ・順位: 8位 ・パフォーマンス: 1600 (Inner: 2556) ・Rat …