らての精進日記

修行をします

aoj2318:Set-constructing Witch

解法

ベルマンフォード法をやる。
i番目の魔女を作るための最小のグリーフシードの数をF[i]とおき、Fを更新していく。

ここで問題となるのが、g番目の魔女がs1,...,sc番目の魔女から作られるとき、
F[g]をF[s1],...,F[sc]から求める方法である。

当然、gを作るためにはs1,...,scをすべて所持していないといけない。
どのような順番でsを作っていくのかを考える。

まず、いくつかのsを並列的に作る必要ない:
ある魔女a,bを並列に作ることを考える(並列に作るが、aのほうが少し早く準備を始めたとする)
bを作る過程で、常にaを作るためにいくつかのグリーフシードが埋まっている。
bを作り始める前にaを完成させておくと、bを作るときには1つしかa用のグリーフシードが埋まっていない。
よって同時に作業する必要はない。

これで、sたちを作る順番のみが重要になった。
当然c!通りの順列はすべて試せない。
ただ、どう考えてもFが大きい順に作ればいいので、解ける。F[g]の計算は適当にやる。

「同じ種類の魔女を同時に複数のグリーフシードに入れることは出来ない」という条件は、
Fが大きい順に作っていくことでクリアできるので、考える必要はない

コード