[1]条件の言い換え

条件に \(1\) から \(K\) の番号を付けます。

このとき、条件 \(i\) は \(A_{P_i} \le X-1 \iff A_{Q_i} \le Y-1\) かつ \(A_{P_i} \le X \iff A_{Q_i} \le Y\) と同値です。以降、\(A_{P_i} \le X_i \iff A_{Q_i} \le Y_i\) という条件が複数あるものとします。

[2]最適解の構築

はじめ、\(A=(1,1,\dots,1)\) とします。

その後、\(A_{P_i} > X_i\) であれば \(A_{Q_i}\) を \(\max(A_{Q_i},Y_i+1)\) で更新することを繰り返します。\(A_{Q_i} > Y_i\) である場合も同様です。

上記の操作を更新がなくなるまで行い、最終的に全要素が \(M\) 以下であるならばその状態の \(A\) が総和の最小値を与えます。そうでないならば条件を全て満たす数列は存在しません。

証明は、もし \(A_{P_i}>X_i\) であれば \(A_{P_i} \le X_i \iff A_{Q_i} \le Y_i\) を満たすためには \(A_{Q_i}>Y_i\) とするしかないことから導かれます。

[3]まとめ

上記のシミュレーションは、適切に実装することにより \(\mathrm{O}(N+K)\) で行うことができます。

よって、この問題を \(\mathrm{O}(N+K)\) で解くことができます。