AtCoder が提供しているABC（AtCoder Beginner Contest）360 C問題をC++とPythonで解いてみました。ABC360は、2024年6月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Move It
問題の詳細は、リンク先をご覧ください。
ある箱に入っている一番重い荷物を求めます。
解答案
箱の数と荷物の数は一致しています。また、ある箱の中に複数の荷物がある場合、軽い荷物から移動すればコストは小さくなります。このため、一番重い荷物がそれぞれの箱に残ります。この和を求めて、荷物の総和から引いた値が、求める答えになります。
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 の問題を紹介していきます。
