ABC331 B問題（Buy One Carton of Milk）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）331 のB問題をC++とPythonで解いてみました。ABC331は、2023年12月2日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Buy One Carton of Milk（Difficulty : 182）

問題はリンク先をご覧ください。

ABC331 B問題 Buy One Carton of Milk

あり得るすべてのパック数を全探索して最小値を計算します。AtCoder Problems による Difficulty は 182 でした。

解答案

「平均が安いパックから買う」などの考え方もありますが、制約から計算量が間に合うなら、まずは全探索です。

間に合うなら、全探索！

C++ プログラム例（ABC331B）

買う卵の個数 $N$ の制約は、$1 \leqq N \leqq 100$ です。6個入りパック、8個入りパック、12個入りパックは、それぞれ多くとも $N$ パック買えば十分です。$100 \times 100 \times 100 = 10^6$ と計算量としては間に合うため、全探索して最小値を求めます。

具体的には、買った卵の個数が $N$ 個以上になる場合の最小値を求めます。単純な3重ループで全探索できます。以下が、C＋＋プログラムとなります。

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

#define INF (1 << 30)

int main()
{
	int n, S, M, L;
	cin >> n >> S >> M >> L;

	int result = INF;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j) {
			for (int k = 0; k <= n; ++k) {
				if (i * 6 + j * 8 + k * 12 >= n) {
					result = min(result, i * S + j * M + k * L);
				}
			}
		}
	}

	cout << result << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC331B）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 331 B"""
INF = 1 << 30
n, S, M, L = map(int, input().split())

result = INF
for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i * 6 + j * 8 + k * 12 >= n:
                result = min(result, i * S + j * M + k * L)

print(result)

こちらも「AC」と判定されました。

最後に

問題の本質とは関係ありませんが、問題文で買うのは卵（英文では eggs）ですが、問題タイトルは、”Milk” となっています。

引き続き ABC の問題を紹介していきます。