公式Editorialでは、尺取、包除原理が紹介されている。
indexを管理する方法。
まず、$X=Y$ の場合は別に処理する。
区間は $X$ が連続している箇所からしか選べない。$X$ が $n$ 個連続した箇所なら $\dfrac{n(n+1)}{2}$ 区間取れる。
ランレングス圧縮し、これを合計すればよい。
以下、$X \gt Y$ とする。また、「$X$ より大きかったり、$Y$ より小さい値」を総称して $Z$ と表現する。
以下の3つを整理する。
求めたいのは、$Z$ を含まず、$X$ と $Y$ を両方含む区間の個数。
ある位置 $i$ にある $X$ を含むと固定して、少なくとも $i$ から見て最も直近の前後いずれかの $Y$ は含む必要がある。
それさえ満たせば、$Z$ が出現するか、数列の端に到達するまで、左右独立に区間を伸ばすことができる。
つまり、$X$ ごとに以下を(存在すれば)求めて合計すればよい。
以降、説明の便宜上、数列の左右端 $A_0,A_{N+1}$ にも、$Z$ が存在するとする。
たとえば、(直前の $Y$, $X$) を含む区間なら、
# * * 注目中のX ... Z _ _ Y _ X _ _ Y _ _ X Z ... # 直前のY |-|-| 区間左端候補 3 |-|-|-|-|-|-| 区間右端候補 7 → 3x7=21 区間とれる
($X$, 直後の $Y$) を含む区間も同様にして数えられる。
複数の $X$ を含む区間は、それぞれの $X$ を固定したときに同じ区間を重複して数えてしまう。
これを避けるため、$X$ を固定する際は「固定した $X$ が、区間内の $X$ の中で一番左である区間だけを数える」ことにする。
また、その中でも、左の $Y$ と右の $Y$ を両方含む区間は重複してしまうため、 「($X$, 直後の $Y$) の区間を計算する場合は、直前の $Y$ を含まない区間だけを数える」ことにする。
これで重複をのぞける。
計算量は、$i$ から直前・直後の $Y$ や $Z$ の位置を求めるのに、 リスト y_idx、z_idxに対して二分探索を使うと $O(N \log{N})$ となる。
または最初のindexリストを作るときに、
みたいにしておくと、これは $O(N)$ で構築できるので、全体でも $O(N)$ となる。
最小費用流。ただし1回流して終わりではなく、追加で何回か流す。
所属と得意分野の種類数が150と少ない。これを頂点としたフローでも計算量的に大丈夫そう。
A B ,--->①--->①---, | `-_ | Ⓢ--->② '②---+-> Ⓣ | ,-' | |--->③' ③---| : : : :
こうすれば、各 $A_i,B_i$ を経由する流量は上限1に限定され、複数の流れが同じ $A_i,B_i$ を通ることがなくなる。
つまり、流量 $f$ 流せば、$f$ 本の流れはすべて別々の $A_i,B_i$ を通り、ドリームチームの条件を満たす。
またそのコストはチームメンバーの $X - C_i$ の合計値となる。
「メンバーの人数 × $X$ - 最小費用流の結果」とすれば、$C_i$ の合計に戻せる。
流量 $f$ が流せなくなったら、その直前 $f-1$ が、$N$ 人で作れるドリームチームの最大構成員数 $k$ となる。
流量 $3$ 流せば3人のドリームチームの強さの最大値が求まり、$4$ 流せば4人の(略)が求まる。
が、毎回新規にグラフを構築したりリセットしたりして、流量を $1,2,3,...$ と増やしながら調べるのは非効率。
最小費用流は、たとえば流量 $f$ を流し終えた後のグラフに対し、「さらに追加で $g$ 流す」ことができる。
この場合、流量 $f$ の結果からの増加分が結果となる。
なので、グラフは再構築やリセットせず、1ずつ追加で流すことを繰り返せばよい。
まず、順列(のように同じ要素を含まない数列)の転倒数を考えると、1回のswapによっては必ず奇数しか変化しない。
... 3 1 5 9 7 ...
3と7をswapする場合、その間にある数字は以下のいずれかだが、
どれをとっても、その数字と3,7との転倒数は「2減る」「2増える」「1増えて1減って、相殺されて0」のいずれかしかない。
また、3と7自体の転倒数は、swapによって1増えるか1減る。よって、全体では奇数の変化となる。
初期状態(転倒数0=偶数)から、奇数回の操作後は転倒数は奇数、偶数回なら偶数となる。
奇数回操作しても偶数回操作しても作れる並び順、というものは存在しない。
また、$K$ 回より少ない回数で達成できる並び順で $K$ と偶奇が同じものは、 適当に同じ要素に2回ずつ操作すれば回数を稼げるので、ちょうど $K$ 回でも達成可能となる。
よって、「その並び順を作るための最小操作回数」ごとに並び順の個数を数えることができれば、 そこから「$K$ 以下」かつ「$K$ と偶奇が一致する」ものの総和を取ることで、答えとなる。
「初期状態」と「$K$ 回の操作後」で色の並び順が同じならばよくて、途中経過は違っていてもよい。
とはいうもののこれは若干ミスリードっぽくて、今は「最小操作回数」を考えたいので、違う色をswapするのは無駄となる。
同じ色の中だけでswapすると考えてよい。
同色の中だけでswapが行われるとして、最小操作回数別に並び順の個数を数えたい。
よく、「順列 $P$ が与えられる。swapによって $1,2,...,N$ を $P_1,P_2,...,P_N$ に並べ替える最小操作回数を求めよ」みたいな問題がある。
これには、サイクルに分割する解法がよく用いられる。
サイクル毎に、サイクルサイズ-1の回数を要するので、その総和が答え。
ということは全体で考えると、長さ1のサイクルもサイクルとして考えて、 $N$ 個の数が「いくつのサイクルに分割されたか」によって $N-(サイクル数)$ が答えともいえる。
そして、$N$ 個の数を、$K$ 個のサイクルに(サイクル内の並び順も区別して)分ける方法の個数 $S_{n,k}$ は、 第1種スターリング数として知られている。
例えばある色の服を着た人が $m$ 人いたら、最小操作回数毎の並び順の個数は、以下のようになる。
色 | 人数 | 最小操作回数 | |||||
---|---|---|---|---|---|---|---|
0 | 1 | … | $a-1$ | … | $b-1$ | ||
色1の服を着た人 | $a$ | $S_{a,a}$ | $S_{a,a-1}$ | $S_{a,1}$ | |||
色2の服を着た人 | $b$ | $S_{b,b}$ | $S_{b,b-1}$ | $S_{b,b-a+1}$ | $S_{b,1}$ |
というのが仮に計算できたとして、ではこの2色を同時に考慮した最小操作回数毎の並び順はどうなるかというのは、これらの畳み込みによって表現できる。
最小操作回数 | ||||
---|---|---|---|---|
$0$ | $1$ | … | $b-a+2$ | |
色1の服を着た人 | $S_{a,a}$ | $S_{a,a-1}$ | ||
色2の服を着た人 | $S_{b,b}$ | $S_{b,b-1}$ | ||
2色を合わせて考慮 | $S_{a,a}S_{b,b}$ | $S_{a,a-1}S_{b,b}+S_{a,a}S_{b,b-1}$ | $S_{a,1}S_{b,1}$ |
他の色も、どんどん畳み込んでまとめていけばよい。
最終的に1つになった数列が、全体での「最小操作回数別の並び順の個数」となる。
畳み込み後の長さ=全体の最小操作回数の最大値は $N-1$ なので、長くなりすぎて計算量的にアウト、ということはない。
さて、先ほど、同色の人が $m$ 人いる場合の最小操作回数毎の並び順 $[S_{m,m},S_{m,m-1},...,S_{m,1}]$ は計算できた前提だったが、ここも問題がある。
スターリング数はDP的に求めるしか無く(多分)、一般的な方法では $S_{m,○}$ を求めるには $O(m^2)$ かかる。
$m$ は最大 $N$ になり得るので、これだとTLE。
しかし、スターリング数にはもう一つ、便利な表現の仕方があって、
従って、ここでも畳み込みが使える。
今回は、スターリング数の $n$ 段目を逆並びにしたものを求めたいので、同色の人数 $m$ に対して
を全て畳み込むと、求めたい数列となる。
畳み込みで結合するに従って数列サイズはだんだん肥大化する。
小さい方から結合するようにしていく(マージテク)ことによって、計算量を抑えられる。