ARC230 B - Chmax and Chmin

考え方

問題で言っている操作の内容は、以下のことである。

• 長さ $k$ の区間を選び、そのうち $Y_k$ より大きいものをすべて $Y_k$ に変更する
• 長さ $k$ の区間を選び、そのうち $X_k$ より小さいものをすべて $X_k$ に変更する

この手の問題は、バックトレースが有効なことが多い。
つまり、$B$ からスタートして、逆再生に当たる以下の操作で $A$ にすることを目指す。

• 長さ $k$ の区間を選び、そのうち $Y_k$ であるものを $Y_k$ 以上の好きな値に変更する
  • ただし、この区間に、操作前から $Y_k$ より大きい値があってはならない
• 長さ $k$ の区間を選び、そのうち $X_k$ であるものを $X_k$ 以下の好きな値に変更する
  • ただし、この区間に、操作前から $X_k$ より小さい値があってはならない

これらの制約は、それぞれ以下のように言い換えられる。

• この区間の全ての数が、以下のいずれかを満たす
  • 元々 $B$ の値が $Y_k$ 以下である
  • 同じ位置で少なくとも $1$ 度後者の操作を適用済で、好きなだけ小さい値にする権利を持っている
• この区間の全ての数が、以下のいずれかを満たす
  • 元々 $B$ の値が $X_k$ 以上である
  • 同じ位置で少なくとも $1$ 度前者の操作を適用済で、好きなだけ大きい値にする権利を持っている

ということで、全 $N^2+N$ 通りの操作それぞれ、制約が解除されたものから実行していくことになる。
これは、以下のデータを持っておいて、処理すればよい。

• 各位置について、好きなだけ大きくする権利/小さくする権利をもっているかの配列 $2$ つ
• それらの権利の未獲得がどの範囲のどの操作をロックしているかの一覧の配列（$2$ 次元配列 $2$ つ）
• 各操作について、いくつの未獲得権利によってロックされているかの配列

処理内容は、以下。
トポロジカルソートするときの、Kahnのアルゴリズムの処理に似ている。

• 最初に、ロックがまったくされていない操作をqueueに詰め込む。
• queueの先頭を取り出して、以下の操作を行う。
  • 好きなだけ大きく/小さくする権利を新たに獲得できたものについて、そのことを記録する
    • $X_k$ や $Y_k$ の値だとすることが可能かどうかで判定する
  • 権利を獲得したものについて、ロックしていた操作のロック数をそれぞれ $1$ 減らす
  • ロック数が $0$ になった操作があれば、それをqueueの末尾に入れる
  • 新たに獲得する権利があったものだけ、操作列に入れる

これで、最初にある数がどの範囲なら $B$ にできるのか、判定できる。
しかも「新たに獲得する権利があったものだけ操作列に」のおかげで、操作列の長さは $2N$ を超えない。
よって、$A$ の各数が全てその範囲に入っていれば、可能ということになる。
つまり、作った操作列を時間系列順、つまり逆順に出力すればよい。

ロック相手の調査も、その後の解除シミュレーションも、各操作について $O(N)$ の操作を行う。
よって、全体の計算量は $O(N^3)$ である。

入力例1での動作

まず、$1$ つ目のテストケースを考える。

入力を受け取る。

n: 3
x: {1, 3, 1}
y: {3, 1, 3}
a: {1, 2, 3}
b: {3, 1, 1}

$B$ から逆向きに処理する。
最初は、どの位置についても好きなだけ大きくする権利・小さくする権利を持っていない。

まず、各操作がいくつの未獲得権利によってロックされているか調べる。
ロック数は以下のようになる。

例えば、chmin 1 2 では $Y_2=1$ であり、$B_1=3>1$ である。
よって、位置 $1$ で好きなだけ小さくする権利が未獲得であることによってロックされている。
また、chmax 2 3 では $X_2=3$ であり、$B_2=B_3=1<3$ である。
よって、位置 $2,3$ で好きなだけ大きくする権利が未獲得であることによって $2$ つロックされている。

ロック数が $0$ の操作を queue に入れると、初期状態は以下のようになる。

chmin 1 1
chmax 1 1
chmin 1 3
chmax 1 3
chmin 2 2
chmax 2 2
chmin 2 3
chmin 3 3
chmax 3 3

この queue を先頭から処理する。

最初の chmin 1 1 では $Y_1=3$ である。
$B_1=3$ なので、位置 $1$ で好きなだけ大きくする権利を得る。
この権利によって解除されるロックはない。

続く chmax 1 1 と chmin 1 3 では、新しい権利は得られない。

次の chmax 1 3 では $X_3=1$ である。
位置 $2,3$ は $B_2=B_3=1$ なので、位置 $2,3$ で好きなだけ小さくする権利を得る。
この $2$ つの権利によって解除されるロックはない。

続く chmin 2 2 と chmax 2 2 では、新しい権利は得られない。

次の chmin 2 3 では $Y_2=1$ である。
位置 $2,3$ は $B_2=B_3=1$ なので、位置 $2,3$ で好きなだけ大きくする権利を得る。
位置 $2$ の権利によって chmax 1 2 のロック数が $1\to0$、chmax 2 3 のロック数が $2\to1$ となる。
さらに、位置 $3$ の権利によって chmax 2 3 のロック数が $1\to0$ となる。
したがって、chmax 1 2 と chmax 2 3 を queue の末尾に追加する。

続く chmin 3 3 と chmax 3 3 では、新しい権利は得られない。

次の chmax 1 2 では $X_2=3$ である。
位置 $1$ は $B_1=3$ なので、位置 $1$ で好きなだけ小さくする権利を得る。
これによって chmin 1 2 のロック数が $1\to0$ となるので、これを queue の末尾に追加する。

最後に chmax 2 3 と chmin 1 2 を処理するが、新しい権利は得られない。
これで queue は空になる。

新しい権利を得られた操作だけを取り出すと、逆向きには以下の順に実行したことになる。

chmin 1 1
chmax 1 3
chmin 2 3
chmax 1 2

この時点で、全ての位置について両側の権利を得ている。
特に、以下が確認できる。

• $A_1<B_1$ で、必要な位置 $1$ の「好きなだけ小さくする権利」を得られている
• $A_2>B_2,A_3>B_3$ で、必要な位置 $2,3$ の「好きなだけ大きくする権利」を全て得られている。

よって、$A$ から $B$ への変換は可能である。
逆向きに採用した操作列を逆順にすると、以下の操作列になる。

chmax 1 2
chmin 2 3
chmax 1 3
chmin 1 1

次に、$2$ つ目のテストケースを考える。

入力を受け取る。

n: 2
x: {1, 1}
y: {2, 2}
a: {1, 2}
b: {2, 1}

この場合、全ての chmin について区間内の $B$ は $Y_k=2$ 以下である。
また、全ての chmax について区間内の $B$ は $X_k=1$ 以上である。
したがって、全 $6$ 操作のロック数が最初から $0$ であり、全て queue に入る。

順に処理すると、chmin 1 1 によって位置 $1$ で好きなだけ大きくする権利を得る。
また、chmax 1 2 によって位置 $2$ で好きなだけ小さくする権利を得る。
それ以外の操作では新しい権利を得られない。

処理終了時に得られている権利は以下の通りである。

一方、$A_1<B_1$ なので位置 $1$ では好きなだけ小さくする権利が必要である。
また、$A_2>B_2$ なので位置 $2$ では好きなだけ大きくする権利が必要である。
どちらも得られていないので、このテストケースは不可能であり、$-1$ を出力する。

注意点

特になし。

別解

特になし。