【競プロ精進ログ】ABC125-B

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。

これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC125-B「Resale」です。

ポイント

一瞬だけbit全探索を考えた問題でしたが，もっと単純に解くことができます。まず，最大化したい対象は$X-Y$です。言い換えれば，できるだけコスパの良い宝石を買っていけばよいということです。ここでいう「コスパの良い宝石」とは，コストよりも価値の方が大きい宝石のことを指します。

つまり，この問題の解法は，「$V_j > C_j$」となる$j$番目の宝石に関して$\sum_{j}(V_j - C_j)$を求めればOKです。ポイントは，全探索は全探索でも，bit全探索は$O(2^N)$かかってしまうのに対して，今回の解法は$O(N)$で実現することができるという点です。

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N;
int V[30];
int C[30];

int main(){
  cin >> N;
  rep(i, N) cin >> V[i];
  rep(i, N) cin >> C[i];
  int ans = 0;
  // もし「コスパが良い」宝石であれば総和に加えていく
  rep(i, N){
    if (V[i] - C[i] > 0) ans += V[i] - C[i];
  }
  cout << ans << endl;
}