🗂

全国統一プログラミング王決定戦予選 | C - Different Strokes

1 min read

問題

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

解法

見た感じどのようにとればいいかわからないのでNが1~3までの時を考える。

なんとなく合計が高いのを取るのがよさそうな感じはする。

ここで高橋くんが取得するiの集合をS, 青木君が取得するiの集合をTとすると高橋君のポイントの総量は以下になる。

\sum_{i \in S} A_i - \sum_{i \in T} B_i

ここでSTは全体集合なので以下のように変形できる。

\sum_{i \in S} A_i + \sum_{i \in T} (A_i - A_i) - \sum_{i \in T} B_i
\sum A_i - \sum_{i \in T} (A_i + B_i)

高橋君も青木君も最適な手をうつとすると、高橋君が(A_i+B_i)の一番大きな順に取得していけば青木君が最小の得点となる。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  ll sumA = 0;
  vector<int> c(n);  // a, b, ab: a_i+b_i
  for (int i = 0; i < n; i++) {
    ll a, b;
    cin >> a >> b;
    c[i] = a + b;
    sumA += a;
  }
  sort(c.rbegin(), c.rend());
  for (int i = 1; i < n; i += 2) {
    sumA -= c[i];
  }
  cout << sumA << endl;
}

参考

https://atcoder.jp/contests/abc024/editorial

Discussion

ログインするとコメントできます