AtCoder Educational DP Contest F~J

https://atcoder.jp/contests/dp/tasks

Tasks - Educational DP Contest

 

F.

LCS를 복원하는 문제입니다. dp로 복원해봅시다.

go(i, j)를 S를 i번을 볼 것이고, T를 j번을 볼 것일 때 지금까지 최대로 겹치는 길이로 정의합니다.

우선 안겹치는 경우 다음 전이는 go(i+1, j) 또는 go(i, j+1)입니다. 

겹치는 경우 다음 전이는 1+go(i+1, j+1)이 됩니다. 이렇게 go(0,0)을 호출해서 모든 dp테이블을 만들었습니다.

이제 track(i,j) 함수를 진행시킵니다. 

track(i, j)는 만약 s[i]=t[j]라면 그 dp는 dp[i][j]=dp[i+1][j+1]+1을 만족하는 경우입니다.

따라서 s[i]를 출력해줍니다. 

그 외에는 dp의 최댓값을 따라가주면 됩니다. 즉 겹치지 않는다면 dp[i+1][j]나 dp[i][j+1]로 전이될테니

dp[i+1][j]가 더 크면 track(i+1,j)를 수행해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
string s, t;
int dp[3003][3003];

int go(int i, int j) {
	if (i == s.size() || j == t.size()) return 0;
	int& ret = dp[i][j];
	if (~ret) return ret;
	ret = max(go(i + 1, j), go(i, j + 1));
	if (s[i] == t[j]) {
		ret = max(ret, go(i + 1, j + 1) + 1);
	}
	return ret;
}

void track(int i, int j) {
	if (i == s.size() || j == t.size()) return;
	if (s[i] == t[j]) {
		cout << s[i];
		track(i + 1, j + 1);
	}
	else if (dp[i + 1][j] > dp[i][j + 1]) track(i + 1, j);
	else track(i, j + 1);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s >> t;
	memset(dp, -1, sizeof(dp));
	go(0, 0);
	track(0, 0);
}

 

 

 

G. 

방향그래프에서 제일 긴 경로를 찾아주는 문제입니다. 

dfs를 해주는 식으로 구현하면 모든 점을 1번씩 방문하므로 O(N)에 해줄 수 있습니다. 

dp[i]를 i에서 시작하는 제일 긴 경로라고 정의해주면 dp[i]=dp[ni]+1이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, m, u, v;
vector<int>g[100001];
int dp[100001];

int dfs(int x) {
	int& ret = dp[x];
	if (~ret) return ret;
	ret = 0;
	for (int nx : g[x]) {
		ret = max(ret, dfs(nx) + 1);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	while (m--) {
		cin >> u >> v;
		g[u].push_back(v);
	}	
	memset(dp, -1, sizeof(dp));
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dfs(i));
	}
	cout << ans << '\n';
}

 

 

 

H.

dp[i][j]는 dp[i-1][j]와 dp[i][j-1]에서 옵니다. 단 "#"이 있는 칸만 오지 못하므로 조건에 맞춰 식을 

세워주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, m, dp[1111][1111];
char a[1111][1111];
const int mod = 1e9 + 7;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	dp[1][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i + 1][j] != '#') {
				dp[i + 1][j] += dp[i][j];
				dp[i + 1][j] %= mod;
			}
			if (a[i][j + 1] != '#') {
				dp[i][j + 1] += dp[i][j];
				dp[i][j + 1] %= mod;
			}
		}
	}
	cout << dp[n][m];
}

 

 

 

I. 

dp[i][j]를 i번째까지 앞면이 j개 나오는 확률이라고 정의합시다. 당연히 j<=i입니다. 

dp[i][j]는 (i-1, j)와 (i-1,j-1)에서 왔습니다. 

(i-1, j)에서 온 경우는 현재 뒷면이 나왔다는 의미이므로 1-p[i]를 곱해서 더해주고, 

(i-1,j-1)에서 온 경우는 현재 앞면이 나왔다는 의미이므로 p[i]를 곱해서 더해주면 됩니다. 

답은 dp[n][n/2+1]+....+dp[n][n]이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
double p[3000], dp[3000][3000];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> p[i];
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (i - 1 >= j)dp[i][j] += (1 - p[i]) * dp[i - 1][j];
			if (j) dp[i][j] += p[i] * dp[i - 1][j - 1];
		}
	}
	double ans = 0;
	for (int j = 0; j <= n / 2; j++) {
		ans += dp[n][n - j];
	}
	cout.fixed; cout.precision(10);
	cout << ans << '\n';
}

 

 

 

J.

갑자기 어려워집니다. dp정의부터 만만치 않은 문제입니다. 우선 현재 1개남은것, 2개남은것, 3개남은것,

빈 것의 개수가 필요합니다.  이들의 총합은 일정하므로 3개변수만 관리하면 됩니다. 

dp[i][j][k]를 1개남은것이 i개, 2개남은게 j개, 3개남은게 k개가 되는 기댓값이라 정의합니다. 

case 1.   빈 접시를 뽑은 경우: 확률은 (n-i-j-k)/n입니다. 그리고 곱해지는건 1+dp[i][j][k]입니다.

case 2. 1개 남은걸 뽑은 경우: 확률은 i/n입니다. 그리고 곱해지는건 1+dp[i-1][j][k]입니다.

case 3. 2개 남은걸 뽑은 경우: 확률은 j/n입니다. 그리고 곱해지는건 1+dp[i+1][j-1][k]입니다.

case 4. 3개 남은걸 뽑는 경우: 확률은 k/n입니다. 그리고 곱해지는건 1+dp[i][j+1][k-1]입니다.

이 식을 잘 정리하면 dp table을 채울 수 있습니다. (i, j, k)는 (i-1, j, k)와 (i+1, j-1, k), (i, j+1, k-1)을

참조합니다. 모든 경우마다 idx-1을 참조하는 경우를 포함하므로 갱신이 제대로 됨을 알 수 있습니다. 

기저케이스는 dp[0][0][0]=0으로 해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
double dp[303][303][303];
int n, a[303], cnt[4];

double go(int i, int j, int k) {
	if (!i && !j && !k) return 0;
	double& ret = dp[i][j][k];
	if (ret != -1) return ret;
	double p0, p1, p2, p3;
	p0 = (double)(n - i - j - k) / n;
	p1 = (double)i / n;
	p2 = (double)j / n;
	p3 = (double)k / n;
	ret = p0;
	if (i) ret += p1 * (1 + go(i - 1, j, k));
	if (j) ret += p2 * (1 + go(i + 1, j - 1, k));
	if (k) ret += p3 * (1 + go(i, j + 1, k - 1));
	ret /= (1 - p0);
	return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	fill(&dp[0][0][0], &dp[300][300][300], -1);
	cout << fixed << setprecision(10);
	cout << go(cnt[1], cnt[2], cnt[3]) << '\n';
}