AtCoder が提供しているABC（AtCoder Beginner Contest）327 のE問題をC++とPythonで解いてみました。ABC327は、2023年11月4日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Maximize Rating（Difficulty : 1227）
問題はリンク先をご覧ください。
DPを使うことで解けました。AtCoder Problems による Difficulty は、1227 でした。
解答案
レート $R$ の定義は、問題文にも書いてある通り、以下となります。
$$R=\frac{\sum^k_{i=1}(0.9)^{k-i}Q_i}{\sum^k_{i=1}(0.9)^{k-i}}\; – \; \frac{1200}{\sqrt{k}}$$
右辺の第1項の分子だけが $Q_i$ に依存します。残りの式は、$k$ だけに依存します。この第1項の分子 $\sum^k_{i=1}(0.9)^{k-i}Q_i$ の最大値をDP（漸化式）で求めます。この式は、最新のコンテストの点はそのままで、それより前のコンテストは、1回毎に 0.9 を掛けて影響が少なくなっていくことを表しています。
dp[i][j] を i 回までに参加したコンテストから j 回コンテストを選んだ場合の最大値とします。dp には、以下の漸化式が成立します。
- dp[i][j] = dp[i-1][j] （$P_{i-1}$ を選ばない場合）
- dp[i][j] = 0.9 × dp[i-1][j-1] + Pi-1 （$P_{i-1}$ を選ぶ場合）
結果的に漸化式は、以下となります。
dp[i][j] = max(dp[i-1][j], 0.9 × dp[i-1][j-1] + Pi-1)
C++ プログラム例（ABC327E）
上記の漸化式をプログラムとして実装します。プログラムでは、$0 \leqq i < n$、$0 \leqq j \leqq i$ とします。このため漸化式は、16行目となります（添え字が1個ずれています）。
最終的な解答は、$1 \leqq i \leqq n$ に対して、レート $R$ を求めて、その最大値を出力します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; ++i) {
cin >> p[i];
}
vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
dp[i + 1][j + 1] = max(dp[i][j + 1], 0.9 * dp[i][j] + p[i]);
}
}
double result = -100000000.0;
double t = 1.0;
for (int i = 1; i <= n; ++i) {
result = max(result, dp[n][i] / t - 1200.0 / sqrt(i));
t = t * 0.9 + 1.0;
}
cout << fixed << setprecision(15) << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC327E）
Python 版も基本的な考え方は同じです。浮動小数点数は、f文字列で出力しています（16行目）。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
"""AtCoder Beginner Contest 327 E"""
n = int(input())
p = list(map(int, input().split()))
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(n):
for j in range(i + 1):
dp[i + 1][j + 1] = max(dp[i][j + 1], 0.9 * dp[i][j] + p[i])
result = -1.0 * 10**10
t = 1.0
for i in range(1, n + 1):
result = max(result, dp[n][i] / t - 1200.0 / (float(i) ** 0.5))
t = t * 0.9 + 1.0
print(f"{result:.15f}")最後に
コンテスト中は、「パフォーマンスが大きい方から考えて…」などで時間を失っていました。公式解説でDPという言葉が、目に入ってから問題の構造が分かりました。コンテスト中に気付けるようになりたいです。
引き続き ABC の問題を紹介していきます。
