AtCoder Beginner Contest 225 G 問題 X - Kazun の競プロ記録

問題

提出解答

問題の概要

縦 $H$ 行, 横 $W$ 行からなるマス目がある. マス $(i,j)$ にバツ印を書くと, $A_{i,j}$ 点入る. 一方で, 1本の斜め線を引くごとに $C$ 点失う. ここで, 斜めに隣接するマスに対して, 斜め線はまとめて引くことができる. 最大で獲得できる点数を求めよ. ただし, 完成後の状態において, 各マスはバツ印が完成しているか, 全く斜め線が引かれていない状態でなくてはならず, どちらか1本のみが引かれていることは許されない.

制約

$1 \leq H,W \leq 100$
$1 \leq A_{i,j} \leq 10^9$
$1 \leq C \leq 10^9$

解法

各マスについて, 「バツ印をつける」か「バツ印をつけない」かという $2$ 択があり, 複数のマスに関する条件がたくさんある. このことから, Project Selection Problem (または, 燃やす埋める問題) という問題を解くことになる.

この問題は, 集合 $X$ から $\{0,1\}$ への関数 $h$ について, $h$ の評価値 $\operatorname{eval}(h)$ を最大化する問題である. ここで, 評価値の計算方法は, 以下のような形が可能であり, これらの総和で表せる ( $x,y,x_1,x_2,\dots,x_n \in X$ , $a$ は整数, $a^+$ は $0$ 以上の整数, $a^-$ は $0$ 以下の整数を表すとする).

$h(x)=0$ のとき, $a$ 点
$h(x)=1$ のとき, $a$ 点
$h(x)=0, h(y)=1$ のとき, $a^-$ 点
$h(x_1)=h(x_2)=\dots=h(x_n)=0$ のとき, $a^+$ 点
$h(x_1)=h(x_2)=\dots=h(x_n)=1$ のとき, $a^+$ 点

今回の問題へ帰着する. $X$ をマス目全体の集合とし, $h: X \to \{0,1\}$ を各マス $(i,j) \in X$ に対して, バツ印を書くならば, $h( (i, j))=1$ , 書かないならば, $h( (i, j) )=0$ とする.

$h( (i,j) )=1$ とさせたとき, 基本的には斜め線 $2$ 本を書いて, $A_{i,j}$ 点を得ることから, $h( (i,j) )=1$ のとき, $A_{i,j}-2C$ 点得ると考える.

また, 斜めに隣接する $2$ つのマス目 $(i,j), (i',j')$ に対して, この $2$ つのマス共にバツ印を書くと, 斜め線を $1$ 本省略できるので, $C$ 点だけ得する. よって, $h( (i,j) )=h( (i',j') )=1$ のとき, $C$ 点を獲得するという条件を追加する. この条件は $C \geq 0$ であるから, 条件の条件を満たす.