Hyper Knights (UVa Live Archive Asia - Site 9 (Bangladesh) - 2010/2011 Dhaka (Bangladesh))

UVa Live Archive Online Judge

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4862

問題

一部が緑、赤に塗られたn*mのボードがある。ボードの各マスには数値が書かれている。そのボードにハイパーナイトを置いて行き、ハイパーナイトが置かれているマスの数値の合計が得点になる。条件としては、

  • 各マスにはハイパーナイトは1体しか置けない
  • 緑のマスにはハイパーナイトを置かなければならない
  • 赤のマスにはハイパーナイトを置いてはいけない
  • ハイパーナイトは互いに攻撃する位置に置いてはいけない
  • ハイパーナイトは最低1体置かなければならない

がある。ハイパーナイトは縦3横1または横3縦1先に進むことができる。得点の最大値とその時のハイパーナイトの位置(辞書順最小)を答えよ。
1<=m,n<=30
赤のマス

解法

ボードのマスの得点をaijと表記する。
まず、ハイパーナイトが置けるマスの得点が全て0以下の場合、最も得点が高いマスに一体ハイパーナイトを置くのが答え。
普通の場合は、ハイパーナイトの動ける部分を考えるとボードは二部グラフ2つで表現できる。なので得点の最大値はプログラミングコンテストチャレンジブックの最後の問題(GCJ2008 WorldFinal E問題)で書かれた方法を用いてs-t最小カットで求めることができる。
具体的に言うと得点が0以下のマス、赤色のマスを取り除き、二部グラフの頂点をU,Vに分割したとする。Uの緑のマスはsとINFで繋ぎ、Uの通常のマスはsとaijで繋ぐ。Vの緑のマスはtとINFで繋ぎ、Vの通常のマスはtとaijで繋ぐ。UとVの間はハイパーナイトが互いに攻撃する位置ならばINFで繋ぐ。このグラフをs-t最小カットすると得点の最大値を求めることができる。
次に辞書順最小なハイパーナイトの置き方を求める。考え方としては、左上のマスからマスを緑に塗って、得点が最大になるかをチェックすればよい。それだと遅すぎるので、最初に求めたs-tカットにINFの辺を追加してsからtにたどり着けるかどうかで、そのマスを使用すべきかどうかチェックする。
最後に辞書順最小になるように0のマスを使うかどうかをチェックする。
アルゴリズム的にも難しいし、コーナーケースも多いし、TLEも厳しい(というかUVa Live ArchiveのPCが遅い)ので大変な問題だった。