https://yukicoder.me/problems/no/698
解法
- bitDPを使うのが一般的な解法ですが、計算量が増えるものの、next_partial_permutationを使うこともできます。
- 標準関数ではありませんが、
next_permutation(v.begin(), v.end())する直前にreverse(v.begin()+middle, v.end())するだけなので、(next_combinationと違って)インラインで組み込むのは簡単です。 v.begin()からv.begin()+middleまでを(middle P sizeの)部分順列として使います。- ただし、ループが回るたびに、
v.begin()+middleからv.end()まではソートされていることが保証されています。この性質を利用することで、vからsize-middle個選んでから残りのmiddle個を総当たりしたのと同じことになるのです。 - ループ回数は14P7 = 17297280回です。
解答例
チームを作ろう２
- この解法であればこちらもループ内の加算とxorを入れ替えるだけで容易に解くことができます。
- cLay https://yukicoder.me/submissions/265093