倒せる敵と薬の好きな方を選べるときは、敵を選んで損しません。なぜなら、敵を先に倒す事で、敵を倒した事による強さの強化分に薬の倍率がかかるためです。また、倒せる敵が複数いるとき、薬を取らない限りはどの敵を先に倒しても最終的な高橋君の強さは同じになります。

よって、倒せる敵は即座に倒すことが最適な戦略になります。薬がない場合は、プライオリティーキューなどを使って到達可能な頂点とそこにいる敵の強さを管理することで貪欲法により解くことができます。

薬がある場合を考えます。薬の個数を \(M\) とします。

薬を使う順序によって敵を倒せるタイミングが変わりますが、薬を使う順序を固定すれば最適な戦略は前述の通りの貪欲になります。つまり、薬を使う順序 \((x,y,z,\ldots)\) を固定したときの戦略は

• 薬を使わずに敵を倒せるだけ倒す
• 薬 \(x\) を取れるなら取る
• 薬を使わずに敵を倒せるだけ倒す
• 薬 \(y\) を取れるなら取る
• ……

となります。

よって、この問題は薬を取る順番 \(M!\) 通りを全探索することで解けます。しかしこの解法の時間計算量は \(O(M! N \log N)\) であるため、実行時間制限に間に合わせることは困難です。

順列を全探索すれば解ける問題で計算量を削減したいということはbitDPの出番です。

使って良い薬の集合を固定した時、どの敵を倒したかは高橋君の強さのみによって定まり、高橋君の強さが高くなると倒した敵の集合は単調に増大することから、

\(dp[S]= \) 使える薬の集合が \(S\) のときの高橋君の強さのありえる最大値

というようなDPをしたくなります。このdpはそのままでは情報が足りず、前の結果から次の結果を(十分高速に)計算することができません。シミュレーションを行う際のプライオリティーキューそのものもdpの値に持ってしまうことで、シミュレーションを続きから行う、つまり、各薬 \(x \in S\) に対して「使った薬の集合が \(S\) で、薬 \(x\) は最後に使う」というケースを \(dp[S\setminus\{x\}]\) から計算できるようになり、適切にDPテーブルを埋めることができるようになります。

計算量は \(O(M2^M N\log N)\) であり十分高速です。
「薬を使わずに敵を倒せるだけ倒す」の処理を関数化しておくと実装が楽です。

実装例(Python)
実装例(C++)
（解説はもらうDPで書いていますが、実装例は配るDPです）