CodeChef May Challenge 2020 - Not a Real World Problem

• 問題
• AC

部分点について。$N \le 15$なら全探索でよい。$H = 2$なら縦2マスの符号の状態（4通り）を持ちながら左から右にDPすればよさそう。

一般の場合について。燃やす埋めるでできたら話が早いと思ってyosupoさんの記事を眺めると、できそうだ。異なる色に塗ると罰金がかかるタイプの問題であることがポイントか。

以下、yosupoさんのフレームワークに従って考える。粒子$i$を正に塗る、負に塗るという言い方を使う。また、粒子$i$の載っているマスに書かれている数を$h_i$とする。

• $h_i \ge 0$の場合: $i$を正に塗ると$p_ih_i$円得られる。負に塗ると$p_ih_i$円失う。→ 最初から$p_ih_i$円持っているとする。$i$を負に塗ると$2p_ih_i$円失う。
• $h_i < 0$の場合: $i$を正に塗ると$p_ih_i$円失う。負に塗ると$p_ih_i$円得られる。→ 最初から$p_ih_i$円持っているとする。$i$を正に塗ると$2p_ih_i$円失う。
• 粒子$i, j$が隣り合っているとき、$i$を正（負）に、$j$を正（負）に塗ると$p_ip_j$円得られる。$i$を正（負）に、$j$を負（正）に塗ると$p_ip_j$円失う。→ 最初から$p_ip_j$円持っているとする。$i$を正（負）に、$j$を負（正）に塗ると$2p_ip_j$円失う。

これをそのままグラフにして、最大フローを流せばよい。

---

ほとんどの$h_{y, x}$に意味がないのはなんだったんだろう…… 誤読を疑って何度も確認してしまった。