SCPC 2022 2차 대회가 9월 3일 오후 1시부터 4시간동안 진행되었다.
SCPC 대회와 관련된 정보는 https://research.samsung.com/scpc 에서 찾을 수 있다.
이 게시글에서는 해당 문제의 풀이를 다룬다.
불일치도
요약
0이상 1 이하의 실수 N개가 주어집니다. 이 중 L이상 R이하인 것의 개수를 F(L,R)이라고 합시다. 이 때, 모든 0≤L≤R≤1에 대해, |F(L,R)N−(R−L)|≤D를 만족하는 최소의 실수 D를 구하세요.
풀이
x 이하인 실수의 개수를 f(x)라고 하면, 식은 충분히 작은 ε에 대해 |f(R)−F(L−ε)N−(R−L)| =|(f(R)N−R)−(f(L−ϵ)N−(L−ϵ))+ϵ|이 가질 수 있는 값의 상한을 구하는 문제가 됩니다. 여기서 ϵ은 충분히 작으니까 무시할 수 있기 때문에, f(x)N−x이 가지는 값의 상한과 하한의 차이를 구하는 문제가 됩니다.
N개의 수를 정렬해서 A1,⋯,AN이라고 합시다(편의상 A0=0,A1=1+ε이라고 가정합니다). Ai≤x<Ai+1인 x에 대해 f(x)N−x는 iN−Ai부터 iN−Ai+1 미만까지의 값을 가집니다.
즉, 이 값들의 최솟값과 최댓값을 계산해서 그 차이를 출력해주면 됩니다.
코드
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
|
#include<bits/stdc++.h>
using namespace std;
double solve(vector<double> V) {
int N = V.size();
sort(V.begin(), V.end());
V.insert(V.begin(), 0.0), V.push_back(1.0);
double mn = 1, mx = -1;
for (int i = 0; i <= N; i++) {
mx = max(mx, (double)i / N - V[i]);
mn = min(mn, (double)i / N - V[i + 1]);
}
return mx - mn;
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
for (int t = 1; t <= T; t++) {
int N; cin >> N;
vector<double> V(N);
for (auto &v : V) cin >> v;
cout << "Case #" << t << endl;
cout << fixed << setprecision(12) << solve(V) << endl;
}
}
|
cs |
돌무더기 게임
요약
양의 정수 N 개가 일렬로 있고, A와 B가 게임을 합니다. 정수가 모두 없어질 때까지 다음 행동을 반복합니다.
- A가 현재 있는 정수 중 하나를 고릅니다.
- B는 A가 고른 정수의 왼쪽에 있는 정수를 모두 없애거나, 오른쪽에 있는 정수를 모두 없앱니다.
A는 A가 가져간 정수의 합을 최대화하고 싶고, B는 A가 가져간 정수의 합을 최소화 하고 싶습니다. 두 명이 최선의 선택을 할 때, A가 고른 정수의 합은 무엇일까요?
풀이
동적 계획법 배열 Di, j를 게임을 Ai,⋯,Aj에서 진행했을 때 답이라고 합시다. A가 k번째 수를 가져가면, B는 왼쪽과 오른쪽 중 이후 게임에서 고른 정수의 합이 작은 쪽을 고를 것입니다.
Di, j=(maxi≤k≤jmin(Di, k−1;Dk+1, j)+Ak) 이고, 이를 직접 계산하면 O(N3)이 됩니다.
이제 다음과 같은 관찰을 합시다.
- Di, j≤Di, j+1;Di, j≤Di−1, j
- 가져갈 수 있는 정수가 더 늘어났으므로, A가 가져간 정수의 합은 증가합니다.
- k≤Ki, j에 대해서는 Di, k−1<Dk+1, j이고, k>Ki, j에 대해서는 Di, k−1≥Dk+1, j인 Ki, j가 존재합니다.
- Di,k−1은 k가 증가함에 따라 단조증가하고, Dk+1,j는 k가 증가함에 따라 단조감소하기 때문입니다.
- Ki−1, j≤Ki, j≤Ki, j+1
- k>Ki, j에 대해 Di−1, k−1≥Di, k−1≥Dk+1, j이므로, Ki−1, j≤Ki, j입니다.
- k≤Ki,j에 대해 Di, k−1<Dk+1, j<Dk+1, j+1이므로, Ki, j≤Ki, j+1입니다.
이제 식을 Ki, j를 기준으로 다시 쓸 수 있습니다.
- Ki, j는 Ki−1, j 이상 Ki, j−1 이하에서 차례대로 탐색해서 찾습니다.
- B가 왼쪽을 남기는 경우, Li,j=maxi≤k≤j(Di, k−1+Ak)=max(Li, j−1;Di, j−1+Aj)입니다.
- B가 오른쪽을 남기는 경우, Ri,j=maxi≤k≤j(Ak+Dk+1, j)=max(Ri+1, j,Ai+Di+1, j)입니다.
- Di, j=max(Li, Ki, j,RKi, j+1, j)이고 Ki,j를 기준으로 왼쪽 혹은 오른쪽을 가져갑니다.
Ki, j를 탐색하는데 걸리는 시간은 Ki, j−1−Ki−1, j에 비례합니다. 이를 모든 (i,j)에 대해 더하면 O(N2)이됩니다(i−j가 같은 것끼리 묶으면 항이 상쇄되어서 O(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
|
#include<bits/stdc++.h>
using namespace std;
long long solve(vector<long long> A) {
int N = A.size();
vector<vector<long long>> D(N, vector<long long>(N)), L = D, R = D;
vector<vector<int>> K(N, vector<int>(N));
for (int i = 0; i < N; i++) D[i][i] = L[i][i] = R[i][i] = A[i], K[i][i] = i;
for (int d = 1; d < N; d++) for (int i = 0; i < N - d; i++) {
int j = i + d, k = max(i, i == 0 ? 0 : K[i][j - 1]);
int maxK = min(j - 1, j == N - 1 ? N - 1 : K[i + 1][j]);
while (k < maxK && D[i][k] <= D[k + 2][j]) ++k;
K[i][j] = k;
L[i][j] = max(L[i][j - 1], D[i][j - 1] + A[j]);
R[i][j] = max(R[i + 1][j], A[i] + D[i + 1][j]);
D[i][j] = max(L[i][k], R[k + 1][j]);
}
return D[0][N - 1];
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
for (int tc = 1; tc <= T; tc++) {
int N; cin >> N;
vector<long long> A(N);
for (auto& a: A) cin >> a;
long long ans = solve(A);
cout << "Case #" << tc << '\n' << ans << endl;
}
}
|
cs |
K 등분 2
요약
K등분 문제는 길이 N의 배열과 K가 주어졌을 때, 합이 같은 K개의 (비어있지 않은 연속된) 구간으로 나누는 경우의 수를 구하는 문제입니다. K등분 문제의 답이 정확히 X가 되는 데이터를 만드세요. (X≤1018;1≤K≤N≤180)
풀이
K등분 문제의 풀이를 생각 해봅시다. 전체의 합을 S라고 하면 i번째 구간까지의 누적합은 iSK가 되어야 합니다. 결국 누적합을 구한 이후 (SK,2SK,⋯,(K−1)SK)가 부분수열로 등장하는 경우의 수를 세는 문제입니다.
편의상 K≠0인 경우만 생각하고, K=S라고 생각합시다. 이러면 (1,2,⋯,K−1)가 부분수열로 등장하는 경우의 수를 세는 문제가 됩니다. i번째 수인 Ai로 끝나는 부분수열의 경우의 수를 Di라고 하면 Di=∑j<i; Aj=Ai+1Dj가 됩니다. 이후 Ai=K−1인 i에 대해 Di를 모두 더하면 답이 됩니다.
답이 x인 수열이 있고, 이를 K등분 해야한다고 생각합시다. 이제 K를 1 증가시키고 K를 삽입해 봅시다. 가장 처음으로 등장하는 K−1뒤에 K를 삽입하면, 두 수의 Di 값은 같을 것입니다. 또한 가장 뒤에 K를 삽입하면, 이에 해당하는 Di값은 x일 것입니다. Ai=K−1,Di=1인 i가 있고, 전체 답이 x인 수열을 ax+b로 바꾸는 방법은 다음과 같습니다.
- 처음으로 등장하는 K−1 뒤에 K를 b개 삽입합니다.
- 마지막에 K를 a개 삽입합니다.
여기서 주목할 점은 이를 반복적으로 사용하기 위해서는 항상 b≥1이어야 하고, 수가 a+b개가 늘어난다는 것입니다. a=2,b=1;a=2,b=2를 사용하면 답을 2배씩 늘릴 때 마다 수가 최대 4개 늘어나므로, 240개 정도로 문제를 해결할 수 있습니다.
더 효율적인 방법은 a=4,b=1;a=4,b=2를 함께 사용해서 4x+1 혹은 4x+2꼴의 수의 경우에는 a=4를 사용하는 것입니다. 이제 K≥1에 대해 다음 사실을 증명합시다.
- 답으로 2K 이하의 수를 만들 때, 홀수는 3K−2, 짝수는 3K−1개 이하의 수를 사용하는 것이 가능합니다.
- K=1,2,3일 때: x를 만들기 위해 1을 x개 쓰면 됩니다.
- K>3일 때, x≤2K라고 합시다.
- x=4k+1: k를 만드는 데에 3(K−2)−1개 이하의 수를 사용합니다. 3(K−2)−1+(4+1)=3K−2입니다.
- x=4k+2: k를 만드는 데에 3(K−2)−1개 이하의 수를 사용합니다. 3(K−2)−1+(4+1)=3K−1입니다.
- x=4k+3=2(2k+1)+1: 2k+1을 만드는 데에 3(K−1)−2개 이하의 수를 사용합니다. 3(K−1)−2+(2+1)=3K−2입니다.
- x=4k+3=2(2k+1)+2: 2k+1을 만드는 데에 3(K−1)−2개 이하의 수를 사용합니다. 3(K−1)−2+(2+2)=3K−1입니다.
이렇기에 우리는 1018≤260이하의 수를 179개 이하의 누적합을 써서 만들 수 있고, 원래 문제인 변화값은 180개 이하로 사용해서 만드는 것이 가능합니다.
이 방법을 발전 시켜서 170개 이하만 사용해서 답을 만드는 것도 가능합니다. 몇 가지 a에 대해 시도해 본 결과중 최솟값을 동적 계획법 등으로 관리하면, 더 적은 개수로 답을 만들 수 있습니다.
코드
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
|
#include <bits/stdc++.h>
using namespace std;
pair<int, vector<int>> aug(int a, int b, pair<int, vector<int>> X) {
auto [k, V] = X;
for(int i=0; i<a; i++) V.insert(next(find(V.begin(), V.end(), k)), k+1);
for(int i=0; i<b; i++) V.push_back(k+1);
return {k+1, V};
}
pair<int, vector<int>> gen(long long x) {
if(x == 0) return {1, {0, 0}};
if(x <= 8) return {1, vector<int>(x, 1)};
const vector<pair<int, int>> ab = {{1, 4}, {2, 4}, {1, 2}, {2, 2}};
for(auto [a, b]: ab) if(x%b == a%b) return aug(a, b, gen((x-a)/b));
}
pair<int, vector<int>> delta(pair<int, vector<int>> P) {
auto [k, V] = P;
vector<int> U = {V[0]};
for (int i = 1; i < (int)V.size(); i++) U.push_back(V[i] - V[i-1]);
U.push_back(k+1 - V.back());
return {k+1, U};
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
for (int i = 1; i <= T; i++) {
cout << "Case #" << i << endl;
long long v; cin >> v;
auto [K, A] = delta(gen(v));
cout << A.size() << ' ' << K << endl;
for (int i = 0; i < (int)A.size(); i++)
cout << A[i] << (i + 1 == (int)A.size() ? '\n' : ' ');
cout << flush;
}
}
|
cs |
아름다운 수열
요약
양의 정수로 이루어진 수열 A1,⋯,AN에 대해 이 수열의 아름다움을 Ai−1≤Ai≥Ai+1을 만족하는 i의 개수라고 정의합시다. (A0=AN+1=0; 1≤i≤N). 양의 정수 N개가 주어질 때 이를 임의로 재배열해서 만들 수 있는 수열의 아름다움의 최댓값을 구해야 합니다.
풀이
Ai−1≤Ai≥Ai+1을 만족하는 i를 아름다운 위치라고 합시다.
아름답지 않은 위치를 i1,i2,⋯,im이라고 하고, i0=0,im+1=N+1이라고 합시다. 아름다운 수인 ik+1부터 ik+1−1번째 까지 수가 만족해야 하는 조건은 Aik≤Aik+1=Aik+2=⋯=Aik+1−1≥Aik+1라는 것을 알 수 있습니다.
아름다움을 최대화하기 위해서는 m이 가능한 한 작아야 합니다. 아름답지 않은 위치의 개수가 m개인 해당하는 수열을 만들기 위해서는
- N개의 수 중 m개의 수 V1,V2,⋯,Vm을 고릅니다.
- 나머지 수의 종류가 m+1개 이하입니다.
- 각 수는 V1 이상의 수, max(V1,V2) 이상의 수, max(V2,V3) 이상의 수, ⋯, max(Vm−1,Vm) 이상의 수, Vm 이상의 수여야 합니다.
여기서 다음 관찰을 합시다.
- 수의 범위를 최대한 늘리기 위해서는 V1,V2,⋯,Vm이 정렬되어있어야 합니다.
- V1,max(V1,V2),⋯,max(Vm−1,Vm),Vm중 Vi 이상인 수는 i+1개 이상입니다. 이를 정확히 i+1개로 만드는 방법은 V1≤V2≤⋯≤Vm으로 나누는 것입니다.
- 마찬가지로, 나머지 수 역시 정렬되어 있어야 합니다. 나머지 수는 V1,V2,⋯,Vm−1이상이 1개씩, Vm+1 이상이 2개 있어야 합니다.
그래서 우리는 수를 묶어서 작은 것부터 하나씩 추가할 것입니다. 그 후 조건에 맞지 않을 때 즉, m을 늘려야 할 때마다 m을 하나씩 고를 것입니다. 남은 수의 서로 다른 수의 개수가 가장 작아야 하기 때문에, 제일 적게 남은 수로 Vm을 사용합니다. 수가 작은것부터 추가되기 때문에 이후에 추가되는 수는 모두 Vm이상이고, 기타 수의 조건에 영향을 주지 않습니다. 구현은 우선 순위 큐 등을 사용해서 O(NlogN) 시간에 가능합니다.
코드
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
|
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> V) {
sort(V.begin(), V.end());
if(V.front() == V.back()) return V.size();
priority_queue<int, vector<int>, greater<int>> Q;
int cur = 0;
auto push = [&](int v) {
if (cur < (int)Q.size()) {
int x = Q.top(); Q.pop();
if(x > 1) Q.push(x-1);
++cur;
}
Q.push(v);
};
int p = V[0], c = 1;
for(int i=1; i<(int)V.size(); i++) {
if(p != V[i]) push(c), p = V[i], c = 1;
else ++c;
}
push(c);
return V.size() - cur;
}
int main() {
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
vector<int> V(N);
for(int&v: V) cin >> v;
cout << "Case #" << t << '\n' << solve(V) << endl;
}
}
|
cs |
최적 함수
요약
점 (xi,yi)가 N개 주어집니다. 2차함수 y=f(x)에 대해, (f(xi)−yi)2의 최댓값을 f의 오차라고 합시다. 오차가 최소가 되는 f를 찾아서, 해당 오차를 출력하세요. (좌표 범위: 106, 출력의 절대 오차 및 상대 오차 허용값: 2×10−6)
풀이
오차가 ε 이하인 함수 f(x)와 g(x)에 대해, (f+g2)(x)의 오차도 ε이하입니다. f의 등고선이 볼록이기 때문에 f에 따른 오차는 Unimodal하고 삼분탐색을 사용할 수 있습니다. 주어진 절대오차 및 상대 오차 허용값을 ε, 좌표 범위를 L이라고 하면 2차항과 1차항에 대한 삼분탐색을 차례로 사용해서, O(Nlog2(Lε)) 정도의 시간에 문제를 해결할 수 있습니다(2차항과 1차항이 주어지면, 상수항은 2차항과 1차항만 계산한 값과 y값 차이의 최솟값과 최댓값의 평균으로 설정하면 됩니다.)
이제 (계산시의) 오차에 대해 생각해 봅시다. Machine epislon을 ϵ이라고 합시다. 함수를 f(x)=ax2+bx+c와 같이 잡으면, 해당하는 c의 값이 O(L2)정도까지 발산할 수 있기 때문에, O(L2ϵ)<<ε여야 하고, ϵ<<10−18이어야 하기 때문에, long double
자료형을 사용해야 하며, 이를 사용해도 실수 오차 문제가 발생할 수 있습니다. 그래서 다음과 같은 형태의 함수를 생각해봅시다.
- 가능한 x의 범위가 [l,r]일 때, f(x)=a(x−l)(x−r)+b(x−l)+c꼴입니다.
이제 최적인 f에 대해 각 항이 O(L)로 bound됨을 보입시다.
- 오차의 제곱근은 L 이하입니다
- f(x)=0의 경우 오차의 제곱근은 좌표 범위인 L 이하가 됩니다.
- |c|는 2L이하입니다.
- f(l)=c이므로, |c|=|f(l)|≤L+|yi|≤2L입니다.
- |b(x−l)|은 모든 x에 대해 4L이하입니다.
- f(r)=b(r−l)+c이므로, |b(x−l)|≤|b(r−l)|≤L+|y−c|≤L+|y|+|c|≤4L입니다.
- |a(x−l)(x−r)|는 모든 x에 대해 8L이하입니다.
- |a(x−l)(x−r)|≤|f(x)−b(x−l)+c|≤y+|f(x)|+|b(x−l)|+|c|≤8L 입니다.
그러므로 해당 a,b,c를 사용해서 삼분탐색을 하면, O(Lϵ)<<ε이면 충분하고, ϵ<<10−12 정도이므로 double
자료형만 사용해도 문제를 해결할 수 있습니다.
코드
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
|
#include <bits/stdc++.h>
using namespace std;
double solve(vector<pair<int, int>> V) {
const double LIM = 1e7;
const int iter = 150;
const double INF = std::numeric_limits<double>::infinity();
sort(V.begin(), V.end());
int L = V.front().first, R = V.back().first;
auto calcC = [&](double a, double b) {
double minv = +INF, maxv = -INF;
for (auto &[x, y] : V) {
double c = y - (a * (x - L) * (x - R)) + b * (x - L);
minv = min(minv, c);
maxv = max(maxv, c);
}
double E = (maxv - minv) / 2;
return E * E;
};
auto calcB = [&](double a) {
double lo = -LIM, hi = +LIM;
for (int i = 0; i < iter; i++) {
double b1 = (lo + lo + hi) / 3, b2 = (lo + hi + hi) / 3;
double v1 = calcC(a, b1), v2 = calcC(a, b2);
if (v1 < v2) hi = b2;
else lo = b1;
}
return calcC(a, (lo + hi) / 2);
};
auto calcA = [&]() {
double lo = -LIM, hi = +LIM;
for (int i = 0; i < iter; i++) {
double a1 = (lo + lo + hi) / 3, a2 = (lo + hi + hi) / 3;
double v1 = calcB(a1), v2 = calcB(a2);
if (v1 < v2) hi = a2;
else lo = a1;
}
return calcB((lo + hi) / 2);
};
return calcA();
}
int main() {
int T;
cin >> T;
for (int t = 1; t <= T; t++) {
int N; cin >> N;
vector<pair<int, int>> V(N);
for (auto &[x, y] : V) cin >> x >> y;
cout << "Case #" << t << '\n';
cout << fixed << setprecision(20) << solve(V) << endl;
}
}
|
cs |
'프로그래밍 > 알고리즘' 카테고리의 다른 글
SCPC 2022 2차 풀이 (0) | 2022.08.06 |
---|---|
SCPC 2021 2차 풀이 (0) | 2021.08.07 |
SCPC 2021 1차 풀이 (0) | 2021.07.17 |
테스트 데이터 만들기: Anti-Hash test / Anti-Javasort test (0) | 2018.10.11 |
Simple Cubic General Maximum Matching Algorithm (0) | 2018.03.22 |