Codeforces Round #645 (Div. 2) F. Tasty Cookie

問題概要

長さがともに $n$ の数列 $A = (A_{1}, ..., A_{n}), B = (B_{1}, ..., B_{n})$ が与えられる。数列 $A$ に対して、以下の操作を $0$ 回以上好きな順番で行って $B$ に一致させたい。

数列 $A$ を反転する。
数列 $A$ を、 $A$ の先頭からの累積和を並べた数列に置き換える。

これが可能かどうか判定し、可能な場合は操作列のうち操作2の回数が最小であるものを求めよ。操作2の回数が $200000$ 以下であれば操作列全体を、そうでなければ操作2の回数だけを出力せよ。

制約

$1 \le n \le 2\times 10^{5}$
$1 \le A_{i} \le 10^{12}$
$1 \le B_{i} \le 10^{12}$

解法

まず $n=1$ のときは最初に処理しておきます。以降は $n \ge 2$ とします。

キーポイントは「逆から考える」ことです。

累積和を取る操作の逆は、階差数列を取ることです。 $B$ からスタートして、階差数列を取る操作と反転操作で $A$ に一致させることを目指します。

ここで $A$ から本来の操作を進めていった数列は全ての要素が正です。つまり逆回しするときにも全ての要素が正になるような操作しか考える必要がありません。階差が全て正になるような数列は、すなわち狭義単調増加数列です。

そのため、操作前もしくは操作途中の $B$ からの操作は、無意味に2回連続で反転操作することを除けば以下のものに限られます。

$B$ または $B$ の反転が $A$ に一致するならば、そこで操作を終了して答えを出力する。
そうでなくて、 $B$ が狭義単調増加数列ならば、そのまま階差を取る。
そうでなくて、 $B$ が狭義単調減少数列ならば、反転させて階差を取る。
そうでない場合、 $A$ と一致させることは不可能なので IMPOSSIBLE を出力して終了する。

このように各場面で取り得る操作が1通りなので、与えられた $B$ からのシミュレーションができます。またこの操作が1通りであることから、条件を満たす操作列が存在するならば操作2の回数は一意であることが示せます。

ただしこれが十分速く終了するとは限らないため、ここで階差を取る操作（本来の累積和を取る操作）が最大で何回起こり得るかを考慮する必要があります。

本来の操作順で考えます。操作結果 $B$ が $B_{i} \le 10^{12}$ を満たすという制約下で最も累積和を取る回数が多くなるパターンは、 $A$ が全て $1$ のものからスタートして、毎回同じ方向に累積和を取った場合です。このとき末尾の要素は $n$ が大きいほど爆発的に増加し、実際に計算すると $n=3$ であれば $1414213$ 回目、 $n = 10$ まで増えると $85$ 回目で $10^{12}$ を超えます。なので $B$ から逆回しでシミュレーションするときにもこの回数を超えることはなく、 $n \ge 3$ の時は間に合います。

問題は $n=2$ のときで、例えば

2
1 1
1 1000000000000

という入力において答えとなる操作列は「累積和を $10^{12}-1$ 回取り続ける」です。これはシミュレーションできません。

そのため最初は逆回しシミュレーションをしていって、操作列全体が要求される $200000$ 回を超えた後は回数だけを数える「まとめて処理」モードに切り替えましょう。 $n=2$ の場合、階差を取る操作は「大きい方から小さい方を引く」操作であるため、大小関係が逆転するまで引き続ける操作はちょうどユークリッドの互除法のようにまとめて処理することができます。こうすれば $B_{i}$ についての対数時間で処理できます。

実際には操作の途中で $A$ と一致するかどうかの判定も挟むので少し厄介です。例えば以下のような実装手順を踏めば良いです。

階差を取った回数が $200000$ 回を超えた後は、出力において反転操作を考慮しなくて良いので、この時点で $A, B$ をそれぞれソートする。
以下を繰り返す。
- もし $A_{1} = B_{1}$ ならば、 $B_{2}$ から $B_{1}$ を引き続けることで $A_{2}$ と一致させられるか判定する。一致させられるなら操作回数を、させられないなら IMPOSSIBLE を出力して終了。
- そうでないなら、 $B_{2}$ から $B_{1}$ を引き続けて $B_{1} \ge B_{2}$ となるまでの操作をまとめて処理し、反転する。ここで $B_{1} = B_{2}$ となる場合は IMPOSSIBLE で終了。