E - Pancakes 解説
by 
square1001
本コンテストの問題 E「Pancakes」の解説をします。
この問題は、パンケーキのある区間を \(1\) 回までひっくり返せるとき、「隣り合うパンケーキの大きさの差」の合計をできるだけ小さくしたい、というものです。
最も単純な解法として、反転させる区間を \(N(N-1)/2\) 通り全探索することが考えられます。見栄えの悪さ ＝「隣り合うパンケーキの大きさの差」の合計を求めるのに \(N\) 回程度の計算回数がかかるので、計算量 \(O(N^3)\) でこの問題を解けます。実装例 (C++) しかし、これだと \(N \leq 500\) 程度までのテストケースでしか正解を得られず、データが大きくなると答えを求めるのに長い時間がかかってしまいます。ここで、この解説では全探索の解法を原点として、より効率的なアルゴリズムを考えていきます。
解説の目次
本解説では、以下の段取りで解法を説明します。
ステップ 1 では、操作における見栄えの悪さの変化量に注目することで、それぞれの \(l, r\) の選び方に対して見栄えの悪さを定数時間 \(O(1)\) で計算する方法を考えます。これにより、全探索を計算量 \(O(N^2)\) で行えるようになります。
ステップ 2 では、これを効率的に解くために、「どんな \(l, r\) を選べば見栄えの悪さが減少するのか」の性質を考えることで、「最長共通区間」の問題に帰着させます。
ステップ 3 では、\(M\) 個の区間から \(2\) つを選ぶときの最長の共通部分を求める「最長共通区間」の問題を計算量 \(O(M \log M)\) で解く方法を解説します。これによって、本問題を計算量 \(O(N \log N)\) で解くことができ、正解 (AC) に到着します。
そして、4 節には本問題の解法のまとめ、その後の 5 節には本問題の C++ による実装例（サンプルコード）を載せています。なお、急いで解説を読みたい方は、4 節「解法のまとめ」を読んでください。なお、この問題は「見栄えの悪さ」の最小値を求める問題ですが、最大値を求める問題は、全く別の解法で計算量 \(O(N)\) で解くこともでき、これについても 6 節で紹介します。
ステップ 1：見栄えの変化を考える
まずは、パンケーキの区間を反転させると、どのように形が変化し、どのように見栄えの悪さが変化するのかを考えてみましょう。具体例として、下図を見てみましょう。この例では \(l = 2, r = 5\) を選んで操作をしており、隣り合うパンケーキの大きさの差は、上の図の例では \(6, 3, 1, 2, 3, 2\) から \(4, 2, 1, 3, 1, 2\) に変わっています。
これに見るように、変化は次のようになります。
- 反転する区間の中では、パンケーキの大きさの差は反転しただけ（形が変わっていないので）
- 反転していない区間の中では、パンケーキの大きさの差は変化していない（形が変わっていないので）
- 反転する区間の両端では、上図の緑色の部分のように、パンケーキの大きさの差は変化する
つまり、上図の例では、反転した区間の両端におけるパンケーキの大きさの差が \(6, 3\) から \(4, 1\) になったから、合計が \(17\) から \(13\) に減っています。このように、見栄えの悪さ (= 合計値) の変化を測る時、反転する区間の両端 (3. のパターン) 以外考えなくてよいです。
具体的に式で表してみると、合計値の変化は以下のように単純な計算で求まります。
基本的には見栄えの悪さは \(|A_{l-1} - A_l| + |A_r - A_{r+1}| - |A_{l-1} - A_r| - |A_l - A_{r+1}|\) 減少します。なぜなら、パンケーキの大きさの差は、左端が \(|A_{l-1} - A_l|\) から \(|A_{l-1} - A_r|\) に、右端が \(|A_r - A_{r+1}|\) から \(|A_l - A_{r+1}|\) に変化するからです。
ただし、\(l = 1\) または \(r = N\) の場合は、以下のように少し違います。
- \(l = 1, r \neq N\) の場合：\(|A_r - A_{r+1}| - |A_l - A_{r+1}|\) 減少する（左端にパンケーキがないので）
- \(l \neq 1, r = N\) の場合：\(|A_{l-1} - A_l| - |A_{l-1} - A_r|\) 減少する（右端にパンケーキがないので）
- \(l = 1, r = N\) の場合：全体が反転するだけで形は変わらず、見栄えも変化しない
このように、見栄えの悪さの減少量に注目すると、それぞれの \(l, r\) の選び方に対して見栄えの悪さを定数時間 \(O(1)\) で求めることができ、全体計算量 \(O(N^2)\) で本問題を解くことができました 実装例 (C++) しかし、これでも実行時間制限超過 (TLE) となってしまうので、今後のステップではこれをさらに効率化するアイデアを考えていきます。
ステップ 2：見栄えが良くなる \(l, r\) の選び方は？
ステップ 1 では、反転させる区間の両端のパンケーキの大きさ、すなわち \(A_{l-1}, A_l, A_r, A_{r+1}\) の値のみによって見栄えの変化量が決まることを説明しました。ステップ 2 では、この 4 つの値についてどのような関係が成り立てばどのくらい見栄えが良くなるのか考察します。
まず、\(A_{l-1}, A_l, A_r, A_{r+1}\) の位置関係は以下の図に示すように \(6\) 通りあります（左右反転と上下反転で一致するものは同じ位置関係と数えているため、実際の大小関係は \(4! = 24\) 通りあります）黄色い部分が「パンケーキの大きさの差」を示しており、その長さの変化量が見栄えの変化量になっています。
さて、見栄えが良くなっているのは上図の 1～6 のどれでしょうか？それぞれのパターンを見ていきましょう。
- 1 と 2 では、黄色い部分が両方長くなっているので、見栄えが悪くなる
- 3 と 4 では、黄色い部分が一方が増えたのと同じ分だけもう一方が減るので、見栄えの悪さは変化しない
- 5 と 6 では、黄色い部分が両方短くなっているので、見栄えが良くなる
したがって、パターン 5, 6 のような位置関係のときに見栄えが良くなるといえます。さらに、その変化量は、2 つの黄色い部分の区間の共通部分 × 2 になっているのです。
これを整理すると、以下の事実がいえます。
\(A_{l-1} \lt A_l\) かつ \(A_r \lt A_{r+1}\) のとき
- 区間 \(A_{l-1} \leq x \leq A_l\) と区間 \(A_r \leq x \leq A_{r+1}\) に共通部分が存在すれば、この共通部分の長さの 2 倍だけ減る
\(A_{l-1} \gt A_l\) かつ \(A_r \gt A_{r+1}\) のとき
- 区間 \(A_l \leq x \leq A_{l-1}\) と区間 \(A_{r+1} \leq x \leq A_r\) に共通部分が存在すれば、この共通部分の長さの 2 倍だけ減る
\(A_{l-1}, A_l\) の大小関係と \(A_r, A_{r+1}\) の大小関係が異なるときは、見栄えが良くなることはない
したがって、減少量を最大にするためには、区間の共通部分が最長になるような \(l, r\) を選ぶことになります。ここで、「最長共通区間」の問題を考えます。
問題：最長共通区間
\(M\) 個の区間が与えられる。区間 \(i\) は \(L_i \leq x \leq R_i\) である。ここから \(2\) つの区間を選ぶとき、選んだ区間の共通部分の長さの最大値を求めてください。ただし、共通部分をもつ区間のペアが存在しない場合は、答えを \(0\) とします。
ここで、変化量の最大値を求めるために、最長共通区間の問題を解くことになっています。具体的には以下の通りです。
- \(A_i \lt A_{i+1}\) となる全ての場所における区間 \(A_i \leq x \leq A_{i+1}\) の、最長共通区間を求める（その答えを \(Z_1\) とする）
- \(A_i \gt A_{i+1}\) となる全ての場所における区間 \(A_{i+1} \leq x \leq A_i\) の、最長共通区間を求める（その答えを \(Z_2\) とする）
これで結果として、\(l \neq 1, r \neq N\) の場合の最大の減少量が \(\max(2Z_1, 2Z_2)\) で求まっているのです。なお、\(l = 1\) や \(r = N\) の場合はパターン数が少ないので、全探索で答えを求められます。
そうなると、あとは「最長共通区間」を効率的に解く方法を考えるだけです。これについてはステップ 3 で解説します。最長共通区間の問題は、元の問題より取り掛かりやすく見えると思います。より取り掛かりやすく見える問題に落とし込むことができたなら、そのまま突き進むというのも競技プログラミングの良い戦略のひとつです。
ステップ 3：「最長共通区間」を \(O(M \log M)\) で解く
ステップ 3 では、最長共通区間の問題を \(O(M \log M)\) で解く方法を説明します。これには色々な解法がありますが、今回はそのうち 1 つを説明します。
まず、2 つの区間の共通部分は次のように計算できます。
性質 区間 \(a_1 \leq x \leq b_1\) と区間 \(a_2 \leq x \leq b_2\) の共通部分は、\(\max(a_1, a_2) \leq x \leq \min(b_1, b_2)\) である。
したがって、区間 \(i, j\) の共通部分は \(\max(L_i, L_j) \leq x \leq \min(R_i, R_j)\) です。この長さができるだけ大きくなる \(i, j\) を求めたいです。
ここで、\(L_i\) をソートして考えてみましょう。\(L_1 \leq L_2 \leq \cdots \leq L_M\) が成り立っているとします。すると、区間 \(i, j\) \((i \lt j)\) の共通部分は \(L_j \leq x \leq \min(R_i, R_j)\) になります。したがって、ある \(j\) に対して共通部分の長さが最大になるのは、最も大きい \(R_i\) を選ぶときになります。下図の例では、\(j = 4\) では \(i = 2\) を選ぶのが最適（共通部分は \(L_4 = 25 \leq x \leq 48 = R_2\)）で、\(j = 7\) では \(i = 5\) を選ぶのが最適（共通部分は \(L_7 = 37 \leq x \leq 65 = R_7\)）です。
したがって、最長共通区間は、以下のアルゴリズムで求められます。
- \(M\) 個の区間を \(L_i\) の小さい順に並び替える
- \(j = 2, 3, \cdots, M\) の順に、以下の処理を行う：
\(j\) がその値に固定されているときに共通区間が最も長くなるのは \(R_i\) が最大の区間を相手として選ぶときなので、その区間は\(L_j \leq x \leq \min(R_j, \max(R_1, R_2, \dots, R_{j-1}))\) となる - この中で最長のものが「最長共通区間」となる。そのような区間がない場合は、答えを \(0\) とする
ここで、\(\max(R_1, R_2, \dots, R_{j-1})\) の値は、累積的に求めていくことができるので、計算量はソートがボトルネックとなり \(O(M \log M)\) となります。
それ以外にも、イベントソート を用いた解法などがあります。
4. 解法のまとめ
まとめると、この問題は以下の手順で解けます。
- 見栄えの変化に関与するのは、反転する区間の両端だけなので、(\(2 \leq l \lt r \leq N-1\) の場合は) 減少分 \(|A_{l-1} - A_l| + |A_r - A_{r+1}| - |A_{l-1} - A_r| - |A_l - A_{r+1}|\) の最大値を求める問題になる。
- 見栄えが減少し得るのは「\(A_{l-1} \lt A_l\) かつ \(A_r \lt A_{r+1}\) のとき」または「\(A_{l-1} \gt A_l\) かつ \(A_r \gt A_{r+1}\) のとき」で、その減少分は「\(A_{l-1}\) と \(A_l\) を両端とする区間」と「\(A_r\) と \(A_{r+1}\) を両端とする区間」の共通部分の長さ × 2 となる。
- ここで、\(A_i \lt A_{i+1}\) のパターンと \(A_i \gt A_{i+1}\) の場合に分けて考えると、\(M\) 個の区間から \(2\) つを選ぶときの最長の共通部分を求める「最長共通区間」の問題を解くことになる。
- 「最長共通区間」の問題は計算量 \(O(M \log M)\) で解ける。ひとつの解法は、区間の左端 \(L_i\) を小さい順にソートすること。このとき、区間 \(i, j\) \((i \lt j)\) の共通部分は \(L_j \lt \min(R_i, R_j)\) となるので、選べる中で \(R_i\) が最大のものを選ぶのが最適。この共通部分を全ての \(j\) に対して計算し、その中で最長のものが「最長共通区間」となる。
このようにして、本問題を全体計算量 \(O(N \log N)\) で解くことができました。
この問題を解くために、重要なテクニックは 3 つあります。それぞれステップ 1, 2, 3 に対応しています。
- 操作で「変わる場所」が少ないとき、変化する場所だけを考えることで計算量を落とす
- 位置関係を考えることで、解く問題の範囲を限定する
- ソートして計算を効率化する
これらのテクニックは、競技プログラミングの他の問題でもよく使われるので、知っておきましょう。
5. サンプルコード
この問題の解答例は以下の通りです。C++, Python による実装例を紹介します。
- Writer による実装 (C++)：https://atcoder.jp/contests/arc119/submissions/22586643
- Tester による実装 (Python)：https://atcoder.jp/contests/arc119/submissions/22668289
6. おまけ：「最大値」を求める場合の解法
本問題は「見栄えの悪さ」を最小化する問題でしたが、最大化する問題であれば、全く別の解き方で計算量 \(O(N)\) で解くことができます。
まず、ステップ 1 で説明した通り、\(2 \leq l \lt r \leq N-1\) に限定すれば以下の問題を解くことになります。
長さ \(N\) の数列 \(A_1, A_2, \dots, A_N\) が与えられる。\(|A_s - A_t| + |A_{s+1} - A_{t+1}| - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) \((s \neq t)\) の最大値を求めなさい。
この問題は絶対値がついているから難しいのですが、最大値を求める問題については、次の性質を使って絶対値を外せる場合があります。
性質 \(x\) の絶対値 \(|x|\) は、\(x\) と \(-x\) のうち大きい方の値である。
したがって、この問題は、以下の \(4\) つの問題に分けることができ、そのうち最も大きい値が答えになります。
- \((A_s - A_t) + (A_{s+1} - A_{t+1}) - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) \((s \neq t)\) の最大値 を求める
- \((A_s - A_t) + (A_{t+1} - A_{s+1}) - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) \((s \neq t)\) の最大値 を求める
- \((A_t - A_s) + (A_{s+1} - A_{t+1}) - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) \((s \neq t)\) の最大値 を求める
- \((A_t - A_s) + (A_{t+1} - A_{s+1}) - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) \((s \neq t)\) の最大値 を求める
このそれぞれの問題は、効率的に計算することができます。手始めに、1 番目に載せた問題について考えてみましょう。
\((A_s - A_t) + (A_{s+1} - A_{t+1}) - |A_s - A_{s+1}| - |A_t - A_{t+1}|\) は、\(s\) の部分と \(t\) の部分に分けて \((A_s + A_{s+1} - |A_s - A_{s+1}|) + (-A_t - A_{t+1} - |A_t - A_{t+1}|)\) と書けます。なので、\(P_i = A_i + A_{i+1} - |A_i - A_{i+1}|, Q_i = -A_i - A_{i+1} - |A_i - A_{i+1}|\) とすると、\(P_s + Q_t\) と書けます。
ここで、以下の問題を考えます。
長さ \(n\) の数列 \(p_1, p_2, \dots, p_n\) と \(q_1, q_2, \dots, q_n\) が与えられる。このとき、\(p_s + q_t\) \((s \neq t)\) の最大値を求めてください。
これは、「基本的には答えが (\(p\) の最大値) + (\(q\) の最大値) になる」ことを利用して、以下のように解くことができます。
- \(p_1, p_2, \dots, p_n\) の中で最大の値を \(p_{x_1}\)、2 番目に最大の値を \(p_{x_2}\) とする。
- \(q_1, q_2, \dots, q_n\) の中で最大の値を \(q_{y_1}\)、2 番目に最大の値を \(q_{y_2}\) とする。
- \(x_1 \neq y_1\) ならば、最大値を \(p_{x_1} + p_{y_1}\) にできる
- \(x_1 = y_1\) ならば、\(p_{x_1} + p_{y_2}\) と \(p_{x_2} + p_{y_1}\) のどちらかが最適なので、そのうち小さい方が答えになる
（※ 数列 \(p, q\) の最大値が複数ヶ所にある場合は、そのうちどれを最大、どれを 2 番目に最大に選んでもよいです）
先ほどの 1 番目の問題は、この問題におきかえられるので、計算量 \(O(N)\) で解けました。
同様にして、2, 3, 4 番目の問題も、式を \(s\) の部分と \(t\) の部分に分けられるので、この問題におきかえることができ、計算量 \(O(N)\) で解けます。
よって、見栄えの悪さの最大値を求める問題は、計算量 \(O(N)\) で解けました。
投稿日時:
最終更新: