【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【動的計画法：その他】

この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。

53. DPL_1_D – 最長増加部分列

LIS でも大活躍！ DP の配列使いまわしテクニックを特集 の「3. LIS の解法(1) (二分探索 ver.)」にて本問題が解説されています。

注意 以下では レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 の「2-1. 「水色コーダー」で要求される 4 つのこと」の「条件 2」には記載のないアルゴリズムとデータ構造を用います。

LIS でも大活躍！ DP の配列使いまわしテクニックを特集 の「4. LIS の解法(2) (セグ木 ver.)」には以下を組み合わせた解法が紹介されています。

  • 座標圧縮
  • セグメント木

座標圧縮については以下が参考になります。

セグメント木の参考文献は本記事の「41. JOI 2013 予選 4 – 暑い日々」に記載してあります。

Atcoder Library の Appendix の「他のジャッジへの提出方法」に AtCoder 以外 (本問題の場合は AOJ) に AtCoder Library を用いたソースコードを提出する方法が記載されています。Atcoder Library を使う場合は確認しておくと良いかと思います。

54. AtCoder Beginner Contest 006 D – トランプ挿入ソート

許可された操作は「任意の場所に挿入する」ことが認められています。そのため、本問題は下記の操作が一回のみ許可されたときに山札のカードを昇順に並べ替えるのに必要な x の最小値を求める問題だと言い換えられます。

  • 山札からカードを x 枚抜き取り、任意の場所に挿入する。

カードを抜いた後の山札が昇順に並んでいれば、山札全体を昇順に並べ替えることができます。ゆえに、山札の最長増加部分列 (LIS) の長さが分かれば、LIS に属さないカードの枚数 (N – (LIS の長さ)) が答えになります。

ビット全探索で抜くカードの組み合わせを列挙して探索する場合、計算量は O(2^N N) 程度かかり、実行時間制限に違反しそうです。

\mathrm{dp}[i][j] を以下を満たす部分増加列の長さの最大値とします。

  • 第 i 番目までのカードのみ使う。
  • 数列の末尾の値が j である。

N \leq 3 \times 10^4 であるため、\mathrm{dp}[i][j] を更新する動的計画法でも時間計算量は O(N^2) = 10^9 程度です。実行時間制限違反寸前ですが、動的計画法の表を単純に使いまわすだけでに違反せずに解答できます。

前問 DPL_1_D – 最長増加部分列 同様に O(N\log(N)) で LIS を求めて求解することも可能です。

  • 解答例 2 二分探索 ver.
  • 解答例 3 セグ木 ver. (前問と異なり、この問題では座標圧縮は不要です)

55. AtCoder Beginner Contest 134 E – Sequence Decomposing

色は最大 N 色まであると考えて、すべての項の色の塗り方を全探索して最小値を見つめる方法では \Omega(N^{N+1}) の計算量になり、実行時間制限に違反しそうです。

同じ色が満たす条件から、数列 A から同じ色の項を取り出した部分列は単調増加部分列でなければなりません。

試しに以下のようにして数列 A をいくつかの単調増加部分列に分割してみます。

以下を A のすべての項が以降で作成する部分列のいずれかに割り当てられるまで繰り返します。

  1. 空の部分列 B を用意します。
  2. 数列 A の各項を添字の若い方から順にみていき、以下を満たす場合に B に追加します。
    • これまでに作成した単調増加部分列のいずれにも属していない。
    • 部分列 B の末項 (前回 B に追加した項) よりも大きい。

このように作成した数列 A の分割を \{B_i\}_{i=1}^{M} とおきます。各 B_i に 1 つの色を割り当てると条件を満たすように A を塗ることができるため、求める色の数の最小値は分割 \{B_i\}_{i=1}^{M} の単調増加部分列の個数 M 以下です。

入力例 1 (A = \{2, 1, 4, 5, 3\}) の場合、B_1 = \{2, 4, 5\}, B_2 = \{1, 3\} となり、M = 2 です。

M を見積もるため、天下り的ですが、\{B_i\}_{i=1}^{M} の次の性質を確認します。

  • 分割 \{B_i\}_{i=1}^{M} の任意の B_{i+1} の項 A_{B_{i+1}^j} に対して B_{i}^{k}<B_{i+1}^j かつ A_{B_{i}^{k}} \geq A_{B_{i+1}^j} となる B_i の項 A_{B_{i}^{k}} が存在します。

このような B_i^k が存在しないと仮定すると B_{i} の構成方法から A_{B_{i+1}^j} は B_i の項でなければならないため、矛盾します。
確認した性質から以下の手順で長さ M である数列 A の単調非増加部分列 C が作成できます。

部分列 B_M から項を一つ取り出し、部分列 C の第 M 項とします。
以下を i = M – 1 から i = 1 まで i を 1 ずつ減らしながら繰り返し行います。

  1. 部分列 C の第 i + 1 項 A_{B_{i+1}^j} に対し B_{i}^{k}<B_{i+1}^j かつ A_{B_{i}^{k}} \geq A_{B_{i+1}^j} を満たす B_i の項 A_{B_{i}^{k}} を C の第 i 項とします。

入力例 1 の場合、C は以下のいずれかです。

\{2, 1\}, \quad \{4, 1\}, \quad \{5, 1\}, \quad \{4, 3\}, \quad \{5, 3\}

長さ M の単調非増加部分列が作成できるため、求める色の数の最小値は A の最長単調非増加部分列の長さ以下であることがわかります。

逆に条件を満たすように色を塗るとき A の単調非増加部分列の各項は別の色に塗る必要があります。単調非増加部分列に属する A_i, A_j (i<j) が同じ色で塗られていると仮定すると、A_i \geq A_j であるため、条件に違反します。
よって、条件を満たすように色を塗るときに必要な色の数は A の単調非増加部分列、特に最長単調非増加部分列の長さ以上です。

以上の考察から必要な色の数の最小値は A の最長単調非増加部分列の長さに一致します。
A の最長単調非増加部分列の長さは最長増加部分列 (LIS) の長さを求める方法と同様に計算量 O(N\log N) = 10^6 程度で求められます。