概要
4/27（日）に実施のABC403のD問題には、C問題までを40分以内で解き終えた後、残り1時間をフルに使って挑戦しました。コンテスト終了１分前に何とかコードを提出したものの、実行結果は、RE（ランタイムエラー）でした。コンテスト終了後に自分でデバッグを試み、2つのバグを修正したものの結局WA（不正解）は解消せず、特定の入力パターンでエラーが発生する原因を突き止められませんでした。ランダムテストを繰り返してようやく例外ケースを発見するも、そこで修正を断念。代わりに公式の解説と解説動画を視聴し、正しい解法を理解したうえで再度コーディングし、無事AC（正解）を獲得しました。
問題
解法の流れ
ACに至ったアルゴリズムは、以下のステップです。
-
度数分布を作成
入力配列aの各値の出現頻度をカウントする。 -
幅 d=0 の場合
幅が0の場合は、各値の度数から1を引いたものをすべて合計して返す。 -
幅 d≥1 の場合
-
度数分布を「幅 d」ごとに飛ばし取り出し、新しいリスト
arrayを作成する。 -
arrayの要素を選ぶ際、隣り合うインデックスを同時に選ばないようにしつつ、
残した度数の和を最大化するために動的計画法（DP）を用いる。
-
-
開始位置をずらして繰り返し
リストarrayのスタート位置を 0 から d−1 まで変えながら、上記手順を計 d 回実施。 -
最終結果の計算
元の度数分布の合計度数 ー 各arrayで選ばれた要素の度数の最大和 を答えとして出力。
特にステップ3の“隣接項目を同時に残さないDP”の組み方がポイントでした。
ソースコード
#include <vector>
#include <algorithm>
using ll = long long;
static const int MAX_B = /* 適宜定義 */;
int solve(ll n, ll d, const std::vector& a) {
// 度数分布を作成
std::vector b(MAX_B);
for (int i = 0; i < n; ++i) {
b[a[i]]++;
}
// 幅 d=0 の特別処理
if (d == 0) {
ll ans = 0;
for (int i = 0; i < MAX_B; ++i) {
if (b[i] >= 2) {
ans += (b[i] - 1);
}
}
return ans;
}
// d > 0 の場合
ll ans = 0;
for (int start = 0; start < d; ++start) {
// d 間隔で飛ばし取り出すリストと総和
std::vector arr;
ll total = 0;
for (int i = start; i < MAX_B; i += d) {
arr.push_back(b[i]);
total += b[i];
}
// 隣接しない要素の和を DP で最大化
ll prev = 0, curr = arr.empty() ? 0 : arr[0];
for (size_t i = 1; i < arr.size(); ++i) {
ll tmp = curr;
curr = std::max(curr, prev + arr[i]);
prev = tmp;
}
ans += (total - curr);
}
return ans;
}
振り返り・気づき
- DPの練習不足：d飛ばしで、隣接する度数を消していく際の考え方の整理ができず、ＤＰを使うまでに考えが至らなかった。ＤＰについての典型問題を解くべき。（解説動画で、問題 - Educational DP Contest / DP まとめコンテスト や、アルゴ式を紹介）
-
問題文の条件見落とし：度数分布の配列サイズをｎとしていたが、100000としなければならなかった。また、ａの値も、1以上しか考慮しておらず、０も考慮に入れるべきだった。
-
ランダムテスト：ランダムテストは想定外の境界ケースでのバグ発見に有効だった。ランダムテストのコーディングも１０分ほどで組めるようになる必要あり。
-
解説動画：実装パターンとDP設計の解説が非常にわかりやすく、理解が飛躍的に深まった。
コメントやアドバイス、大歓迎です！