Official

B - Increasing Triples Editorial by maspy

\(A_i < B_j < C_k\) となる組 \((A_i, B_j, C_k)\) を単に \(3\) つ組と呼ぶことにします。本問題は、同じ要素を高々 \(1\) 度まで使わないという制約のもと、なるべく多くの \(3\) つ組を選ぶ問題として言い換えられます。

以下、入力をソートして、\(A_1\leqq \cdots\leqq A_N\), \(B_1\leqq \cdots\leqq B_N\), \(C_1\leqq \cdots\leqq C_N\) が成り立つとしておきます。

最大個数の \(3\) つ組を選んだ状態を「最適解」と呼ぶことにします。

◆ 最適解の構造 (1)

次のいずれかが成り立つことを示すことができます：

  • 最適解は、\(3\) つ組をひとつも選ばない
  • 最適解のうちで、\(A_1\) を選ぶものが存在する

このことを証明しましょう。

\(3\) つ組をひとつ以上選んでいて、\(A_1\) は選んでいないような最適解が存在するとします。そのような最適解で選ばれている \(3\) つ組のひとつ \((A_i, B_j, C_k)\) に対して、これを \((A_1, B_j, C_k)\) に変更することができます。この変更操作は選んだ \(3\) つ組の個数を変えていないため、変更前が最適解ならば変更後も最適解です。よって \(A_1\) を選ぶような最適解が存在することにがわかります。

以上のことから、本問題における考察対象を、\(A_1\) を選ぶ場合に限定してよいことがわかりました。

◆ 最適解の構造 (2)

次に、\(B_j\) の選び方について考えましょう。

\(B_j\leq A_1\) を満たす \(B_j\) は、\(3\) つ組として選ぶことは不可能です。よって、そのような \(B_j\) は初めから削除してしまって考察すればよいです。

\(B\) が空のときは明らかなので、以下、そうでないとします。したがって、\(A_1 < B_1\) を仮定します。

次のいずれかが成り立つことを示すことができます：

  • 最適解は、\(3\) つ組をひとつも選ばない
  • 最適解のうちで、\(A_1, B_1\) を同じ \(3\) つ組に選ぶものが存在する

このことを証明しましょう。

\(3\) つ組をひとつ以上選び、\(A_1, B_1\) を同じ \(3\) つ組に選ばない最適解が存在したと仮定します。ここから、\(A_1, B_1\) を同じ \(3\) つ組に選ぶ最適解の存在を示せばよいです。 まず、(1) の証明と同じようにして、\(A_1, B_1\) がともに \(3\) つ組に選ばれているような最適解が存在することが分かります。これらが \(A_1, B_1\) を同じ組に選んでいないとして、\(A_1, B_1\) を含む \(3\) つ組を \((A_1, B_j, C_k)\), \((A_i, B_1, C_{k'})\) とします。\(B_1\) の最小性よりこれを \((A_1, B_1, C_{k'})\), \((A_i, B_j, C_k)\) に入れ替えることができるため、\(A_1, B_1\) を同じ \(3\) つ組に選ぶ最適解が得られました。

◆ 最適解の構造 (3)

\(C_k\leqq B_1\) を満たす \(C_k\) は、\(3\) つ組として選ぶことは不可能です。よって、そのような \(C_k\) は初めから削除してしまって、\(A_1 < B_1 < C_1\) として考察すればよいです。

(1), (2) と同様にして、次を証明することができます：

  • 最適解のうちで、\((A_1, B_1, C_1)\) を同じ \(3\) つ組に選ぶものが存在する。

◆ 解法

以上をまとめて、次の貪欲アルゴリズムが得られます。

  • \(A\) が空ならば終了する。そうでないならば \(A\) の最小値を \(A_1\) とし、\(A_1\) 以下であるような \(B_j\) をすべて削除する。
  • \(B\) が空ならば終了する。そうでないならば \(B\) の最小値が \(B_1\) であるとし、\(B_1\) 以下であるような \(C_k\) をすべて削除する。
  • \(C\) が空ならば終了する。そうでないならば \(C\) の最小値を \(C_1\) とする。
  • \(3\) つ組 \((A_1, B_1, C_1)\) を選ぶ。\(A_1, B_1, C_1\) は削除して、はじめに戻る。

それぞれの最小値の取得や削除を効率よく行うことで、本問題は \(\Theta(N\log N)\) 時間で解くことができます。

実装の方針として、

などがあります。

posted:
last update: