はまやんはまやんはまやん

hamayanhamayan's blog

Uncrossed Lines [LeetCode 1035]

https://leetcode.com/contest/weekly-contest-134/problems/uncrossed-lines/

2つの配列A,Bがある。
各配列の要素を横一列に並べる。
A[a]=B[b]となっている要素を直線で結ぶ。
直線が公差しないように結んだときの直線の最大数は?

1≦配列サイズ≦500
1≦A[i],B[i]≦2000

解説

https://leetcode.com/submissions/detail/225442192/

動的計画法を使うが、その中で
テク「遷移が多い場合は貪欲法を使うことで最適であろう遷移を絞ることができる」
を使う。

dp[a][b] := 配列Aのa-1まで、配列Bのb-1まで直線が確定しているときの直線の最大数
まず、これの状態数はO(N^2)なので、遷移はO(1)かO(logN)くらいに収めたい。
dp[a][b]からの遷移を考えると、

1. 直線を作らない → dp[a+1][b], dp[a][b+1]へ+0で遷移
2. A[a]と配列Bのどれかで直線を作る → A[a]=B[bb]、b≦bbのとき、dp[a+1][bb+1]へ+1で遷移
3. B[b]と配列Aのどれかで直線を作る → A[aa]=B[b]、a≦aaのとき、dp[aa+1][b+1]へ+1で遷移

1.は遷移数が2つで、2と3が場合によっては、O(N)になってしまう。
2と3の遷移数が多いが、A[a]とB[bb]で直線を作るときに最も近いbbを選ぶのが最も最適である。
わざわざ遠くを選ぶ必要もないので、最も近いbbだけ採用することで、遷移が1つになる。
この最も近いbbは
VB[b] := B[i]=bであるiのソート済み配列
を持っておけば、O(logN)で持ってこれる。
3.でも2.と同様のことを行えば、遷移処理全体はO(logN)で済む。
 
これで全体O(N^2logN)でAC。

class Solution {
public:
	int maxUncrossedLines(vector<int>& A, vector<int>& B) {
		int NA = A.size();
		int NB = B.size();

		vector<vector<int>> VA(2010), VB(2010);
		rep(i, 0, NA) VA[A[i]].push_back(i);
		rep(i, 0, NB) VB[B[i]].push_back(i);

		vector<vector<int>> dp(NA + 2, vector<int>(NB + 2, 0));
		dp[0][0] = 0;
		rep(a, 0, NA + 1) rep(b, 0, NB + 1) {
			chmax(dp[a + 1][b], dp[a][b]);
			chmax(dp[a][b + 1], dp[a][b]);

			// featuring A[a]
			if (a < NA) {
				auto ite = lower_bound(all(VB[A[a]]), b);
				if (ite != VB[A[a]].end()) {
					int bb = *ite;
					chmax(dp[a + 1][bb + 1], dp[a][b] + 1);
				}
			}

			// featuring B[b]
			if (b < NB) {
				auto ite = lower_bound(all(VA[B[b]]), a);
				if (ite != VA[B[b]].end()) {
					int aa = *ite;
					chmax(dp[aa + 1][b + 1], dp[a][b] + 1);
				}
			}
		}

		return dp[NA][NB];
	}
};