ABC 298 F — Rook Score

考察

行を一つ固定すると、列の合計が大きいほど得点も大きくなりそうだ。ただし、行と列の交点に書かれた値は二重に数えるので、その分を引く必要がある。列の合計が大きい順に調べ、初めて交点の値が0になれば、それ以降を調べずに済む。この打切りまでの試行を、入力されたマスの個数で数える。

まず得点を式にする。マス (r,c)(r,c) の値を vr,cv_{r,c} とし、入力に現れないマスでは vr,c=0v_{r,c}=0 とする。行 rr の値の合計を RrR_r、列 cc の値の合計を CcC_c とおく。Rr+CcR_r+C_c では交点だけを2回数えるため、行 rr、列 cc を選んだ得点は

S(r,c)=Rr+Cc−vr,cS(r,c)=R_r+C_c-v_{r,c}

となる。行和・列和と、入力された交点の値をそれぞれ辞書に集計すれば、この式を評価できる。

入力に現れる行数を HH、列数を WW とする。どちらも NN 以下だが、全交点を調べると HWHW 回、最大で N2N^2 回の評価が必要になる。そこで行を固定し、どの列なら調べずに省けるかを考える。入力に現れない行・列を候補から外してよい理由は、正当性で確認する。

行 rr が固定されている間は RrR_r が共通なので、まず列和の大きい列を見たい。しかし、そこに大きな値が書かれていると、交点の減算で得点が下がる。例えば、次の小さな盤面を考える。0は入力に現れないマスを表す。

列1列2行和
行1909
行2088
列和98

行1を固定すると、列1の得点は 9+9−9=99+9-9=9、列2の得点は 9+8−0=179+8-0=17 である。最大の列和を持つ列だけでは、この行の最適値を見逃す。

一方、交点が空なら減算は0で、その列和をそのまま得点に足せる。列和の降順で最初に見つけた空交点は、後続のどの列よりも悪くならない。 後続の列和はそれ以下で、交点の補正で得点が増えることもないからである。これが打切りの根拠になる。

具体的な手順は次のとおり。

  1. 入力の各マスについて行和・列和を加算し、座標の組をキーに値を保存する。
  2. 入力に現れる列を列和の降順に並べる。列和が等しい列の順序は任意でよい。
  3. 答えを0で初期化する。入力に現れる各行について、列を先頭から調べ、Rr+Cc−vr,cR_r+C_c-v_{r,c} で答えを更新する。
  4. 調べた交点が入力に現れなければ、その得点を評価してからその行の走査を終える。空交点がなければ、最後の列まで評価する。

二重ループでも、各行で必ず全列を見るわけではない。走査が続くのは入力されたマスに当たったときだけなので、総試行数は疎な入力の個数から評価できる。

典型の発動条件

疎行列の行列和集約

値が書かれた少数のマスだけが与えられ、行・列の和を組み合わせる問題では、行和・列和と交点の補正へ分解する。巨大な盤面そのものを作らず、入力に現れる座標と値だけを保持する。ただし、候補の行・列まで入力に現れるものへ限定するには、値の非負性などの根拠を別に確認する。

上界順探索の早期打切り

候補の得点が「基礎値から非負の補正を引く」形なら、基礎値は得点の上界になる。上界の降順に調べ、補正が0の候補を得た時点で、後続の上界に追いつかれることはない。補正が負になり得る問題では、この理由で打ち切れない。

問題固有の要素

本問では、補正が必要な交点は入力された NN マスに限られる。「補正なしの候補に当たるまで進む」という探索にすると、走査を続ける各試行が疎な入力の一つに対応する。値の上界による候補の省略と、例外の個数による計算量の評価を組み合わせるのが鍵である。

正当性

まず、入力に現れない行を選んだ場合、得点は選んだ列の列和だけになる。これを入力に現れる任意の行 rr へ替えても、Rr−vr,c≥0R_r-v_{r,c}\geq 0 なので得点は減らない。同様に、入力に現れない列を入力に現れる任意の列へ替えても、Cc−vr,c≥0C_c-v_{r,c}\geq 0 により得点は減らない。N≥1N\geq 1 なので、替え先の行・列は存在する。従って、入力に現れる行と列の組だけで最大値を達成できる。

次に行 rr を固定する。列和の降順で最初に見つかる空交点の列を c∗c^* とする。この列以後の任意の列 cc では、降順より Cc≤Cc∗C_c\leq C_{c^*}、値の非負性より vr,c≥0v_{r,c}\geq 0 だから、

Rr+Cc−vr,c≤Rr+Cc≤Rr+Cc∗=S(r,c∗)R_r+C_c-v_{r,c}\leq R_r+C_c\leq R_r+C_{c^*}=S(r,c^*)

が成り立つ。従って、そこまでに評価した得点の最大値がその行の最適値である。空交点がない行では全列を評価するので、やはり最適値を得る。これを候補の全行で行い最大を取れば、盤面全体の答えになる。

実装上の注意

  • 行和・列和は最大 2×10142\times 10^{14} になる。加減算の途中も含め、64ビット整数で扱う。
  • 交点の検索には、元の行・列の座標の組をキーにする。空交点を検索するたびに辞書へ値0を挿入する必要はない。
  • 一行だけなら、その行の全列が入力済みであり、打ち切らず全列を調べる。一列だけの場合も、各行の唯一の交点を評価する。N=1N=1 なら、そのマスの値がそのまま答えになる。
  • 列和が同値でも、正当性の不等式は等号を許すため、どちらを先に調べてもよい。最初の空交点を評価する前に終了しないことに注意する。

復習の核

  • 行と列を合わせた得点は、二重計上する交点を引いて表す。減算を忘れると、列和だけによる選択を正当化してしまう。
  • 「上界の降順」と「補正が非負」を揃え、補正が0になった候補で打ち切る。
  • 二重ループの総量は、続行する試行を入力の例外へ、停止する試行を外側の反復へ対応させて数える。

計算量と制約

時間

列和による整列は O(Wlog⁡W)O(W\log W) 時間。全行を合わせた交点の試行数は、次の二種類に分けて数える。

  • 入力済みの交点を調べる試行は、同じ行で同じ列を再訪しないため、相異なる入力マスへ一対一に対応する。合計で NN 回以下である。
  • 空交点を調べる試行は、その直後に打ち切るため、一行につき高々1回、合計で HH 回以下である。

空交点のない行で最後まで調べる分も、前者に含まれる。従って総試行数は N+HN+H 以下であり、走査は各検索を除けば O(N+H)O(N+H) 時間である。

ハッシュ表の検索・加算が期待 O(1)O(1) 時間なら、集計に期待 O(N)O(N) 時間、走査に期待 O(N+H)O(N+H) 時間を使う。整列も含めて全体で期待 O(Nlog⁡N)O(N\log N) 時間となる。平衡二分探索木の辞書を使う場合は各操作が O(log⁡N)O(\log N) 時間かかるが、集計・検索の回数は O(N)O(N) なので、全体で最悪 O(Nlog⁡N)O(N\log N) 時間に収まる。

空間

行和が HH 個、列和と整列用の配列が WW 個、入力済み交点の値が NN 個なので、全体で O(N+H+W)=O(N)O(N+H+W)=O(N) 空間を使う。

制約との対応

1≤N≤2×1051\leq N\leq 2\times 10^5、1≤ri,ci,xi≤1091\leq r_i,c_i,x_i\leq 10^9 で、入力の座標の組は相異なる。座標の大きさに比例する配列は作らず、行・列・交点の辞書を使う。H,W≤NH,W\leq N なので整列と総走査数は制約内に収まる。打切りと候補の限定には、入力値が正で、未入力のマスが0という条件を使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Rook Score の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

      この解説で扱わないこと:

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題