AtCoder

ABC327 E問題(Maximize Rating)を解く

AtCoder_ABC327_E

AtCoder が提供しているABC(AtCoder Beginner Contest)327 のE問題をC++とPythonで解いてみました。ABC327は、2023年11月4日21:00に実施されました。

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

E問題 Maximize Rating(Difficulty : 1227)

問題はリンク先をご覧ください。

ABC327 E問題 Maximize Rating

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 の問題を紹介していきます。

COMMENT

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

CAPTCHA