ソートしたやつがうまく出力されないです。。

Question

AtCoderの日立製作所社会システム事業部プログラミングコンテスト2020のB問題について質問がございます。
#問題文
あなたは、冷蔵庫と電子レンジを買うために、とある家電量販店に来ました。

この家電量販店では、
A種類の冷蔵庫とB種類の電子レンジが販売されています。
i番目( 1≤i≤A)の冷蔵庫の値段は
ai円であり、 j番目(1≤j≤B)の電子レンジの値段は bj円です。

また、あなたは M種類の割引券を所持しており、
i番目(1≤i≤M)の割引券では、 xi番目の冷蔵庫 と yi番目の電子レンジを同時に買うと、 支払総額が
ci円安くなります。ただし、複数の割引券を同時に使うことはできません。
さて、あなたは冷蔵庫と電子レンジをちょうど1台ずつ買おうと思っています。かかる金額の最小値を求めてください。

#制約
入力は全て整数
・1≤A≤10^5
・1≤B≤10^5
・1≤M≤10^5
・1≤ai,bi,ci≤10^5
・1≤xi≤A
・1≤yi≤B
・ci≤axi+byi
となっていまして自分は以下のようにコードを書きました。

#include <iostream>
#include <vector>
#include <algorithm>
#include <sort>

using std::cin;
using std::cout;
using std::endl;
using std::vector;

int main(){
  int A,B,M;
  cin >> A >> B >> M;
  vector<int> a(A);
  vector<int> b(B);
  vector<int> c(M);
  for (int i=0;i<A;++i) cin >> a[i];
  for (int j=0;j<B;++j) cin >> b[j];
  for (int i=0;i<M;++i) cin >> c[i];
  
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  
  int ans;
  for (int i=0;i<M;++i){
     ans=min(a[i]+b[i]-c[i],a[0]+b[0]);
  }
  cout << ans << endl;
}

これで提出したところWAとなってしまいました。aとbをソートしたので最安値の電子レンジと冷蔵庫を買うときor　i番目で割引券を使ったときで小さい方を出力しようとしたのですがうまく行きませんでした。原因がわかる方いらっしゃいましたら教えていただけると嬉しいです。よろしくお願い致します。

Answer 1

こちらの問題ですね。

B - Nice Shopping - AtCoder 日立製作所 社会システム事業部 プログラミングコンテスト2020

原因として少なくとも2つあります。

• 割引券のデータはxi yi ciと1行に3つの整数が入ったものがM個連なるものなので、

for (int i=0;i<M;++i) cin >> c[i]; のループでは正しくその組み合わせが取り出せません。

• 割引券の組み合わせxi, yi, ciは　xi番目の冷蔵庫(a) と yi番目の電子レンジ(b)を同時に買うと支払総額がci円安くなるものなので、aとbをソートしてしまったらそのオリジナルの並びが壊され、i番目という指定が無効になってしまいます。

※上記2つを考慮して作ったコードで3つのサンプルテストケースはパスしましたが、回答に挙げるのは控えておきます。AtCoderでユーザーさんらがACしたコードも参照できますし。

Comments

[cunwe]

dodox86さん、ご回答ありがとうございました。僕がそもそも問題文にそぐわないコードを書いていたのですね、気をつけます。もう一度考えてから他の方の回答を見て理解を深めていきたいと思います。