ABC 391 F — K-th Largest Triplet

考察

三つの配列を降順に並べると、選ぶ位置を先へ進めても値は増えない。最大の組から候補を広げれば、全組を作らずに必要な順位まで調べられる。同じ位置の組を重複登録せず、値が等しい別の組は残す。

全組を並べると N3N^3 個になるが、必要なのは上位の高々 5×1055\times 10^5 個だけだ。大きい組から順に作れないだろうか。各配列の要素は正なので、一要素を大きくすると式の値は小さくならない。そこで三つの配列を降順に並べる。

以後、添字は0から始める。選んだ位置の組を (i,j,k)(i,j,k)、その範囲を 0≤i,j,k<N0\leq i,j,k<N とし、その値を定義する。

f(i,j,k)=AiBj+BjCk+CkAif(i,j,k)=A_iB_j+B_jC_k+C_kA_i

0≤i<N−10\leq i<N-1 なら、一方向の変化は次の式で確認できる。

f(i,j,k)−f(i+1,j,k)=(Ai−Ai+1)(Bj+Ck)≥0f(i,j,k)-f(i+1,j,k)=(A_i-A_{i+1})(B_j+C_k)\geq 0

前半は降順なので非負、後半は要素が正なので正である。他の二方向も同様に、添字を増やしても値は増えない。最大の組の一つは (0,0,0)(0,0,0) だと分かる。この状態を原点と呼ぶ。

なぜ以前の候補も残すのか

降順の独自例 A=(3,1),B=(4,2),C=(5,1)A=(3,1),B=(4,2),C=(5,1) を見る。最大値47から添字を一つ増やした三つの候補は29、31、19である。次に31を選んだ後、その隣に追加できる値は17、11だが、以前の候補29はまだ残っている。直前の組の隣だけを見てはいけない。

生成済みで未出力の候補全体を、最大値を取り出せる優先度付きキュー(max-heap)へ残す。この候補集合が探索境界(frontier)となる。

  1. 値と組 (f(0,0,0),0,0,0)(f(0,0,0),0,0,0) をキューへ入れ、組 (0,0,0)(0,0,0) を登録済み集合へ記録する。
  2. 最大値の組を取り出す。これが KK 回目なら、その値を答えて終了する。
  3. 取り出した組の各添字を一つ増やした三つの組のうち、範囲内かつ未登録のものを集合へ記録してキューへ入れ、手順2へ戻る。

同じ組へは複数方向から到達するので、登録は追加時に行う。一方、全要素が1なら値はすべて3でも、組の数だけ順位がある。集合のキーは値ではなく添字の組にする。

典型の発動条件

全状態が多くても上位の少数だけが必要で、最大の出発点と値が悪化する向きが分かるなら、探索境界を優先度付きキューで管理する。未出力状態への経路上に、値がそれ以上の候補が残ることを確認する。

implicit graphの重複排除

複数の経路から同じ状態へ到達する場合は、追加時に状態を登録する。何を同一視するかは問題の数え方で決める。この問題では値が等しくても添字の組が違えば別の順位を占める。

問題固有の要素

交差項を含む式でも、他の二要素の和が正なので各方向に単調となる。一つの変数だけ動かした差を因数分解すると、この制約の役割が見える。

正当性

任意の未出力の組 xx へ、原点から添字を一つずつ増やして進む経路を取る。その経路で最初の未出力状態を yy とする。原点なら初期登録され、それ以外なら直前の状態を取り出した際に登録されている。未出力なので、どちらもキューに残っている。

経路上で値は増えないから f(y)≥f(x)f(y)\geq f(x)。従ってキューの最大値は、すべての未出力状態の最大値でもある。この操作を繰り返すと KK 回目が答えになる。同じ組は一度だけ登録し、値が等しい別の組は区別するので、同値の順位も正しく数える。

実装上の注意

添字が NN に達する候補は追加しない。K=1K=1 なら初回で終了し、K=N3K=N^3 なら全組を数える。要素は最大 10910^9、答えは最大 3×10183\times 10^{18} なので、乗算前に符号付き64 bit整数へ変換する。組のキーも整数幅を確認する。

復習の核

  • 全状態が多く上位だけが少ないとき、最大の出発点と単調な向きを探す。
  • 未出力状態への経路を描き、最初の未出力状態がキューに残る理由を説明する。
  • 同じ値と同じ状態の重複を区別する。

計算量と制約

時間

三列の整列が O(Nlog⁡N)O(N\log N)。一回の取り出しにつき追加は高々三件で、全体の候補は O(K)O(K) 件。優先度付きキューと、登録済み集合に使う平衡二分探索木の各操作は O(log⁡(K+1))O(\log(K+1)) なので、全体は O(Nlog⁡N+Klog⁡(K+1))O(N\log N+K\log(K+1)) 時間。

空間

入力が O(N)O(N)、キューと登録済み集合が O(K)O(K) なので、合計 O(N+K)O(N+K)。全組は保持しない。

制約との対応

1≤N≤2×1051\leq N\leq 2\times 10^5、1≤K≤min⁡(N3,5×105)1\leq K\leq\min(N^3,5\times 10^5)、1≤Ai,Bi,Ci≤1091\leq A_i,B_i,C_i\leq 10^9。列挙量を N3N^3 から KK に抑える。要素が正という条件は単調性に使い、順位の範囲は答えに到達できることを保証する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

K-th Largest Triplet の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: priority queue・best-first列挙

主題
  • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: priority queue・best-first列挙

      執筆: abc-explanation-author1.1.1 / revision 2

      学習の位置

      体系上の位置: priority queue・best-first列挙

      • 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題