HackerRank Zalando CodeSprint: Make Our Customers Happy
problem
商品が$3$種類ある。それぞれ在庫が$N_a, N_b, N_c$個ある。 注文が$N$個あって、それぞれの商品を高々$1$個まで要求する。 全て満たすことのできる注文の数の最大値を答えよ。
solution
Fulfill the given orders greedily, in the order of size from small. $O(N)$.
At first, fulfill the orders A
, B
and C
, while it’s possible.
Then, fulfill the orders A,B
, A,C
and B,C
, in certain optimal order.
There are $3! (= 6)$ ways to fulfill there orders so it can be searched by bruteforce.
Finally, fulfill the order A,B,C
.
implementation
#include <iostream>
#include <algorithm>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
template <class T> bool setmin(T & l, T const & r) { if (not (r < l)) return false; l = r; return true; }
using namespace std;
int main() {
int na, nb, nc; cin >> na >> nb >> nc;
int n; cin >> n;
int qa = 0;
int qb = 0;
int qc = 0;
int qab = 0;
int qbc = 0;
int qca = 0;
int qabc = 0;
repeat (i,n) {
string s; cin >> s;
bool a = s.find('A') != string::npos;
bool b = s.find('B') != string::npos;
bool c = s.find('C') != string::npos;
if ( a and not b and not c) ++ qa;
if (not a and b and not c) ++ qb;
if (not a and not b and c) ++ qc;
if ( a and b and not c) ++ qab;
if (not a and b and c) ++ qbc;
if ( a and not b and c) ++ qca;
if ( a and b and c) ++ qabc;
}
auto fulfill = [](int & acc, int & na, int & nb, int & nc, bool a, bool b, bool c, int cnt) {
if (a) setmin(cnt, na);
if (b) setmin(cnt, nb);
if (c) setmin(cnt, nc);
acc += cnt;
if (a) na -= cnt;
if (b) nb -= cnt;
if (c) nc -= cnt;
};
int ans = 0;
array<int,3> xs; repeat (i,3) xs[i] = i;
do {
int acc = 0;
int a = na;
int b = nb;
int c = nc;
fulfill(acc, a, b, c, 1, 0, 0, qa);
fulfill(acc, a, b, c, 0, 1, 0, qb);
fulfill(acc, a, b, c, 0, 0, 1, qc);
for (int x : xs) {
if (x == 0) fulfill(acc, a, b, c, 1, 1, 0, qab);
if (x == 1) fulfill(acc, a, b, c, 0, 1, 1, qbc);
if (x == 2) fulfill(acc, a, b, c, 1, 0, 1, qca);
}
fulfill(acc, a, b, c, 1, 1, 1, qabc);
setmax(ans, acc);
} while (next_permutation(xs.begin(), xs.end()));
cout << ans << endl;
return 0;
}