AtCoder が提供しているABC（AtCoder Beginner Contest）315 のC問題をC++とPythonで解いてみました。ABC315は、2023年8月19日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Flavors（Difficulty : 321）
問題はリンク先をご覧ください。
2つ選んだ美味しさの最大値を求める問題です。AtCoder Problems による Difficulty は 321 でした。
解答案
いくつかシミュレーションしてみると、以下のことが分かります。
美味しさが最大のアイスクリームは片方の候補になる。
場合分けして考えます。
- 美味しさが最大のアイスクリームがひとつの場合
- 美味しさが次のアイスクリームを選んでいきます。味が異なればSnextを、味が同じであれば、Snext / 2を加えていきます。
- 美味しさが最大のアイスクリームは候補に入ります。仮に2番目と3番目のアイスクリームの味が異なれば、どちらかを美味しさが最大のアイスクリームと入れ替えて、より大きな満足度が得られるためです。味が同じでも、美味しさが最大のアイスクリームと入れ替えて、より大きな満足度が得ることができます。
- 美味しさが最大のアイスクリームが複数ある場合
- 味がすべて同じ場合は、美味しさがひとつの場合とほぼ同じになります。
- 異なる味がある場合は、2×Smax が最大値となります。
参考までにABC302D問題（Difficulty 682 解説）と考え方は似ています。ただし、この問題の方が簡単です。
C++ プログラム例（ABC315C）
上記の考察に基づいて、美味しさが最大のアイスクリームをソートして求めます。後は、すべての残りのアイスクリームとの満足度を求めて、その最大値が解となります。
ソートは、美味しさと味のpairで行い、美味しさをマイナスすることにより降順にソートしています（15、17行目）。演算はマイナスしています（22、24行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> f(n), s(n);
for (int i = 0; i < n; ++i) {
cin >> f[i] >> s[i];
}
vector<pair<int, int>> p;
for (int i = 0; i < n; ++i) {
p.push_back(make_pair(-s[i], f[i]));
}
sort(p.begin(), p.end());
int result = 0;
for (int i = 1; i < n; ++i) {
if (p[0].second != p[i].second) {
result = max(result, -(p[0].first + p[i].first));
} else {
result = max(result, -(p[0].first + p[i].first / 2));
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC315C）
Python版もC++のプログラムをそのまま移植しました。
"""AtCoder Beginner Contest 315 C"""
n = int(input())
f = [0] * n
s = [0] * n
for i in range(n):
f[i], s[i] = map(int, input().split())
p = []
for i in range(n):
p.append((-s[i], f[i]))
p.sort()
result = 0
for i in range(1, n):
if p[0][1] != p[i][1]:
result = max(result, -(p[0][0] + p[i][0]))
else:
result = max(result, -(p[0][0] + p[i][0] // 2))
print(result)こちらも「AC」と判定されました。
最後に
この問題は、最大の美味しさをもつアイスクリームが必ず候補になることは直感的に分かりましたが、強い自信が持てなくてD問題とE問題の内容を確認していました。
結果的に、えいや！という感じで提出してAC判定でした。解いた問題が増えていけば、このような迷いも減っていくと期待しています。
引き続き ABC の問題を紹介していきます。
