AtCoder が提供しているABC（AtCoder Beginner Contest）318 のC問題をC++とPythonで解いてみました。ABC318は、2023年9月2日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Blue Spring（Difficulty : 400）
問題はリンク先をご覧ください。
周遊パスを購入するセット数ごとに料金の合計を求めて、その最小値が解となります。AtCoder Problems による Difficulty は 400 でした。
解答案
周遊パスはD枚セットで販売されています。このセット数について、0セット（周遊パスを使わない）から、N ÷ D の商を切り上げたセット数まで料金の合計を調べます。
また、通常料金が高い順に周遊パスを適用していきます。演算の重複を避けるため、最初に通常料金の合計を求めて、その合計から料金が高い順番にD個ずつ引いていきます。
C++ プログラム例（ABC318C）
以下が、プログラムの補足です。
- 配列 f に通常料金を読み込み、降順にソートする（13ー17行目）。合わせて通常料金の合計 sum を求めておく。
- 変数 result の初期値を sum とする。これは周遊パスを使わない場合に該当する。
- 周遊パスを1セットからN/Dセットまで購入したときの料金を求める。周遊パスは、通常料金が高い方から適用する。演算としては sum から引いていく（23ー25行目）。
- 最後に、N が D で割り切れない場合の料金を求める（29ー30行目）。
最後に料金の最大値 result を出力します。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int main()
{
int n;
ull d, p;
cin >> n >> d >> p;
vector<ull> f(n);
ull sum = 0;
for (int i = 0; i < n; ++i) {
cin >> f[i];
sum += f[i];
}
sort(f.begin(), f.end(), greater<ull>());
ull result = sum;
int index = 0;
for (int i = 1; i <= n / d; ++i) {
ull cost = i * p;
for (int j = 0; j < d; ++j) {
sum -= f[index];
++index;
}
result = min(result, cost + sum);
}
if (n % d != 0) {
result = min(result, ((n / d) + 1) * p);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC318C）
Python 版も基本的な考え方は同じです。変数名 sum は、組込み関数と同名であるため、s に変更しました。以下となります。
"""AtCoder Beginner Contest 318 C"""
n, d, p = map(int, input().split())
f = list(map(int, input().split()))
s = sum(f)
f.sort(reverse=True)
result = s
index = 0
for i in range(1, n // d + 1):
cost = i * p
for j in range(d):
s -= f[index]
index += 1
result = min(result, cost + s)
if n % d != 0:
result = min(result, (n // d + 1) * p)
print(result)こちらも「AC」と判定されました。
最後に
この問題は、最初DPを適用しようとして四苦八苦していました。周遊パスを購入するセット毎に料金を求めることに気づいて解くことができました。問題を解く量を増やして実力を上げれば、早く気づけるようになるでしょうか。
引き続き ABC の問題を紹介していきます。
