🗂

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

2020/12/27に公開

競プロ

tech

問題

解法

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

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

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

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

ここで $S$ と $T$ は全体集合なので以下のように変形できる。

\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;
}

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

問題

解法

コード

参考

Discussion