この問題は最大流問題に帰着して解くことができます。

予め報酬は全てもらっておき、アチーブメントが未達成ならコストがかかると考えることで、コスト最小化の問題になります。以下、この問題を考えます。

条件「スキル \(i\) をレベル \(x\) 以上にする」に対応する頂点 \(S_{i,x}\) と、実績 \(j\) に対応する頂点 \(T_{j}\) を用意します。条件および実績と頂点を同一視します。このときコストは次のように定式化できます。

• 全ての \(i\) で \(S_{i,1}\) は達成済み
• \(x>1\) について \(S_{i,x}\) が達成済みならコスト \(C_i\)
• \(T_{j}\) が未達成ならコスト \(A_j\)
• \(S_{i,x}\) が未達成なら \(S_{i,x+1}\) は未達成 (\(\Leftrightarrow\) \(S_{i,x}\) が未達成かつ \(S_{i,x+1}\) が達成済みならコスト \(\infty\))
• \(S_{k,L_{j,k}}\) が未達成なら \(T_{j}\) は未達成 (\(\Leftrightarrow\) \(S_{k,L_{j,k}}\) が未達成かつ \(T_{j}\) が達成済みならコスト \(\infty\))

以上により問題は、コストが最小になるように頂点を「未達成」「達成済み」の2つの集合に分ける問題となり、最小カット問題に帰着されました。最小カット問題は最大流を求めるアルゴリズムを用いて解くことができます。

レベルの最大値を \(L\) として、頂点数 \(O(NL+M)\)、辺数 \(O(NL+NM)\) なので、全体として \(N,M\)に関する \(4\) 次の時間で解くことができます。leading term は \(L\) について \(2\) 次であり、十分高速に動作します。