考察
三つの配列を降順に並べると、選ぶ位置を先へ進めても値は増えない。最大の組から候補を広げれば、全組を作らずに必要な順位まで調べられる。同じ位置の組を重複登録せず、値が等しい別の組は残す。
全組を並べると 個になるが、必要なのは上位の高々 個だけだ。大きい組から順に作れないだろうか。各配列の要素は正なので、一要素を大きくすると式の値は小さくならない。そこで三つの配列を降順に並べる。
以後、添字は0から始める。選んだ位置の組を 、その範囲を とし、その値を定義する。
なら、一方向の変化は次の式で確認できる。
前半は降順なので非負、後半は要素が正なので正である。他の二方向も同様に、添字を増やしても値は増えない。最大の組の一つは だと分かる。この状態を原点と呼ぶ。
なぜ以前の候補も残すのか
降順の独自例 を見る。最大値47から添字を一つ増やした三つの候補は29、31、19である。次に31を選んだ後、その隣に追加できる値は17、11だが、以前の候補29はまだ残っている。直前の組の隣だけを見てはいけない。
生成済みで未出力の候補全体を、最大値を取り出せる優先度付きキュー(max-heap)へ残す。この候補集合が探索境界(frontier)となる。
- 値と組 をキューへ入れ、組 を登録済み集合へ記録する。
- 最大値の組を取り出す。これが 回目なら、その値を答えて終了する。
- 取り出した組の各添字を一つ増やした三つの組のうち、範囲内かつ未登録のものを集合へ記録してキューへ入れ、手順2へ戻る。
同じ組へは複数方向から到達するので、登録は追加時に行う。一方、全要素が1なら値はすべて3でも、組の数だけ順位がある。集合のキーは値ではなく添字の組にする。
典型の発動条件
monotone multidimensional best-first search
全状態が多くても上位の少数だけが必要で、最大の出発点と値が悪化する向きが分かるなら、探索境界を優先度付きキューで管理する。未出力状態への経路上に、値がそれ以上の候補が残ることを確認する。
implicit graphの重複排除
複数の経路から同じ状態へ到達する場合は、追加時に状態を登録する。何を同一視するかは問題の数え方で決める。この問題では値が等しくても添字の組が違えば別の順位を占める。
問題固有の要素
交差項を含む式でも、他の二要素の和が正なので各方向に単調となる。一つの変数だけ動かした差を因数分解すると、この制約の役割が見える。
正当性
任意の未出力の組 へ、原点から添字を一つずつ増やして進む経路を取る。その経路で最初の未出力状態を とする。原点なら初期登録され、それ以外なら直前の状態を取り出した際に登録されている。未出力なので、どちらもキューに残っている。
経路上で値は増えないから 。従ってキューの最大値は、すべての未出力状態の最大値でもある。この操作を繰り返すと 回目が答えになる。同じ組は一度だけ登録し、値が等しい別の組は区別するので、同値の順位も正しく数える。
実装上の注意
添字が に達する候補は追加しない。 なら初回で終了し、 なら全組を数える。要素は最大 、答えは最大 なので、乗算前に符号付き64 bit整数へ変換する。組のキーも整数幅を確認する。
復習の核
- 全状態が多く上位だけが少ないとき、最大の出発点と単調な向きを探す。
- 未出力状態への経路を描き、最初の未出力状態がキューに残る理由を説明する。
- 同じ値と同じ状態の重複を区別する。
計算量と制約
時間
三列の整列が 。一回の取り出しにつき追加は高々三件で、全体の候補は 件。優先度付きキューと、登録済み集合に使う平衡二分探索木の各操作は なので、全体は 時間。
空間
入力が 、キューと登録済み集合が なので、合計 。全組は保持しない。
制約との対応
、、。列挙量を から に抑える。要素が正という条件は単調性に使い、順位の範囲は答えに到達できることを保証する。
出典