CF519 D - Mysterious Crime

Codeforces

超凡ミスで2問落としてまた1893まで落ちちゃった
マジで深夜はパフォーマンス落ちる

問題

長さnの順列がm個与えられる
それぞれの順列の先頭と末尾からいくつかの数字を消し、全ての順列を一致させたい
数字の消し方は何通りあるか

1 <= n <= 10^5
1 <= m <= 10

解法

1個目の順列が 1,2,3,... となるように各順列の数字を変換する
(2,1,4,3 -> 1,2,3,4 とすると 2->1, 1->2, 4->3, 3->4 という変換ルールが出来るということ)
すると、最終的な数列のうち1個目の順列のk番目を左端とするものの最長の長さは
min(各順列のkから右にk+1, k+2, ...と1ずつ増えていくような列の長さの最大値)
となる
この長さの最大値は単純なdpで求められる
左端と最長の長さLが決まれば、kを左端とする長さ1,2,...,Lの数列は全て作れるから、左端を全部試して答えにLを足していけばいい

今見るとめちゃくちゃ簡単なんだけど眠すぎてボケてたのか、本番では長さの最大値をdpするって発想が出てこなくて二分探索してた
二分探索だと4,5,6と4,6,5の区別が付かないからダメ & 計算量的にも危険

int n, m, a[11][100100], res, p[11][100100], dp[11][100100];
map<int,int> con;

signed main() {
	cin >> n >> m;
	rep(i,m) rep(j,n) cin >> a[i][j];
	rep(i,n) con[a[0][i]] = i+1;
	rep(i,m) rep(j,n) a[i][j] = con[a[i][j]], p[i][a[i][j]] = j;
	rep(i,m) for (int j=n-1; j>=0; j--) {
		if (a[i][j]==a[i][j+1]-1) dp[i][j] = dp[i][j+1] + 1;
		else dp[i][j] = 1;
	}
	reps(j,1,n+1) {
		int mn = 1<<30;
		rep(i,m) chmin(mn, dp[i][p[i][j]]);
		res += mn;
	}
	cout << res << endl;
}

http://codeforces.com/contest/1043/problem/D