1. 다이어트
길이 \(N\)인 배열 \(A, B\)가 있다.
각 배열에서 원소를 \(K\)개씩 골라 (A의 원소, B의 원소)로 이루어진 순서쌍을 \(K\)개 만든다.
각 순서쌍의 합의 최대값을 최소화한 값을 알아내야 한다.
\(A, B\)를 각각 정렬한 다음, \(A\)에서 가장 작은 \(K\)개의 값과 \(B\)에서 가장 작은 \(K\)개의 값만을 사용하자.
\(A_i\)와 \(B_{k+1-i}\)를 각각 매칭 시켜주면 최적임을 알 수 있다.
|
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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
int n, k;
ll a[200001], b[200001];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T; cin >> T;
for (int t = 1; t <= T; t++)
{
cin >> n >> k;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
sort(a, a + n);
sort(b, b + n);
ll ans = 0;
for (int i = 0; i < k; i++)
{
ll res = a[i] + b[k - 1 - i];
ans = max(ans, res);
}
cout << "Case #" << t << '\n';
cout << ans << '\n';
}
}
|
2. 카드 게임
\(N\)개의 카드로 이루어진 덱 \(X, Y\)가 있다. 각 카드의 값은 \(K\)이하이다.
두 플레이어가 게임을 한다.
각 플레이어는 두 덱중 하나를 골라, 위에서부터 1개 이상의 카드를 가져갈 수 있다.
단, 가져가는 카드에 적인 수의 합이 \(K\)이하여야 한다.
마지막 카드를 가져가는 사람이 진다.
게임의 상태를 두 덱에 남아있는 카드의 수 \((i, j)\)로 나타낼 수 있다. 총 \((N+1)^2\)개의 상태가 있다.
이 중 무조건 이기는 게임의 상태와 무조건 지는 게임의 상태의 개수를 알아내야 한다.
문제에 쓰여 있듯이, 현재 상태에서 어떻게 플레이하더도 다음 상태가 이기는 상태라면 현재 상태는 지는 상태이고, 다음 상태가 지는 상태가 하나라도 있다면 이기는 상태이다.
따라서 DP를 이용해 문제를 풀 수 있게 된다.
총 \(O(N^2)\)개의 상태가 있고, 각 상태를 계산하는데 최대 \(O(N)\)개의 부분 문제를 계산해야 하므로 naive하게 푼다면 총 시간복잡도는 \(O(N^3)\)이다.
하지만 \(N \le 3000\)이라 이대로는 시간초과가 나므로, 추가로 최적화가 필요하다.
현재 상태가 이기는 상태라면 1, 지는 상태라면 0이라고 생각해보자.
그러면 부분 문제에 해당하는 구간을 봤을 때, 구간 합과 구간의 길이가 같으면 이기는 상태가, 그렇지 않으면 지는 상태가 된다는 사실을 알 수 있다.
이를 계산하는데 세그먼트 트리등으로 \(O(\log N)\)의 시간이 걸리도록 하면 총 시간복잡도가 \(O(N^2 \log N)\)이 되는데, 실제로 제출해보면 의문의 시간초과를 받게 된다.
따라서 이를 \(O(1)\)에 계산해야 한다.
본인은 투포인터를 이용했고, 총 시간복잡도 \(O(N^2)\)에 문제를 해결할 수 있었다.
|
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
92
93
94
95
96
97
98
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int N = 3010;
int n, k;
int x[N], y[N];
int ans[N][N];
int xl[N], yl[N];
int xsum[N], ysum[N];
int xcnt[N], ycnt[N];
int main()
{
setbuf(stdout, NULL);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
scanf("%d%d", &n, &k);
for (int i = 0; i < n; i++) cin >> x[i];
for (int i = 0; i < n; i++) cin >> y[i];
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++) ans[i][j] = 0;
xl[i] = yl[i] = xsum[i] = ysum[i] = xcnt[i] = ycnt[i] = 0;
}
int win = 0, lose = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 && j == 0)
{
ans[i][j] = 1;
win++;
continue;
}
bool rx = 0, ry = 0;
if (j)
{
xsum[i] += x[j - 1];
xcnt[i] += ans[i][j - 1];
while (xsum[i] > k)
{
xsum[i] -= x[xl[i]];
xcnt[i] -= ans[i][xl[i]];
xl[i]++;
}
int cnt = j - xl[i];
if (xcnt[i] != cnt) rx = 1;
}
if (i)
{
ysum[j] += y[i - 1];
ycnt[j] += ans[i - 1][j];
while (ysum[j] > k)
{
ysum[j] -= y[yl[j]];
ycnt[j] -= ans[yl[j]][j];
yl[j]++;
}
int cnt = i - yl[j];
if (ycnt[j] != cnt) ry = 1;
}
if (rx || ry)
{
ans[i][j] = 1;
win++;
}
else
{
ans[i][j] = 0;
lose++;
}
}
}
printf("Case #%d\n%d %d\n", t, win, lose);
}
}
|
3. 사다리 게임
\(N\)개의 세로선과 \(K\)개의 가로선으로 이루어진 사다리가 있다.
\(M\)개의 쿼리 \((i,j)\)가 주어지는데, 각 쿼리마다 \(i\)번 세로선에서 시작해 \(j\)번 세로선에서 끝나기 위해, 없애야 하는 가로선의 최소 개수를 알아내야 한다.
만약 어떻게 해도 \(i\)번에서 \(j\)번으로 이동할 수 없다면, 답은 -1이다.
모든 쿼리의 답의 합을 알아내야 한다.
\(x\)번 세로선을 골라, 여기에서 시작해 \(N\)개의 모든 세로선에서 끝나기 위해 없애야 하는 가로선의 최소 개수를 계산하자.
이를 \(dp\)배열에 저장한다고 가정한다.
초기 값은 다음과 같다: \(dp_x = 0\), 그 외는 INF
\(K\)개의 가로선을 차례대로 살펴보자. 가로선이 \(a, b\)번 세로선을 연결하고 있다면,
\(dp_a = \min(dp_a+1, dp_b)\),
\(dp_b = \min(dp_b+1, dp_a)\)
임을 알 수 있다.
그러면 각 세로선에서 시작했을 때의 모든 값을 \(O(N+K)\)에 계산할 수 있으므로,
총 시간복잡도 \(O(N^2+NK+M)\)에 문제를 해결할 수 있다.
|
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;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int INF = 987654321;
int n, k, m;
int ans[2001][2001];
pii line[2001];
int main()
{
setbuf(stdout, NULL);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
scanf("%d%d%d", &n, &k, &m);
for (int i = 0; i < k; i++)
{
int l, r; scanf("%d%d", &l, &r);
line[i] = { l,r };
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++) ans[i][j] = INF;
ans[i][i] = 0;
for (int j = 0; j < k; j++)
{
int l = line[j].first, r = line[j].second;
int tl = ans[i][l], tr = ans[i][r];
ans[i][l] = min(tr, tl + 1);
ans[i][r] = min(tl, tr + 1);
}
for (int j = 1; j <= n; j++) if (ans[i][j] == INF) ans[i][j] = -1;
}
int sum = 0;
for (int i = 0; i < m; i++)
{
int l, r; scanf("%d%d", &l, &r);
sum += ans[l][r];
}
printf("Case #%d\n%d\n", tc, sum);
}
}
|
4. 범위 안의 숫자
\(n\)길이의 숫자로 이루어진 문자열 \(t\)가 주어진다.
\(t\)의 각 인덱스 중 하나를 골라, 이 인덱스의 숫자를 1로 바꿀 수 있다. (하지 않을 수도 있다)
그렇게 만들어진 문자열에서 길이 \(k\)의 부분 문자열을 모두 하나의 수로 만든다.
그러면 길이 \(m\)인 구간 \([a, a+m]\)에 대해, 이 구간에 속해 있는 수의 개수를 계산할 수 있다.
\(a\)를 적당히 조절해, 이 개수를 최대값을 찾아야 한다.
만들 수 있는 수를 전부 만들자. 총 \((k+1)(n-k+1)\)개의 수가 나올 것이다.
각각의 수와, 이 수를 만들기 위해 1로 바꿔야하는 인덱스 번호를 저장하고, 수의 크기순으로 정렬하자.
그러면 투 포인터를 이용해 \(m\)범위안에 있는 수들을 모두 찾을 수 있다.
이 수들에서,
"어떤 인덱스도 1로 바꾸지 않았을 때 수의 개수",
"1번 인덱스를 1로 바꿨을 때 수의 개수",
"2번 인덱스를 1로 바꿨을 때 수의 개수",
...
"n번 인덱스를 1로 바꿨을 때 수의 개수"
를 각각 세어서 그 중 최대값을 계산해 나가면 답을 찾을 수 있을 것이다.
1로 바꾼 인덱스를 인덱스로 하고 (바꾸지 않았을 때는 n+1),
그 안에 있는 수의 개수를 값으로 하는 최대값 세그먼트 트리를 만들면 된다.
다만 몇몇 수들의 경우 특정한 \(x\)번 인덱스를 바꿔야 나오는 값이 아니라,
(\(l\)번 미만의 인덱스 or \(r\)번 초과의 인덱스) 를 바꿔야 나오는 값이다. (\(t\)에서의 원본일 때)
따라서 구간 갱신을 필요로 하고, Lazy Propagation이 가능한 최대값 세그먼트 트리를 만들어야 한다.
|
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int N = 50010;
const ll TEN[] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };
ll n, k, m;
char t[N];
vector <pair<ll, pii> > v;
int segTree[N * 4];
int lazy[N * 4];
void setLazy(int ptr, int l, int r)
{
int val = lazy[ptr]; lazy[ptr] = 0;
segTree[ptr] += val;
if (l != r)
{
lazy[ptr * 2] += val;
lazy[ptr * 2 + 1] += val;
}
}
void update(int ptr, int l, int r, int i, int j, int val)
{
if (lazy[ptr]) setLazy(ptr, l, r);
if (j < l || r < i) return;
if (i <= l && r <= j)
{
segTree[ptr] += val;
if (l != r)
{
lazy[ptr * 2] += val;
lazy[ptr * 2 + 1] += val;
}
return;
}
update(ptr * 2, l, (l + r) / 2, i, j, val);
update(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j, val);
segTree[ptr] = max(segTree[ptr * 2], segTree[ptr * 2 + 1]);
}
int getVal(int ptr, int l, int r, int i, int j)
{
if (lazy[ptr]) setLazy(ptr, l, r);
if (j < l || r < i) return 0;
if (i <= l && r <= j) return segTree[ptr];
return max(getVal(ptr * 2, l, (l + r) / 2, i, j)
, getVal(ptr * 2 + 1, (l + r) / 2 + 1, r, i, j));
}
int main()
{
setbuf(stdout, NULL);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
scanf("%lld%lld%lld", &n, &k, &m);
scanf("%s", t);
v.clear();
memset(segTree, 0, sizeof segTree);
memset(lazy, 0, sizeof lazy);
ll cNum = 0;
for (int i = 0; i < n; i++)
{
cNum *= 10;
cNum += t[i] - '0';
if (i >= k) cNum -= TEN[k] * (t[i - k] - '0');
if (i >= k - 1)
{
v.push_back({ cNum, {i - (k - 1), i} });
for (int j = 0; j < k; j++)
{
ll dig = t[i - (k - 1) + j] - '0';
cNum -= dig * TEN[k - 1 - j];
cNum += TEN[k - 1 - j];
v.push_back({ cNum, {-1, i - (k - 1) + j} });
cNum -= TEN[k - 1 - j];
cNum += dig * TEN[k - 1 - j];
}
}
}
sort(v.begin(), v.end());
int ans = 0;
int l = -1, r = 0;
while (l < (int)v.size())
{
if (l >= 0)
{
ll lval = v[l].first;
while (l < v.size() && v[l].first == lval)
{
int sl = v[l].second.first;
int sr = v[l].second.second;
if (sl == -1)
{
update(1, 0, n, sr, sr, -1);
}
else
{
update(1, 0, n, 0, sl - 1, -1);
update(1, 0, n, sr + 1, n, -1);
}
l++;
}
}
else l++;
if (l >= v.size()) break;
ll lval = v[l].first;
while (r < v.size() && v[r].first <= lval + m)
{
int sl = v[r].second.first;
int sr = v[r].second.second;
if (sl == -1)
{
update(1, 0, n, sr, sr, 1);
}
else
{
update(1, 0, n, 0, sl - 1, 1);
update(1, 0, n, sr + 1, n, 1);
}
r++;
}
int res = segTree[1];
ans = max(ans, res);
}
printf("Case #%d\n%d\n", tc, ans);
}
}
|
5. 우범 지역
좌표평면 위에 \(N\)개의 위치가 주어지고, 이 위치가 존재할 확률 \(p_i\)가 주어진다.
좌표평면 위에 현재 존재하는 모든 점에 대해 컨벡스 헐을 만든다.
점 \(q\)가 이 컨벡스 헐 안에 존재할 확률을 구해야 한다.
반대로, 점 \(q\)가 주어지는 점으로 이루어진 컨벡스 헐 안에 존재하지 않을 확률을 구해보자.
\(i\)번 점이 무조건 존재한다고 생각해보자.
\(q\)를 기준으로 했을 때, \(i\)번 점의 시계방향에 있는 점들이 모두 존재하지 않는다면 \(q\)는 주어지는 점으로 이루어진 컨벡스 헐 안에 무조건 존재하지 않게 된다.
모든 점에 대해서 각 점이 무조건 존재하면서 이 점의 시계방향에 있는 점들이 모두 존재하지 않는 경우와, 모든 점이 존재하지 않는 경우를 합하면 \(q\)가 컨벡스 헐 안에 존재하지 않는 모든 경우가 된다는 사실을 관찰을 통해 알 수 있다.
따라서 점을 각도순으로 정렬하고, 확률의 부분곱을 구해놓으면 각 \(N\)개 점이 기준 일 때의 확률을 \(O(1)\)에 계산할 수 있게 되므로, 총 시간 복잡도 \(O(N \log N)\)에 답을 구할 수 있음을 알 수 있다.
단 \(N\)이 커지면 확률의 부분곱의 오차가 매우 심해지므로, 대신 log의 부분합을 구함으로써 오차를 줄일 수 있다.
이 때, 어떤 점이 존재할 확률이 1인 경우는 존재하지 않을 확률이 0인데, 0에 log을 취하면 에러가 난다.
이는 존재하지 않을 확률에 매우 작은 값 (\(10^{-12}\))를 더해줌으로써 해결했다.
|
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
92
93
94
95
96
97
98
99
100
101
102
103
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
const int N = 100010;
struct VECTOR
{
ll x, y;
};
ll cross(VECTOR v1, VECTOR v2)
{
return v1.x * v2.y - v1.y * v2.x;
}
struct Point
{
pll cd;
long double p;
};
int n;
Point point[N * 2];
long double lgp[N * 2];
ll qx, qy;
bool comp(Point& a, Point& b)
{
pll p1 = a.cd;
pll p2 = b.cd;
ll dx1 = p1.first - qx;
ll dy1 = p1.second - qy;
ll dx2 = p2.first - qx;
ll dy2 = p2.second - qy;
if (pll(dx1, dy1) > pll(0, 0) ^ pll(dx2, dy2) > pll(0, 0))
return pll(dx1, dy1) > pll(dx2, dy2);
VECTOR v1 = { dx1, dy1 };
VECTOR v2 = { dx2 - dx1, dy2 - dy1 };
return cross(v1, v2) > 0ll;
}
int main()
{
setbuf(stdout, NULL);
int T; scanf("%d", &T);
for (int tc = 1; tc <= T; tc++)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld", &point[i].cd.first);
for (int i = 1; i <= n; i++) scanf("%lld", &point[i].cd.second);
for (int i = 1; i <= n; i++) scanf("%Lf", &point[i].p);
scanf("%lld%lld", &qx, &qy);
sort(point + 1, point + n + 1, comp);
for (int i = 1; i <= n; i++)
{
point[n + i] = point[i];
}
for (int i = 1; i <= n * 2; i++)
{
lgp[i] = lgp[i - 1] + log(1.0 - point[i].p + 1e-12);
}
long double ans = exp(lgp[n]);
int l = 1, r = 1;
while (l <= n)
{
VECTOR v1 = { qx - point[l].cd.first, qy - point[l].cd.second };
r = max(r, l);
while (r + 1 < l + n)
{
VECTOR v2 = { point[r + 1].cd.first - qx, point[r + 1].cd.second - qy };
if (cross(v1, v2) < 0ll) r++;
else break;
}
long double res = log(point[l].p) + (lgp[r] - lgp[l]);
res = exp(res);
ans += res;
l++;
}
ans = 1.0 - ans;
printf("Case #%d\n%.12Lf\n", tc, ans);
}
}
|
'문제 풀이 > 그외' 카테고리의 다른 글
| Google Kick Start - Round F 2020 (0) | 2020.09.27 |
|---|---|
| Google Kick Start - Round E 2020 (2) | 2020.08.23 |
| Google Kick Start - Round D 2020 (0) | 2020.07.13 |
| Google Code Jam - Round 1A 2020 (2) | 2020.04.11 |
| Google Code Jam - Qualification Round 2020 (0) | 2020.04.11 |
