A 問題
ある日を選んで問題を解くとき、その日の問題数が次の日の問題数よりも多い場合に選択します。ただし、n+1 日目は 0 問とする。
コードを見る
<code>
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> a, b;
void solve() {
cin >> n;
a.resize(n + 1);
b.resize(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
b.push_back(0);
int result = 0;
for (int i = 2; i <= n + 1; ++i) {
if (a[i - 1] - b[i] > 0) {
result += a[i - 1] - b[i];
}
}
cout << result << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
</code>
B 問題
与えられた条件に基づいて計算を行う。
コードを見る
<code>
#include <iostream>
using namespace std;
int n, a, b, c;
void solve() {
cin >> n >> a >> b >> c;
int total = a + b + c;
int w = n / total * 3;
int q = n % total;
if (q != 0 && q <= a) {
w++;
} else if (q != 0 && q <= a + b) {
w += 2;
} else if (q != 0) {
w += 3;
}
cout << w << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
</code>
C 問題
k が n に等しい場合、すべての問題を解くことができます。k が n-1 より小さい場合、どの問題も解けません。k が n-1 に等しい場合、解けない問題が存在しない場合のみ解けます。
コードを見る
<code>
#include <iostream>
#include <vector>
using namespace std;
int n, m, k;
vector<bool> can_solve(300005, false);
vector<int> problems, selected;
void solve() {
cin >> n >> m >> k;
problems.resize(m + 1);
selected.resize(k + 1);
for (int i = 1; i <= m; ++i) {
cin >> problems[i];
}
for (int i = 1; i <= k; ++i) {
cin >> selected[i];
can_solve[selected[i]] = true;
}
for (int i = 1; i <= m; ++i) {
if (k == n) {
cout << 1;
} else if (k < n - 1) {
cout << 0;
} else if (!can_solve[problems[i]]) {
cout << 1;
} else {
cout << 0;
}
}
cout << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
</code>
D 問題
二分探索を使用して、指定された範囲内の数を見つける。
コードを見る
<code>
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int n, x, y;
vector<int> values;
void solve() {
cin >> n >> x >> y;
values.resize(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> values[i];
}
sort(values.begin() + 1, values.end());
int result = 0;
for (int i = 1; i < n; ++i) {
int sum_without_i = accumulate(values.begin() + 1, values.end(), 0LL) - values[i];
int min_value = sum_without_i - y;
int max_value = sum_without_i - x;
if (max_value < values[i + 1]) continue;
if (min_value > values[n]) continue;
int left = i + 1, right = n;
while (left < right) {
int mid = (left + right) / 2;
if (values[mid] >= min_value) {
right = mid;
} else {
left = mid + 1;
}
}
int start = right;
left = i + 1, right = n;
while (left < right) {
int mid = (left + right + 1) / 2;
if (values[mid] <= max_value) {
left = mid;
} else {
right = mid - 1;
}
}
result += left - start + 1;
}
cout << result << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
</code>
E 問題
価格は a または b の配列から選ばれます。それぞれの価格に対して、販売量と不評数を計算し、条件を満たすかチェックします。
コードを見る
<code>
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
int n, k;
vector<int> a, b;
int max_profit = 0;
void evaluate(int price) {
int sales = n - (lower_bound(b.begin() + 1, b.end(), price) - b.begin() - 1);
int bad_reviews = sales - (n - (lower_bound(a.begin() + 1, a.end(), price) - a.begin() - 1));
if (bad_reviews > k) return;
max_profit = max(max_profit, sales * price);
}
void solve() {
cin >> n >> k;
a.resize(n + 1);
b.resize(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
max_profit = 0;
for (int i = 1; i <= n; ++i) {
evaluate(a[i]);
evaluate(b[i]);
}
cout << max_profit << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
</code>