2023 年 10 月時点の AtCoder の一部言語環境ではライブラリとして高性能な数理最適化ソルバーを利用できます。 本問題のように、問題を混合整数線形計画問題などの一般的な形式の最適化問題に帰着させることが比較的容易で、言い換えた問題のスケールがそれほど大きくならない場合、その問題を汎用ソルバーに解かせることで、十分高速に解が得られる場合があります。本問題ではこの方針で AC が得られたので、以下で紹介します。

本問題を \(N\) 次元ベクトル \(x\) と \(M\) 次元ベクトル \(y\) に関する最適化問題として定式化します。 \(x_i\) は最終的なスキル \(i\) のレベルで、\(1 \le x_i \le 5\) を満たす整数です。また、 \(y_i\) はアチーブメント \(i\) を達成する場合に \(1\) 、しない場合に \(0\) をとる整数です。すると、アチーブメント \(i\) の達成に関するスキル \(j\) の制約条件は、不等式 \(x_j - L_{ij} y_i \ge 0\) として表せます。また、最大化したい値（目的関数）は、 \(\sum_{i=1}^M A_i y_i - \sum_{i=1}^{N} C_i(x_i - 1)\) と書き下せます。

結局本問題は

\[ \begin{array}{rl} \mathrm{maximize}_{x, y} \; & \sum_{i=1}^M A_i y_i - \sum_{i=1}^{N} C_i(x_i - 1) \\ \mathrm{s.t.} \; & x_i \in \{1, 2, 3, 4, 5 \} \quad (i = 1, \ldots, N)\\ & y_i \in \{0,1 \} \quad (i = 1, \ldots, M)\\ & x_j- L_{ij} y_i \ge 0 \quad (i = 1, \ldots, M, j = 1, \ldots, N) \end{array} \]

という整数計画問題に帰着され（なお実は \(x_i\) については整数制約は不要で \(1 \le x_i \le 5\) の上下限制約だけで十分です）、これは Python 環境の PuLP や SciPy ライブラリなどを利用することで（少なくとも本問題で用意されたテストケースに対しては）高速に解くことが可能です。

実装例：

• PuLP + CBC の使用例： https://atcoder.jp/contests/abc326/submissions/47050511
• SciPy + HiGHS の使用例： https://atcoder.jp/contests/abc326/submissions/47049840