Kazun の競プロ記録

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

AtCoder Beginner Contest 259 G問題 Grid Card Game

AtCoder ABC ABC259 G問題 600 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

H 行 W 列のグリッドがあり, 各マスには整数が書かれたカードがある. 上から i 行目, 左から j 列目にあるカードに書かれている整数は A_{i,j} である.

高橋君と青木君は次のゲームを行う.

  • 高橋君は H 個ある行のうちいくつかの行を選び, その選んだ行それぞれにあるカードの上に赤いコマを置く.
  • 青木君は W 個ある列のうちいくつかの列を選び, その選んだ列それぞれにあるカードの上に青いコマを置く.
  • その後, 次のようにして得点を決定する.
    • 赤いコマと青いコマの両方が置かれており, 負の整数が書かれているカードが存在するならば, 得点は -10^{100} 点.
    • 上記のようなカードが存在しない場合は1つでもコマが置かれているカードに書かれている整数の総和がそのまま得点になる.

可能な得点の最大値を求めよ.

制約

  • 1 \leq H,W \leq 100
  • -10^9 \leq A_{i,j} \leq 10^9

解法

まず, なにもコマを置かない場合が 0 点なので, -10^{100} 点が最大値になることはない. よって, -10^{100} 点に関するルールを次のようにしてもよい.

  • 負の整数が書かれているカードには赤いコマと青いコマの両方を置いてはいけない.

R:=\{r_1, \dots, r_H\}, C:=\{c_1, \dots, c_W\} をそれぞれ i 行目全体を表す集合, j 列目全体を表す集合とし, X:=R \cup C とする.

このとき, \operatorname{Map}(X, \{0,1\}) を X から \{0,1\} への写像全体の集合としたとき, \operatorname{eval}: \operatorname{Map}(X, \{0,1\}) \to \mathbb{Z} を h \in \operatorname{Map}(X, \{0,1\}) に対して, 以下で定める.

  • \displaystyle \operatorname{eval}(h):=\sum_{k \in Y} \mu_k(h). ただし, Y:=R \cup C \cup R \times C とする.
\mu_{r_i}(h)=\begin{cases} \sum_{j=1}^W A_{i,j} & (h(r_i)=1) \\ 0 & (h(r_i)=0) \\ \end{cases}
\mu_{c_j}(h)=\begin{cases} \sum_{i=1}^H A_{i,j} & (h(c_j)=1) \\ 0 & (h(c_j)=0) \\ \end{cases}
\mu_{r_i, c_j}(h)=\begin{cases} \begin{cases} -A_{i,j} & (A_{i,j} \geq 0) \\ -\infty & (A_{i,j} \lt 0) \end{cases} & (h(r_i)=h(c_j)=1) \\ 0 & ({\rm otherwise}) \\ \end{cases}

h(r_i)=1, h(c_j)=1 はそれぞれ i 行目, j 列目を選ぶことを意味し, h(r_i)=0, h(c_j)=0 はそれぞれ i 行目, j 列目を選ばないことを意味する.

ここで, \bullet': \operatorname{Map}(X, \{0,1\}) \to \operatorname{Map}(X, \{0,1\}) を h \in \operatorname{Map}(X, \{0,1\}) に対して以下で定める.

h'(r_i)=h(r_i), \quad h'(c_j)=1-h(c_j)

このとき, \bullet' は全単射であり, 各 \mu_k(h') は

\mu_{r_i}(h')=\begin{cases} \sum_{j=1}^W A_{i,j} & (h'(r_i)=1) \\ 0 & (h'(r_i)=0) \\ \end{cases}
\mu_{c_j}(h')=\begin{cases} \sum_{i=1}^H A_{i,j} & (h'(c_j)=0) \\ 0 & (h'(c_j)=1) \\ \end{cases}
\mu_{r_i, c_j}(h')=\begin{cases} \begin{cases} -A_{i,j} & (A_{i,j} \geq 0) \\ -\infty & (A_{i,j} \lt 0) \end{cases} & (h'(r_i)=1, h'(c_j)=0) \\ 0 & ({\rm otherwise}) \\ \end{cases}

である. このような形に変形すると, 最大フローを利用する最小カット問題に帰着できる.

よって, 最大フロー問題を解くことにより, N:=\max(H,W) として時間計算量 O(N^4) で解くことができた.