AtCoder が提供しているABC（AtCoder Beginner Contest）317 のD問題をC++とPythonで解いてみました。ABC317は、2023年8月26日21:00に実施されました。
ABC316は欠番になりました。AtCoderからのお知らせはこちらです。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 President（Difficulty : 929）
問題はリンク先をご覧ください。
ナップサック問題と同じ趣旨の問題です。DPで解けます。AtCoder Problems による Difficulty は 929 でした。
解答案
ナップサック問題（より詳しく「0-1 ナップサック問題」）と捉えることができます。ナップサック問題は、複数の品物に対して、重さ（wi）と価値（vi）が与えられた場合に、ある重さで得る価値を最大化する品物の組み合わせや、ある価値を得るための重さを最小化する品物の組み合わせを求める問題です。
選挙区で勝つために鞍替えさせる人数（0人の場合もある）が重さに、その選挙区で得られる議席数が価値に対応します。この問題の場合、当選に必要な議席を得るために最小となる鞍替えさせる人数を求めることになります。
dp[i][j] は、i 番目の選挙区までを考えたときに j 議席得るために必要な鞍替えする最小の人数とします。$\sum_{i = 1}^N Z_i < 10^5$ という制約があるため、j の範囲も $10^5$ 以下となります。漸化式は、以下となります。
- dp[i + 1][j] = min (dp[i][j], dp[i][j – zi] + w)
上の式で、w は以下となります。
- xi > yi の場合は、すでに勝っているため、w = 0 となる。
- xi < yi の場合は、鞍替えする人数 w = (xi + yi) / 2 + 1 – xi となる。
漸化式の初期値は、以下となります。
2024/4/30補足 記事に記載の初期値が間違っていました。修正しました。
- dp[0][0] = 0、それ以外の dp[i][j] = 無限大 とします。
C++ プログラム例（ABC317D）
考察で考えた漸化式をプログラムに落としこみます。出力する解答は、dp[N][j]（j が過半数以上）の最小値となります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
#define INF (1ULL << 60)
int main()
{
int n;
cin >> n;
vector<int> x(n), y(n), z(n);
int z_sum = 0;
for (int i = 0; i < n; ++i) {
cin >> x[i] >> y[i] >> z[i];
z_sum += z[i];
}
vector<vector<ull>> dp(n + 1, vector<ull>(z_sum + 1, INF));
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= z_sum; ++j) {
int w;
if (x[i] > y[i]) {
w = 0;
} else {
w = (x[i] + y[i]) / 2 + 1 - x[i];
}
if (j - z[i] >= 0) {
dp[i + 1][j] = min(dp[i][j], dp[i][j - z[i]] + w);
} else {
dp[i + 1][j] = dp[i][j];
}
}
}
ull result = INF;
for (int j = z_sum / 2 + 1; j <= z_sum; ++j) {
result = min(result, dp[n][j]);
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC317D）
C++で実装した漸化式を Python に移植しました。
以下のプログラムは、「Python (CPython 3.11.4)」では、TLE判定となり、「Python (PyPy 3.10-v7.3.12)」で、AC判定となりました。
新ジャッジは、Python と PyPy の実行時間の差が大きくなったように感じます。ただ単にわたしの Python のプログラムが良くない書き方になっているかもしれませんが。
"""AtCoder Beginner Contest 317 D"""
INF = 2 ** 60
n = int(input())
x = [0] * n
y = [0] * n
z = [0] * n
z_sum = 0
for i in range(n):
x[i], y[i], z[i] = map(int, input().split())
z_sum += z[i]
dp = [[INF for j in range(z_sum + 1)] for i in range(n + 1)]
dp[0][0] = 0
for i in range(n):
for j in range(z_sum + 1):
if x[i] > y[i]:
w = 0
else:
w = (x[i] + y[i]) // 2 + 1 - x[i]
if j - z[i] >= 0:
dp[i + 1][j] = min(dp[i][j], dp[i][j - z[i]] + w)
else:
dp[i + 1][j] = dp[i][j]
result = INF
for j in range(z_sum // 2 + 1, z_sum + 1):
result = min(result, dp[n][j])
print(result)こちらも「AC」と判定されました。
最後に
ABC317は、最終的にABCEの4問を解くことができました。
D問題に取り組む時間も30分ほどありました。DPで解けそうなことは分かり、漸化式まで落とし込みましたがが、（多少、筋が悪いプログラムになって）WAを取り切ることができませんでした。終わってからナップザック問題とのコメントを見て解くことができました。
DPについて、あまり体系的に理解できていません。なにか工夫して整理してみます。
引き続き ABC の問題を紹介していきます。
