問題

問題文

あなたは、冷蔵庫と電子レンジを買うために、とある家電量販店に来ました。
この家電量販店では、 $A$ 種類の冷蔵庫と $B$ 種類の電子レンジが販売されています。$i$ 番目 $(1 \le i \le A)$ の冷蔵庫の値段は $a_i$円であり、$j$ 番目 $(
1 \le j \le B)$ の電子レンジの値段は $b_j$ 円です。
また、あなたは $M$ 種類の割引券を所持しており、$i$ 番目 $(1 \le i \le M)$ の割引券では、$x_i$ 番目の冷蔵庫と $y_i$ 番目の電子レンジを同時に買うと、支払総額が $c_i$ 円安くなります。ただし、複数の割引券を同時に使うことはできません。
さて、あなたは冷蔵庫と電子レンジをちょうど $1$ 台ずつ買おうと思っています。かかる金額の最小値を求めてください。

制約

・入力は全て整数
・$1 \le A \le 10^5$
・$1 \le B \le 10^5$
・$1 \le M \le 10^5$
・$1 \le a_i,b_i,c_i \le 10^5$
・$1 \le x_i \le A$
・$1 \le y_i \le B$
・$c_i \le a_{x_i} + b_{y_i}$

収録されている問題セット

AtCoder Problems Boot camp for beginners Easy 100 [#024]

回答

回答1 (AC)

単純に考えると $A$ 種類の冷蔵庫と $B$ 種類の電子レンジの全ての組み合わせを調べたくなります。しかし、組み合わせは $AB \le 10^{10}$ 通りあるため、全てを調べると TLE になってしまいます。

割引券を使用しない場合、冷蔵庫と電子レンジも最も安い組み合わせは、最安値の冷蔵庫と最安値の冷蔵庫を買った場合です。このため、割引券を使用しない場合については、これ以外の組み合わせは必要ありません。

次に割引券を使用する場合、割引券は $M < 10^5$ 種類なので、それぞれの割引券を使った場合の合計金額を求めることが可能です。そこでそれぞれの合計金額を求めながら、最小値を調べていけば良いでしょう。コードは以下のようになりました。

hitachi2020b-1.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
  int A, B, M;
  cin >> A >> B >> M;

  int amin = INT_MAX;
  vector<int> a(A);
  for ( int i=0; i<A; i++ ) {
    cin >> a.at(i);
    amin = min( amin, a.at(i) );
  }
  
  int bmin = INT_MAX;
  vector<int> b(B);
  for ( int j=0; j<B; j++ ) {
    cin >> b.at(j);
    bmin = min( bmin, b.at(j) );
  }

  int pmin = amin+bmin;
  int x, y, c;
  for ( int i=0; i<M; i++ ) {
    cin >> x >> y >> c;
    pmin = min( pmin, a.at(x-1)+b.at(y-1)-c );
  }

  cout << pmin << endl;
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

前の記事 → AtCoderログ：0120 - ABC 092 B