アルゴリズムの力を使って 25 ms で本番 20 位相当のスコア を取ることができたので, これを紹介します.

ハンガリアン法を使用します. ハンガリアン法は, \(N + M\) 頂点 \((N ≥ M)\) の二部グラフの最大重みマッチングを \(O(NM^2)\) 時間で求めるアルゴリズムです.

\(T = 26\) をコンテストの種類数, \(W\) を整数のパラメータとします.
アルゴリズムは以下の通りです.

• \(i = 1, …, D\) について, \(i\) 日目のコンテストを以下のように決定する.
  • 今後 \(W\) 日間で同じコンテストを複数回開催しないと仮定し, \(W\) 日後の満足度を最大化するようなコンテストの開き方を求める.
    これは, ハンガリアン法により \(O(TW^2)\) 時間で求められる.
  • 上の解における \(i\) 日目のコンテストを採用する.

\(W = 20\) で最もスコアが良くなり, 121627924 点 を獲得できます.