AtCoder が提供しているABC（AtCoder Beginner Contest）338 のC問題をC++とPythonで解いてみました。ABC338は、2024年1月27日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Leftover Recipes（Difficulty : 513）
問題はリンク先をご覧ください。
料理Aが作れる個数に対して全探索します。AtCoder Problems による Difficulty は 513 でした。
解答案
C++ プログラム例（ABC338C）
先に作ることができる料理Aの最大値 a_max を求めます（23ー30行目）。
料理Aを0個からa_max個まで増やして、残りの材料 r で料理Bが作れる個数 b_n を求めて最大値を求めます。コードとしては、a_max を求める 23ー30行目と b_n を求める 34ー42行目は、趣旨として、同じコードになっています。
計算量ですが、a_max の最大値は、106 となり、それぞれに対して最大10回のループが発生するため、合わせて 107 回程度となるため、間に合います。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define INF (1 << 30)
int main()
{
int n;
cin >> n;
vector<int> q(n);
for (int i = 0; i < n; ++i) {
cin >> q[i];
}
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> b(n);
for (int i = 0; i < n; ++i) {
cin >> b[i];
}
int a_max = INF;
for (int i = 0; i < n; ++i) {
int t;
if (a[i] > 0) {
t = q[i] / a[i];
a_max = min(a_max, t);
}
}
int result = 0;
for (int a_n = 0; a_n <= a_max; ++a_n) {
int b_n = INF;
for (int i = 0; i < n; ++i) {
int t;
int r = q[i] - a[i] * a_n;
if (b[i] > 0) {
t = r / b[i];
b_n = min(b_n, t);
}
}
result = max(result, a_n + b_n);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC338C）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 338 C"""
INF = 1 << 30
n = int(input())
q = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a_max = INF
for i in range(n):
if a[i] > 0:
t = q[i] // a[i]
a_max = min(a_max, t)
result = 0
for a_n in range(a_max + 1):
b_n = INF
for i in range(n):
r = q[i] - a[i] * a_n
if b[i] > 0:
t = r // b[i]
b_n = min(b_n, t)
result = max(result, a_n + b_n)
print(result)こちらも「AC」と判定されました。
最後に
「全探索を行う」という基本で解くことができました。
引き続き ABC の問題を紹介していきます。
