ABC008 D - 金塊ゲーム

概要

D - 金塊ゲーム

W×Hマスの各マスに金が置いてある。またそのうちNマスに金を回収する機械が置いてある。
金を回収する機械を動作させると、その機械が置いてある行・列の金をすべて回収することが出来る。
ただし機械を動作させたとき、機械のマスから行方向・列方向に隣接マスを辿り、すでに金が回収されている列・行に突き当たると、
それより先のマスの金を回収することはできない。すなわり、金の回収具合は機械を動作させる順番に依存する。
回収できる金の最大値を答えよ。

制約

1 ≦ N ≦ 30
1 ≦ W, H ≦ 10^6

方針

メモ化再帰を使う。メモする内容は、
memo(l, r, t, b) : l行目からr行目、t列目からb行目の長方形領域で得られる金の最大値

メモのイメージ。
長方形領域内に機械がなければ、その長方形領域から得られる金は0。
長方形領域内(l, r, t, b)に機械が1つあれば、その機械で得ることが出来る金はr - l + b - t + 1。
長方形領域内に機械が複数あれば、機械を順番に使って長方形領域を狭めてゆく。

機械を使う順番は明示的に与えるのでなく、
再帰関数を用いつつうまく領域内にある機械だけを使ってゆく。

感想

kmjpさんの解答を参考にしました。
kmjp.hatenablog.jp

この解法は正直思いつかない。。
計算量が十分小さいかの確認ができていないので、要確認。

ABC D問題最難候補
・ABC 008 D 金塊ゲーム (体感 700 点)
・ABC 017 D サプリメント (体感 700 点)
・ABC 020 D LCM Rush (101点の方、体感 800 点)
・ABC 024 D 動的計画法 (体感 600 点)
・ARC 084 D Small Multiple (700 点)

— けんちょん (@drken1215) May 29, 2018

ABC-D最難候補とのことです。同感です。。

解答

Submission #4390070 - AtCoder Beginner Contest 008

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef tuple<int, int, int, int> i4;
 
const int max_n = 33;
 
int W, H;
int N;
 
int X[max_n], Y[max_n];
 
map<i4, ll> memo;
 
ll dfs(int l, int r, int t, int b){
	// cout << l << "," << r << "," << t << "," << b << endl;
 
	if(r < l || b < t) return 0;
	i4 x = make_tuple(l, r, t, b);
 
	if(memo.find(x) != memo.end()) return memo[x];
 
	memo[x] = 0;
	for(int i = 0; i < N; i++){
		if(l <= X[i] && X[i] <= r && t <= Y[i] && Y[i] <= b){
			memo[x] = max(memo[x]
				      , r - l + b - t + 1
					    + dfs(l, X[i]-1, t, Y[i]-1)
					    + dfs(X[i]+1, r, t, Y[i]-1)
					    + dfs(l, X[i]-1, Y[i]+1, b)
					    + dfs(X[i]+1, r, Y[i]+1, b));
		}
	}
 
	return memo[x];
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> W >> H;
	cin >> N;
 
	rep(i, N) cin >> X[i] >> Y[i];
	cout << dfs(1, W, 1, H) << endl;
}