Codeforces 92C (123C) Brackets

問題

各成分が'('または')'であるnxmの行列が、monotonusであるとは、
(1, 1)から右または下に動いて(n, m)へ辿り着いたときにできる括弧文字列が、
どのような動き方をしたとしても対応していることを言う。

monotonusであるような行列を、c[i][j]にしたがって順序をつける。
行列a, bについて、a[i][j] != b[i][j]なる(i, j)のうち、c[i][j]が最小である(i, j)について、
a[i][j] < b[i][j]ならa < bとする。

このような順序をつけて、可能なmonotonusな行列をすべて並べたとき、
k番目に来るものを求めよ。

制約条件

n, m≦100
k≦10^8
1≦p[i][j]≦nmかつすべてのp[i][j]は異なる整数

方針

(i, j)には、(i - 1, j)と(j, i - 1)のどちらからも来られるため、
全てのi, jについて、a[i - 1][j]とa[i][j - 1]が等しい。

したがって、/の向きの斜めの線上に並ぶ要素は全部等しい。
逆にこの条件を見たすなら、どのようにたどっても順路の文字列は同じなので、
ひとつの経路を確かめて、括弧の対応が取れていればmonotonus.

なので、長さn + m - 1の文字列で、順序がk番目のものをもとめればよい。
これは1文字ずつ決めうちして、DPしてく典型的な方法が使える。

文字列のうち、i番目に優先度が高い添え字をo[i]とする。
o[i]を'('に固定して、文字列がk通り作れないなら、o[i]は')'
（残りの文字は未確定にしておいて、何通りあるかはDPで簡単に求まる）

ソースコード

int n, m, p[200][200];
ll k;
ll dp[201][201];

ll calc(const string &s){
	int n = s.size();
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	rep(i, n) rep(j, i + 1) if(dp[i][j]){
		rep(k, 2){
			if(s[i] == '(' && k == 0 || s[i] == ')' && k == 1) continue;
			int nj = j + (k ? 1 : -1);
			if(nj < 0) continue;

			dp[i + 1][nj] = min(dp[i + 1][nj] + dp[i][j], inf);
		}
	}
	return dp[n][0];
}

int main(){
	cin >> n >> m >> k;
	
	rep(i, n) rep(j, m){
		cin >> p[i][j];
		int k = min(i, m - j - 1);
		p[i - k][j + k] = min(p[i - k][j + k], p[i][j]);
	}
	vi o;
	vector<pi> v;
	rep(i, m - 1) v.pb(mp(p[0][i], v.size()));
	rep(i, n) v.pb(mp(p[i][m - 1], v.size()));
	sort(all(v));
	
	int l = v.size();
	rep(i, l) o.pb(v[i].second);
	string s(l, '?');
	
	rep(i, l){
		s[o[i]] = '(';
		ll w = calc(s);
		if(w < k) s[o[i]] = ')', k -= w;
	}
	rep(i, n) rep(j, m) cout << s[i + j] << (j==m-1?"\n":"");
	
	return 0;
}