「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から解いて結局解けなかったので時間を無駄にしてしまいました。逆元も使いこなせるようになりたいです。