AtCoder

ABC360 C問題(Move It)を解く

AtCoder_ABC360_C

AtCoder が提供しているABC(AtCoder Beginner Contest)360 C問題をC++とPythonで解いてみました。ABC360は、2024年6月30日21:00に実施されました。

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

C問題 Move It(Difficulty : 36)

問題の詳細は、リンク先をご覧ください。

ABC360 C問題 Move It

ある箱に入っている一番重い荷物を求めます。AtCoder Problems による Difficulty は 36 でした。

解答案

箱の数と荷物の数は一致しています。また、ある箱の中に複数の荷物がある場合、軽い荷物から移動すればコストは小さくなります。このため、一番重い荷物がそれぞれの箱に残ります。この和を求めて、荷物の総和から引いた値が、求める答えになります。

C++ プログラム例(ABC360C)

配列 m の添え字は荷物の箱の場所、値はその箱に入っている一番重い荷物とします。荷物の総和を求めておき(23-26行目)、それぞれの箱に入っている一番重い荷物の重さを引いています。これで移動する荷物の重さの合計が分かります。

以下が、C++プログラムです。

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

typedef long long int ll;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	vector<ll> w(n);
	for (int i = 0; i < n; ++i) {
		cin >> w[i];
	}

	vector<ll> m(100001);
	for (int i = 0; i < n; ++i) {
		m[a[i]] = max(m[a[i]], w[i]);
	}

	ll result = 0;
	for (int i = 0; i < n; ++i) {
		result += w[i];
	}
	for (auto e : m) {
		result -= e;
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC360C)

Python版も基本的な考え方は同じです。組込み関数 sum によりすっきりと書けています。以下がプログラムです。

"""AtCoder Beginner Contest 360 C"""
n = int(input())
a = list(map(int, input().split()))
w = list(map(int, input().split()))

m = [0] * (10 ** 5 + 1)
for i in range(n):
    m[a[i]] = max(m[a[i]], w[i])

result = sum(w) - sum(m)

print(result)

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

最後に

C問題としては解きやすい問題でした。

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

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA