考察
行を一つ固定すると、列の合計が大きいほど得点も大きくなりそうだ。ただし、行と列の交点に書かれた値は二重に数えるので、その分を引く必要がある。列の合計が大きい順に調べ、初めて交点の値が0になれば、それ以降を調べずに済む。この打切りまでの試行を、入力されたマスの個数で数える。
まず得点を式にする。マス の値を とし、入力に現れないマスでは とする。行 の値の合計を 、列 の値の合計を とおく。 では交点だけを2回数えるため、行 、列 を選んだ得点は
となる。行和・列和と、入力された交点の値をそれぞれ辞書に集計すれば、この式を評価できる。
入力に現れる行数を 、列数を とする。どちらも 以下だが、全交点を調べると 回、最大で 回の評価が必要になる。そこで行を固定し、どの列なら調べずに省けるかを考える。入力に現れない行・列を候補から外してよい理由は、正当性で確認する。
行 が固定されている間は が共通なので、まず列和の大きい列を見たい。しかし、そこに大きな値が書かれていると、交点の減算で得点が下がる。例えば、次の小さな盤面を考える。0は入力に現れないマスを表す。
行1を固定すると、列1の得点は 、列2の得点は である。最大の列和を持つ列だけでは、この行の最適値を見逃す。
一方、交点が空なら減算は0で、その列和をそのまま得点に足せる。列和の降順で最初に見つけた空交点は、後続のどの列よりも悪くならない。 後続の列和はそれ以下で、交点の補正で得点が増えることもないからである。これが打切りの根拠になる。
具体的な手順は次のとおり。
- 入力の各マスについて行和・列和を加算し、座標の組をキーに値を保存する。
- 入力に現れる列を列和の降順に並べる。列和が等しい列の順序は任意でよい。
- 答えを0で初期化する。入力に現れる各行について、列を先頭から調べ、 で答えを更新する。
- 調べた交点が入力に現れなければ、その得点を評価してからその行の走査を終える。空交点がなければ、最後の列まで評価する。
二重ループでも、各行で必ず全列を見るわけではない。走査が続くのは入力されたマスに当たったときだけなので、総試行数は疎な入力の個数から評価できる。
典型の発動条件
疎行列の行列和集約
値が書かれた少数のマスだけが与えられ、行・列の和を組み合わせる問題では、行和・列和と交点の補正へ分解する。巨大な盤面そのものを作らず、入力に現れる座標と値だけを保持する。ただし、候補の行・列まで入力に現れるものへ限定するには、値の非負性などの根拠を別に確認する。
上界順探索の早期打切り
候補の得点が「基礎値から非負の補正を引く」形なら、基礎値は得点の上界になる。上界の降順に調べ、補正が0の候補を得た時点で、後続の上界に追いつかれることはない。補正が負になり得る問題では、この理由で打ち切れない。
問題固有の要素
本問では、補正が必要な交点は入力された マスに限られる。「補正なしの候補に当たるまで進む」という探索にすると、走査を続ける各試行が疎な入力の一つに対応する。値の上界による候補の省略と、例外の個数による計算量の評価を組み合わせるのが鍵である。
正当性
まず、入力に現れない行を選んだ場合、得点は選んだ列の列和だけになる。これを入力に現れる任意の行 へ替えても、 なので得点は減らない。同様に、入力に現れない列を入力に現れる任意の列へ替えても、 により得点は減らない。 なので、替え先の行・列は存在する。従って、入力に現れる行と列の組だけで最大値を達成できる。
次に行 を固定する。列和の降順で最初に見つかる空交点の列を とする。この列以後の任意の列 では、降順より 、値の非負性より だから、
が成り立つ。従って、そこまでに評価した得点の最大値がその行の最適値である。空交点がない行では全列を評価するので、やはり最適値を得る。これを候補の全行で行い最大を取れば、盤面全体の答えになる。
実装上の注意
- 行和・列和は最大 になる。加減算の途中も含め、64ビット整数で扱う。
- 交点の検索には、元の行・列の座標の組をキーにする。空交点を検索するたびに辞書へ値0を挿入する必要はない。
- 一行だけなら、その行の全列が入力済みであり、打ち切らず全列を調べる。一列だけの場合も、各行の唯一の交点を評価する。 なら、そのマスの値がそのまま答えになる。
- 列和が同値でも、正当性の不等式は等号を許すため、どちらを先に調べてもよい。最初の空交点を評価する前に終了しないことに注意する。
復習の核
- 行と列を合わせた得点は、二重計上する交点を引いて表す。減算を忘れると、列和だけによる選択を正当化してしまう。
- 「上界の降順」と「補正が非負」を揃え、補正が0になった候補で打ち切る。
- 二重ループの総量は、続行する試行を入力の例外へ、停止する試行を外側の反復へ対応させて数える。
計算量と制約
時間
列和による整列は 時間。全行を合わせた交点の試行数は、次の二種類に分けて数える。
- 入力済みの交点を調べる試行は、同じ行で同じ列を再訪しないため、相異なる入力マスへ一対一に対応する。合計で 回以下である。
- 空交点を調べる試行は、その直後に打ち切るため、一行につき高々1回、合計で 回以下である。
空交点のない行で最後まで調べる分も、前者に含まれる。従って総試行数は 以下であり、走査は各検索を除けば 時間である。
ハッシュ表の検索・加算が期待 時間なら、集計に期待 時間、走査に期待 時間を使う。整列も含めて全体で期待 時間となる。平衡二分探索木の辞書を使う場合は各操作が 時間かかるが、集計・検索の回数は なので、全体で最悪 時間に収まる。
空間
行和が 個、列和と整列用の配列が 個、入力済み交点の値が 個なので、全体で 空間を使う。
制約との対応
、 で、入力の座標の組は相異なる。座標の大きさに比例する配列は作らず、行・列・交点の辞書を使う。 なので整列と総走査数は制約内に収まる。打切りと候補の限定には、入力値が正で、未入力のマスが0という条件を使っている。
出典