連続部分列はつぎのような手法と相性が良い。また、部分列に関しても下の記事の手法のほうが良いものもあるだろう。
部分列は数列と文字列両方ある。
文字列の部分列の数え上げはけんちょん先生の
にある。
数列の部分列についてかく。
数列の部分列は、連続部分列の問題と違って一定のパターン化がしづらいと思われる。
というわけでこのページは出てきた解けなかったほぼすべてのパターンをまとめる。
ちなみに、数列の部分列は全くの空を1通りとして数えて、
長さNでは2^N通りある。(それぞれの番目について選ぶか選ばないかの2択)
数列の部分列は、連続部分列の問題と違って一定のパターン化がしづらいと思われる。
というわけでこのページは出てきた解けなかったほぼすべてのパターンをまとめる。
ちなみに、数列の部分列は全くの空を1通りとして数えて、
長さNでは2^N通りある。(それぞれの番目について選ぶか選ばないかの2択)
部分列の相補性
数列から部分列Aを生成すると、空の列も部分列として許容するなら、必ずAの含まれなかった要素を全て持つ部分列Bが形成される。これを部分列の相補性ということにする。（僕が今名付けました。）
この考えを利用すると、すべての部分列はペアをつくることができる。
例として、数列{1, 10, 100}なら
({}, {1, 10, 100}), ({1}. {10, 100}). ({10}, {1, 100}), ({100}, {1, 10})
となる。
({}, {1, 10, 100}), ({1}. {10, 100}). ({10}, {1, 100}), ({100}, {1, 10})
となる。
この考え方を持っておくと解ける問題があった。
AGC020 C(700) Median Sum
上記の考え方を利用すると、空の列も部分列として数えるなら、2^N / 2の計2^(N-1)ペアできるとわかる。
また、相補性があるのでお互いのペアの和はかならず、数列の前項の和になるとわかる。
例えば、{1, 10, 100}の数列のペアの１つとして({1, 100}, {10})が存在するけど、それらの和は1 + 100 + 10 == 111で数列の前項の和に等しい。
また、相補性があるのでお互いのペアの和はかならず、数列の前項の和になるとわかる。
例えば、{1, 10, 100}の数列のペアの１つとして({1, 100}, {10})が存在するけど、それらの和は1 + 100 + 10 == 111で数列の前項の和に等しい。
中央値というキーワードに対する操作として、要素を大きい方と小さい方にわけるというのがある。普段ならばどの要素をどう振り分ければいいのか困るが、今回は上記の考え方を利用すると都合よくペアになってる。よって、ペアのうちでの大きい方と小さい方に分けることを考える。
そうやって各ペアについて大きい方と小さい方に分けると、相補性の特徴として、大小がはっきりとわかれる。なぜならば、和が一定でかつ小さい方の大きい方の差がどんどん縮まり、最終的には境界条件となる二つのペアの和が同じになるためである。
そうやって各ペアについて大きい方と小さい方に分けると、相補性の特徴として、大小がはっきりとわかれる。なぜならば、和が一定でかつ小さい方の大きい方の差がどんどん縮まり、最終的には境界条件となる二つのペアの和が同じになるためである。
つまり、こう考えると、境界では二つの部分列ペアの和の差は0に一番近い状態になってる。
これは言い換えると、小さい方のペアは(全項の和)/2以下の最大、大きい方のペアは(全項の和)/2以上の最小になることである。
そしてこの問題は空の列を部分列としてみなさないため、中央値は大きい方のペアの一番小さいもの、つまり(全項の和)/2以上の最小のものである。
これは言い換えると、小さい方のペアは(全項の和)/2以下の最大、大きい方のペアは(全項の和)/2以上の最小になることである。
そしてこの問題は空の列を部分列としてみなさないため、中央値は大きい方のペアの一番小さいもの、つまり(全項の和)/2以上の最小のものである。
あとはこれを数え上げればよい。
boolのdp[i][j] := i項目まで見て、和がjが作れたかどうか
で動的計画法をすればよい。計算量はO(n^3)、2000^3である。
boolのdp[i][j] := i項目まで見て、和がjが作れたかどうか
で動的計画法をすればよい。計算量はO(n^3)、2000^3である。
まずいですね。でも動的計画法の手順としてはこれ以上計算量はおちません。
しかし計算するのは真偽の二値のDPなので、C++のbitsetを利用すれば64倍の定数倍高速が可能です！
しかし計算するのは真偽の二値のDPなので、C++のbitsetを利用すれば64倍の定数倍高速が可能です！
