백준15974 공룡 발자국

작성일 | In

문제 링크

  • http://icpc.me/15974

문제 출처

  • 2018 KOI 중등부 4번

사용 알고리즘

  • DP
  • sliding window

시간복잡도

  • $O(N^2 log N)$

풀이

2018년 문제는 BOJ에서 서브태스크를 지원해주길래, 서브태스크를 따라서 풀어봤습니다.

Subtask 1(14점)

모든 점이 발자국에 포함됩니다. 발뒤꿈치를 잡고, 각도 순으로 정렬해주면 됩니다.
코드

Subtask 2(26점)

모든 경우의 수를 $O(2^N N^3)$ 정도의 시간으로 확인해볼 수 있습니다. 계속 답이 안 나오길래 막 짜다보니 코드가 조금 더러워졌습니다…
코드

Subtask 3(55점)

이제부터 점점 100점 풀이에 다가가기 시작합니다.

$DP(0, i, j)$ = 마지막으로 선택한 점이 j, 마지막에서 두 번째로 선택한 점이 i이면서 j가 발가락인 경우
$DP(1, i, j)$ = j가 골인 경우처럼 dp를 잘 정의하고 문제를 풀어봅시다.

$DP(0, i, j)$은 적당한 k들에 대해 $max(dp(1, k, i)) + 1$이고, DP(1, i, j)도 적당한 k들에 대해 $max(dp(0, k, i)) + 1$입니다.

각 상태마다 적당한 k들에 대해 모두 탐색을 해준다면 $O(N^3)$에 정답을 구할 수 있습니다. 답을 역추적하기 위해서 $DP(*, i, j)$가 최대가 되는 k도 같이 저장해야 합니다.
코드

Subtask 4(100점)

Subtask 3에서의 풀이를 $O(N^2)$ 혹은 $O(N^2 log N)$ 정도로 최적화해야합니다.
$DP(t, k, i)$를 모두 계산해놓은 상태에서 $DP(1-t, i, j)$를 계산하는 방식으로 dp table을 채울 것입니다.
발뒷꿈치를 기준으로 각도 순으로 정렬한 상황에서, k는 i보다 먼저 나오고, j는 i보다 나중에 나옵니다. i를 기준으로 먼저 나오는 점들과 나중에 나오는 점들을 각각 나눠서 점 i를 기준으로 정렬합시다.

$DP(1-t, i, j) = max(DP(t, k, i)) + 1$를 그대로 이용할건데, 각 j에 대해 $DP(1-t, i, j)$가 최대가 되는 k는 슬라이딩 윈도우를 통해 구해줄 수 있습니다.

각 i마다 $O(N log N)$에 처리할 수 있기 때문에 총 시간복잡도는 $O(N^2 log N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
typedef pair<double, double> pd;

istream& operator >> (istream &in, p &v){
	in >> v.x >> v.y;
	return in;
}

ostream& operator << (ostream &out, const p &v){
	out << v.x << " " << v.y;
	return out;
}

int ccw(p a, p b, p c){
	ll res = (b.x-a.x)*(c.y-a.y);
	res -= (b.y-a.y)*(c.x-a.x);
	if(res > 0) return 1;
	if(res) return -1;
	return 0;
}

int n;
vector<p> v;

//dp[0][i][j] -> j가 발가락, dp[1][i][j] -> i가 발가락
int dp[2][3030][3030];
int prv[2][3030][3030];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(auto &i : v) cin >> i;
	int idx = 0;
	for(int i=1; i<n; i++) if(v[i].y < v[idx].y) idx = i;
	swap(v[0], v[idx]); sort(v.begin()+1, v.end(), [&](p &a, p &b){
		return ccw(v[0], a, b) > 0;
	});

	for(int i=1; i<n-1; i++){
		vector<int> a(1), b;
		for(int j=1; j<i; j++) if(ccw(v[0], v[j], v[i])) a.push_back(j);
		for(int j=i+1; j<n; j++) if(ccw(v[0], v[i], v[j])) b.push_back(j);
		sort(a.begin(), a.end(), [&](int &aa, int &bb){ return ccw(v[i], v[aa], v[bb]) > 0; });
		sort(b.begin(), b.end(), [&](int &aa, int &bb){ return ccw(v[i], v[aa], v[bb]) > 0; });
		int pv = 0, mx = 0, idx = 0;
		for(auto j : b){
			while(pv < a.size() && ccw(v[a[pv]], v[i], v[j]) > 0){
				int t = a[pv]; pv++;
				if(mx < dp[0][t][i] + 1) mx = dp[0][t][i] + 1, idx = t;
			}
			dp[1][i][j] = mx, prv[1][i][j] = idx;
		}
		pv = mx = idx = 0;
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		for(auto j : b){
			while(pv < a.size() && ccw(v[a[pv]], v[i], v[j]) < 0){
				int t = a[pv]; pv++;
				if(mx < dp[1][t][i] + 1) mx = dp[1][t][i] + 1, idx = t;
			}
			dp[0][i][j] = mx, prv[0][i][j] = idx;
		}
	}

	int mx = 0, x = 0, y = 0;
	for(int i=1; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(ccw(v[0], v[i], v[j]) != 1) continue;
			if(mx < dp[0][i][j]){
				mx = dp[0][i][j]; x = i, y = j;
			}
		}
	}
	if(!mx){
		cout << 0; return 0;
	}
	vector<int> ans; ans.push_back(y); ans.push_back(x);
	while(ans.back() != 0){
		int t = ans.size();
		ans.push_back(prv[t&1][ans[t-1]][ans[t-2]]);
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for(auto i : ans) cout << v[i] << "\n";
}