Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 298 F問題 Rook Score

AtCoder ABC ABC298 F問題 500 pts

問題
提出解答
問題の概要
- 制約
解法 1 (座標圧縮)
解法 2 (方針)
解法 3 (高速化)

問題

提出解答

問題の概要

$10^9$ 行 $10^9$ 列からなるマス目があり, 上から $r$ 行目, 左から $c$ 列目のマスを $(r,c)$ と書くことにする.

$i=1,2, \dots, N$ に対して, $(r_i, c_i)$ には正の整数 $x_i$ が, それ以外の $(10^{18}-N)$ 個のマスには $0$ が書かれている.

$1$ 以上 $10^9$ 以下の整数の組 $(R,C)$ を選び, $R$ 列目または $C$ 行目である $(2 \times 10^9-1)$ 個のマスにかかれている整数の総和を $S$ とする.

$S$ として考えられる最大値を求めよ.

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq r_i, c_i \leq 10^9$
$1 \leq x_i \leq 10^9$
$i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$

解法 1 (座標圧縮)

$R$ 列目または $C$ 行目である $(2 \times 10^9-1)$ 個のマスにかかれている整数の総和 $S$ のことを $S(R,C)$ と書くことにする.

ここで, $R$ 行目にのマス書かれている $10^9$ 個の整数の総和を $A_R$ , $C$ 列目にのマス書かれている $10^9$ 個の整数の総和を $B_C$ , $(R,C)$ に書かれている整数を $X_{R,C}$ と書くことにすると,

$S(R,C)=A_R+B_C-X_{R,C}$

が成り立つ.

ここで, 制約から $A_R-X_{R,C} \geq 0$ であるので, $S(R,C)$ を最大にするような選び方で $A_R \gt 0$ となるような $(R,C)$ の選び方が存在する. 同様にして, $B_C \gt 0$ であるような選び方も存在する.

よって, 最初から $(R,C)$ については $A_R, B_C \gt 0$ であるようなものについて制限してもよい.

また, 必要ならば行 (列) の削除と行 (列) 番号の付け直しを行うことにより, $N$ 行 $N$ 列の問題であるとしてもよい. これ以降ではそれを仮定する.

解法 2 (方針)

$R$ の選び方を場合分けする. $R$ を固定する. このとき, 次のようにすることで $R$ を固定した場合の最大値を求めることができる.

$r_i=R$ であるような $i$ 全てに対して $A_R+B_{c_i}-X_{R,c_i}$ を計算する.
上での計算の $c_i$ として登場しなかった全ての $c$ に対して, $X_{R,c}=0$ であることに注意して, $A_R+B_c$ の最大値を求める.

解法 3 (高速化)

この計算は次のようにして計算できる.

多重集合 $E$ を用意し, $E:=\{B_c \mid c=1,2, \dots, N\}$ とする.
の順に行う (なお計算するには最大値の判定も含めることにする).
- $r_i=R$ であるような $i$ 全体の集合を $I_R$ とする. 各 $i \in I_R$ に対して, $A_R+B_{c_i}-X_{R, c_i}$ を計算し, $E$ から $B_{c_i}$ を削除する.
- $A_R+\max E$ を計算する.
- 各 $i \in I_R$ に対して, $E$ に $B_{c_i}$ 追加する.
最大値を返す.

この $E$ の管理としては順序付き集合やセグメントツリーを利用することによって, 全体で $O(N \log N)$ 時間で計算できる.