97. 今日解いた問題（2022.04.07）

仕事がかなり大変だったので、比較的解きやすい2問だけ…。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

問題一覧

A - Erase by Value (Diff: 265)
B - Dividing Subsequence (Diff: 1317)

自分の解法など

A - Erase by Value

最適な戦略を考察します。

辞書順最小ということは、なるべく前方の文字を小さくできればよいです。よって、前から順に見て、その文字を消したとき次に現れる文字が小さくなるのであれば、その文字を消すのが最適です。

計算量は $O(N)$ です。

B - Dividing Subsequence

倍数の $Q$ における位置を高速に求める方法を考える

まず、 $Q_j$ が $P_i$ の倍数となるような $j$ を高速に求める方法を考えます。

各整数が $Q$ のどのインデックスに存在するか前計算を行います。ここでは $Q_j \rightarrow j$ から生成される $N$ 要素の配列 $A$ を用意します。 $Q$ が順列という制約があるので、このような配列は必ず作れます。

ある整数 $m$ の倍数が $Q$ のどのインデックスに存在するかは、 $m$ の倍数を順に見て $A$ から取得すれば $O(N/m)$ で計算できます。操作としてはエラトステネスの篩と同じようなイメージです。 $P$ の全ての要素についてこの計算を行うと、調和級数が出てくることを考慮して $O(N \log N)$ であることが分かります。これは十分高速です。

このようにして作成した、整数 $m$ の倍数が存在する $Q$ のインデックスリストを $D_{m, i}$ とします。

最長部分列の求め方を考える

$P$ のインデックスを $i$ 、 $Q$ のインデックスを $j$ として $(i, j)$ のペア集合 $\{(i, D_{P_i, 1}), (i, D_{P_i, 2}), \dots\}$ を考えます。これは、問題の条件に合うインデックスのペア集合です。ここから適切な要素を選んで、最長部分列を求めたいです。これは最長増加部分列（LIS）の問題に似ていることに気付きます。

やりたいことは、このインデックスペア集合から以下の条件を満たすできるだけ大きな部分集合を得ることです。

【1】同じ $i$ を含まない
【2】 $i$ の昇順に並べると、 $j$ について狭義単調増加になっている

ここが最大のポイントですが、LIS の問題に帰着させることを考えてみます。【2】の条件から、 $j$ のみを並べて LIS を求めることを考えます。 $i$ の昇順に並べたいので、 $(D_{P_1, 1}, D_{P_1, 2}, D_{P_2, 1}, D_{P_3, 1}, D_{P_3, 2}, \dots)$ のような並べ方がよさそうです。ただし、何も考えず並べると【1】の条件を満たせなくなります。これは、 $D_{P_i}$ を降順に並べることで解決できます。なぜなら、同じ $i$ に対して降順に $j$ が並んでいるので、最長増加部分列を取るアルゴリズムで同じ $i$ から部分列を伸ばす操作が行われないからです。

わかりにくいので例 1 で考えます。 $P=(3, 1, 4, 2), Q=(4, 2, 1, 3)$ です。このとき、 $A=(3, 2, 4, 1), D_{1} = (1, 2, 3, 4), D_{2} = (1,2), D_{3} = (4), D_{4}=(1)$ です。これを LIS の問題に帰着させるための数列に置き直すと、 $( (4), (4,3,2,1), (1), (2,1) )$ になります。なお、わかりやすくするため $D_{i}$ ごとにカッコで括っていますが、実際は一次元配列です。ここから最長増加部分列を取ると、 $i, j$ ともに狭義単調増加を満たすようなものが得られるとわかります。