# SCPC 2020 Round 1 문제 풀이 및 후기

> SCPC 삼성 프로그래밍 경진대회

![Uploading file..._agtmbqnbc]()

결과

- 다이어트: 100/100점
- 카드 게임: 150/150점
- 사다리 게임: 150/150점
- 범위 안의 숫자: 200/200점
- 우범 지역: 0/200점

## 먼저 쓰는 느낀 점

무난하게 Round 2로 갈것같다. All solve하고 싶었지만 마지막 문제 풀이를 전혀 생각 못했다. 5번은 기하 문제였는데 기하 연습좀 해야겠다. 만점이 45명 정도인데 scpc수상하려면 5번 정도 수준의 문제를 대회시간에 풀 실력을 키워야겠다. ~~나름 할만큼 했는데 주변에 올솔이 너무 많다 ㅠ~~

디스크립션이 살짝 이상한 부분이 있었다.

---

[cgiosy](https://blog.naver.com/rla_xodbs/222081264751), [rkm0959](https://rkm0959.tistory.com/160) 님의 후기를 참고하여 작성했습니다.

## 실력 맞추기

길이 $N$인 배열 $A$와 $B$가 있다. $A$와 $B$의 순서는 마음대로 바꿀 수 있다. 이 때 $A$의 수를 단 하나 원하는 아무 수로 바꿀 수 있다. $\sum_{i=1}^{N} |A[i]-B[i]|의 최솟값을 구하시오.

- 제한조건
$$
1 ≤ N ≤ 200,000,
1 ≤ K ≤ N, 1 ≤ A[i] ≤ 10^9
$$

### 풀이

- 그리디
- 정렬

1. $A$와 $B$에서 가장 작은 $K$개의 수만 사용해야 한다.
2. $A$와 $B$를 오름차순 정렬했을 때 $A[1]$은 $B[K]$와 매칭하면 답을 구할 수 있다.
- 증명: 만약 그렇지 않다면 $A[1]$이 $B[i] (i \ne K)$ 와 매칭되고 $A[j] (j \ne 1)$ 가 $B[K]$와 매칭되는데 $A[j] + B[K] ≤ max(A[1] + B[K], A[i] + B[j])$ 이기 때문이다.
3. $A[2..K]$ 와 $B[1..K-1]$ 에 대해서도 2번을 동일하게 적용하면 된다.

시간 복잡도는 $K$개를 정렬하는데 드는 속도인 $O(NlogK)$이다.

### 여담

가장 쉬운 문제. 보자마자 풀었다. 부분 점수는 모든 경우를 다 해보면 얻을 수 있었던걸로 기억한다.

### 코드

> 실제 제출한 코드와는 다르다

#include <bits/stdc++.h>
using namespace std;
const int MAX = 20000;

int A[MAX], B[MAX];
void solve() {
	int N, K; scanf("%d %d", &N, &K);
	for (int i = 0; i < N; i++) 
		scanf("%d", A+i);
	for (int i = 0; i < N; i++)
		scanf("%d", B+i]);
	partial_sort(A, A+K, A+N);
	partial_sort(B, B+K, B+N);
	int ans = 0;
	for (int i = 0; i < K; i++)
		ans = max(ans, A[i]+B[K-i-1]);
	printf("%d\n", ans);
}

int main() {
	// setbuf(stdout, NULL);
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		printf("Case #%d\n",i);
		solve();
	}
}

## 카드 게임

두 사람이 길이 $N$의 배열 $X$와 $Y$로 게임을 한다. 둘이 번갈아 가며 턴을 진행하며, 각 턴에선 원하는 배열 하나에서 맨 뒤의 수들을 여러 개 지울 수 있다. $X$와 $Y$의 수는 모두 $K$ 이하고 지우는 수들의 합이 $K$ 이하여야 한다. 둘은 최선의 전략으로 게임을 하며, 자신의 턴에서 남아있는 수가 없는 사람이 이긴다.

X와 Y에 남아있는 수의 개수를 $i$, $j$개라고 할 때, 해당 상태에서 선공이 이길지 후공이 이길지는 정해져 있다. 모든 가능한 상태 $(N+1)^2$ 개 중 $(i, j)$에서 선공이 이기는 상태의 수와 후공이 이기는 상태의 수를 구하시오. 단, 상태 $(0, 0)$은 선공이 이긴 상태로 본다.

- 제한 조건
$$
1 ≤ N, K ≤ 3000\\1 ≤ A[i] ≤ K
$$

### 풀이

- DP

#### 부분 점수

1. $(i, j)$ 상태 값이 $WIN$인지 $LOSE$인지 알려면 상대방에게 $(i', j')$ 로 바뀌어 넘겨주었을 때의 값들을 이용해 알 수 있다.
2. 만약 $(i', j') = LOSE$로 변환할 수 있다면 $(i, j) = WIN$, 없다면 $(i, j) = LOSE$ 이다.

이때 채워야할 값은 $(N+1)^2$ 이고 각 칸 마다 최대 $2N$개의 값을 확인해야하기 때문에
시간 복잡도는 $O(N^3)$이다.

#### 만점

1. 한번에 하나의 배열만 건드릴 수 있으므로 $(i', j')$ 는 $(i, j')$ 이거나, $(i', j)$이다. 이때 $i'$의 최솟값을 $a$, $j'$의 최솟값을 $b$라고 할수 있다.
2. 그렇다면 $(i, [b..j-1])$, $([a..i-1], j)$에 $LOSE$가 있는지 빠르게 판별하면 $(i, j)$의 값을 알 수 있다.
3. 연결된 구간이므로 prefix sum을 통해 $O(1)$ 만에 구할 수 있다.

시간 복잡도는 $O(N^2)$이다.

### 여담

친구들을 보니 Grundy 게임으로 많이 접근을 해서 시간초과가 난것 같다.

### 코드

> 실제 제출한 코드와는 다르다

#include <bits/stdc++.h>
using namespace std;
int X[3001], Y[3001], N, K;
int xl[3001], yl[3001];
int xpsum[3001][3001], ypsum[3001][3001];

int getx(int i, int j) {
	if (i < 0) return 0;
	return xpsum[i][j];
}
int gety(int i, int j) {
	if (j < 0) return 0;
	return ypsum[i][j];
}

int go(int i, int j) {
	if (i == 0 && j == 0) return 1;
	if (gety(i, j-1) - gety(i, yl[j]-1) != j-yl[j]) 
		return 1;
	if (getx(i-1, j) - getx(xl[i]-1, j) != i-xl[i]) 
		return 1;
	return 0;
}

void solve() {
	int A = 0, B = 0;
	scanf("%d %d", &N, &K);
	int lb = 1, sum = 0;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &X[i]);
		sum += X[i];
		while (sum > K) {
			sum -= X[lb];
			lb++;
		}
		xl[i] = lb - 1;
	}
	lb = 1, sum = 0;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &Y[i]);
		sum += Y[i];
		while (sum > K) {
			sum -= Y[lb];
			lb++;
		}
		yl[i] = lb - 1;
	}

	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= N; j++) {
			int ret = go(i, j);
			xpsum[i][j] = ypsum[i][j] = ret;
			if (ret == 1) A++;
			else B++;
			if (i) xpsum[i][j] += xpsum[i-1][j];
			if (j) ypsum[i][j] += ypsum[i][j-1];
		}
	}
	printf("%d %d\n", A, B);
}

int main() {
	// setbuf(stdout, NULL);
	int T; scanf("%d", & T);
	for (int i = 1; i <= T; i++) {
		printf("Case #%d\n",i);
		solve();
	}
}

## 사다리 게임

$N$개의 세로선이 있고 $M$개의 가로선이 있다. 가로선은 $(a, b)$ 순서쌍으로 이루어지며, 세로선 $a$와 세로선 $b$를 양방향으로 연결한다. $i$번째 세로선에서 모든 가로선을 타며 내려가면 $j$번째 세로선에 도착하게 되는데, 가로선을 최소한으로 지워 원하는 세로선으로 도착하도록 만드려고 한다.

즉, 사다리가 주어지면 $Q$개의 쿼리에 대해 $i$번째 세로선에서 시작해 $j$번째 세로선에 도착하도록 만들 때 최소한으로 지워야 하는 가로선의 개수의 합을 출력해야 한다. 만약 $i$에서 $j$로 갈 수 없다면 $-1$을 더한다.

- 제한 조건
$$
2 ≤ N ≤ 1500\\1 ≤ M ≤ 2000\\1 ≤ Q ≤ 10^5\\1 ≤ i < j ≤ N
$$

### 풀이

- DP
- 최단 경로
- 0-1 BFS

여러가지 풀이가 있는 것으로 알고 있다. 나는 DP로 풀었다.

1. $i$ 에서 $j$로 가기 위한 최소 제거 횟수를 $dp[i][j]$라 하자. dp 테이블의 초기값은 $dp[i][i] = 0$이고 $dp[i][j]=\infty (j \ne i)$
2. $(u, v)$ 간선을 만나면 값을 $1$ 올리고 그대로 있거나, 값을 그대로 하고 바꾸는 선택이 가능하다. 최솟값을 계속 저장한다. 두 값을 동시 업데이트하는거에 주의를 해야한다.
$$
dp[i][u] = min(dp[i][u]+1, dp[i][v])\\dp[i][v] = min(dp[i][v]+1, dp[i][u])
$$

시간 복잡도는 $O(N^2 + NM + Q)$ 이다.

### 여담

$-1$을 더하라는건 정말 :thinking_face: 이다.

## 코드

> 실제 제출한 코드와는 다르다

구현에서는 업데이트가 필요한 것만 관리하기 위해서 큐를 사용했는데 그냥 $2N$개를 봐도 무방하다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 987654321;

int N, K;
queue<int> q[1500];
int ans[1500][1500];
void solve() {
	int m;
	scanf("%d %d %d", &N, &K, &m);
	memset(ans, -1, sizeof(ans));
	for (int i = 0; i < N; i++) {
		q[i] = queue<int>();
		q[i].push(i);
		ans[i][i] = 0;
	}
	while (K--) {
		int a = scanf("%d", &a);
		int b = scanf("%d", &b);
		--a; --b;
		vector<int> A(N, INF), B(N, INF);
		while (!q[a].empty()) {
			int now = q[a].front(); q[a].pop();
			A[now] = ans[now][a] + 1;
			B[now] = ans[now][a];
		}
		while (!q[b].empty()) {
			int now = q[b].front(); q[b].pop();
			B[now] = min(B[now], ans[now][b] + 1);
			A[now] = min(A[now], ans[now][b]);
		}
		for (int i = 0; i < N; i++) {
			if (A[i] != INF) {
				q[a].push(i);
				ans[i][a] = A[i];
			}
			if (B[i] != INF) {
				q[b].push(i);
				ans[i][b] = B[i];
			}
		}
	}

	int ret = 0;
	while (m--) {
		int x, y; scanf("%d %d",&x, &y);
		ret += ans[x-1][y-1];
	}
	printf("%d\n", ret);
}

int main() {
	// setbuf(stdout, NULL);
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		printf("Case #%d\n",i);
		solve();
	}
}

## 범위 안의 숫자

숫자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$에서 임의의 숫자를 골라 1로 바꾸고, 연속한 $K$개의 숫자로 이루어진 수를 모두 나열했을 때 적절한 수 $a$를 골라 $[a, a + M]$에 있는 수의 개수를 최대화하여라.

- 제한 조건
$$
1 ≤ N ≤ 50000\\1 ≤ K ≤ min(9, N)
$$

### 풀이

- 세그먼트 트리
- 좌표 압축

1. $K$값이 작은 것에 주목한다. 총 나올 수 있는 길이 $K$의 수는 $N(K+1)$개 보다 작다. 이를 모두 구해 $V$에 저장한다.
2. $V$를 정렬하고 좌표 압축을 한다.
3. $V$에 있는 각 원소 $a$에 대해서 $[a, a+M]$에 포함되는 $V$의 최대 인덱스 번호를 저장한다.
4. range update를 지원하는 maximum segment tree를 만든 다음, 아무것도 바꾸지 않은 $S$에 대해서 $K$개의 연속된 숫자로 이루어진 수를 모두 업데이트를 한다. 이 때 업데이트를 할때 그 수의 인덱스 번호부터 3에서 구한 최대 인덱스 번호까지 구간 업데이트를 한다. 이를 통해 각 node의 말단에는 그 수를 마지막으로 하는 구간에 해당하는 개수를 알 수 있다.
5. $S$의 $i$번째 숫자를 $1$로 바꾸었을때 바귀는 값을 빼고 넣고하는 과정을 반복하며 최대값을 갱신한다.

시간 복잡도는 $O(NKlog(NK))$이다.

제한시간이 10초지만 상수가 크고 테스트케이스가 있기 때문에 최적화를 조금 해야 할 수 있다.

### 여담

구현을 정말 애먹었다.무려 7번 틀렸다. 인덱스 실수 하고 시간초과 나고, 대회 때는 나만 그런줄 알았는데 끝나고 보니 다들 그래서 조금 안심이다.

세그먼트트리를 안쓰고도 풀 수 있다는데 나중에 다시 봐야겠다.

### 코드

공개하기 정말 부끄러운 코드인데(`real_solve` 등) 다시 짜기는 또 귀찮다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 50'000;

ll ten[10]={1};
char s[MAX+5];
int n, k, m, sz;
int ub[MAX*10+5];
int t[MAX*41], lazy[MAX*41];
vector<int> base, a[MAX+5], b[MAX+5];
vector<ll> nums;
unordered_map<int,int> hsh;

void push(int v) {
	t[v*2] += lazy[v];
	lazy[v*2] += lazy[v];
	t[v*2+1] += lazy[v];
	lazy[v*2+1] += lazy[v];
	lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int addend) {
    if (l > r) 
        return;
    if (l == tl && tr == r) {
        t[v] += addend;
        lazy[v] += addend;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), addend);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

void update(int l, int r, int addend) {
	update(1, 0, sz-1, l, r, addend);
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return 0;
    if (l <= tl && tr <= r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)), 
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

int query() {
	return query(1, 0, sz-1, 0, sz-1);
}

void init() {
	base.clear();
	nums.clear();
	hsh = unordered_map<int,int>();
	memset(t, 0, sizeof(t));
	memset(lazy, 0, sizeof(lazy));

}

void get_number() {
	ll val = 0;
	for (int i = 0; i < k - 1; i++) {
		val = val * 10 + s[i] - '0';
	}
	for (int i = k - 1; i < n; i++) {
		val = val * 10 + s[i] - '0';
		val %= ten[k];
		nums.push_back(val);
		base.push_back(val);
		int x = val;
		for (int j = 0; j < k; j++) {
			int digit = (val % ten[j+1]) / ten[j];
			if (digit == 1) continue;
			b[i-j].push_back(val); 
			val -= (digit - 1) * ten[j];
			nums.push_back(val);
			a[i-j].push_back(val);
			val += (digit - 1) * ten[j];
		}
	}

	sort(begin(nums), end(nums));
	nums.erase(unique(begin(nums), end(nums)), end(nums));

	sz = nums.size();
	for (int i = 0; i < sz; i++) {
		hsh[nums[i]] = i;
	}
	int idx = 0;
	for (int i = 0; i < sz; i++) {
		while (nums[i] - nums[idx] > m) {
			ub[idx] = i - 1;
			idx++;
		}
	}
	for (; idx < sz; idx++) {
		ub[idx] = sz - 1;
	}
}

void real_solve() {
	for (int i : base) {
		int idx = hsh[i];
		update(idx, ub[idx], 1);
	}
	int ans = query();
	for (int i = 0; i < n; i++) {
		for (int j : a[i]) {
			int idx = hsh[j];
			update(idx, ub[idx], 1);
		}
		for (int j : b[i]) {
			int idx = hsh[j];
			update(idx, ub[idx], -1);
		}
		ans = max(ans, query());
		for (int j : a[i]) {
			int idx = hsh[j];
			update(idx, ub[idx], -1);
		}
		for (int j : b[i]) {
			int idx = hsh[j];
			update(idx, ub[idx], 1);
		}
		a[i].clear();
		b[i].clear();
	}
	printf("%d\n", ans);
}

void solve() {
	scanf("%d %d %d %s", &n, &k, &m, s);
	init();
	get_number();
	real_solve();
}

int main() {
	// setbuf(stdout, NULL);
	for (int i = 1; i <= 10; i++) 
		ten[i] = 10 * ten[i-1];
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		printf("Case #%d\n",i);
		solve();
	}
}

## 우범 지역

N개의 점 $(x_i, y_i)$들이 주어지는데, 각 점에는 선택될 확률 $p_i$이 있다. 선택된 점들의 컨벡스 헐에 점 $q$가 포함될 확률을 구하시오. 단, $q$와 임의의 서로 다른 두 점을 골랐을 때 직선 상에 놓여있지 않는다.

- 제한 조건
$$
1 ≤ N ≤ 100000\\1 ≤ x_i, y_i ≤ 10^9\\0 < p_i ≤ 1
$$

### 풀이

> 풀이를 알려주신 @Miren0923님께 감사드립니다.

- 기하
- Sliding window

0. 컨벡스 헐에 점이 있는 경우를 생각하는 것보다 컨벡스헐에 점이 없는 경우를 생각하는 것이 더 쉽다.
1. "점 $q$가 컨벡스헐에 들어가지 않는다."와 "점 $q$와 나머지 선택된 점을 가르는 직선이 있다"가 동치
2. 점 $q$를 중심으로 나머지 점을 (각도를 기준으로) 원주에 올리면, 점이 하나도 없는 180도 길이의 구간이 있는 확률이 답
3. 선택된 점이 없는 경우의 확률 + 선택된 점이 있는 경우의 확률을 더하면 된다.
- 점이 없는 경우: 모든 점마다 선택되지 않을 경우 확률 곱
- 점이 있는 경우: 모든 점마다 (자신이 선택될 확률) * (180도 이후에 점이 선택되지 않을 확률의 곱)
4. (180도 이후에 점이 선택되지 않을 확률의 곱)을 구하려면 sliding window를 통해서 구할 수 있다.
- 여기서 실수 오차가 나는걸 방지 하기 위해서(나눗셈 없이) sparse table을 사용하면 된다.
- 그밖에도 세그먼트트리를 사용하거나 로그값을 이용해서 실수오차를 방지할 수 있다.

확률 자체는 빠르게 구하면 $O(N)$만에 구할 수도 있지만 결국 정렬을 해야해서 전체 시간 복잡도는 $O(NlogN)$이다.

### 여담

못 풀었다. 전혀 접근 자체를 하지 못했고 확률 문제다 보니 [몬테 카를로](https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%EB%B0%A9%EB%B2%95)로 비벼라도 볼까 했으나 여의치 않았다. 0번을 생각하면 2번까지 생각하고, 점이 있는 경우 처리하면서 재밌게 고민햇을텐데 0번을 생각하지 못했다.

브루트 포스로 $O(NlogN * 2^N)$ 에 짜는것 밖에 생각이 안났다. 저 2^N을 줄이기 위해서 생각을 많이 했다. 들로네 삼각분할을 쓰고 전처리? meet-in-the-middle? 스위핑? 전혀 아니었다.

### 코드

> [Juno](https://boj.kr/Juno)의 코드를 변형했다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

const int MAX = 200000;
typedef long double ld;
struct point {
	ll x,y;ld p;
	point(ll x, ll y,ld p=0):x(x),y(y),p(p){}
	ll operator/(point b)const{return x*b.y-y*b.x;}
	inline int sgn()const{return y<0||(y==0&&x<0);}
};

int ix[MAX],iy[MAX];
ld ip[MAX];
void solve() {
	int n; scanf("%d", &n);
	for (int i=0; i<n; i++) scanf("%d", ix+i);
	for (int i=0; i<n; i++) scanf("%d", iy+i);
	for (int i=0; i<n; i++) scanf("%Lf", ip+i);
	int cx, cy;scanf("%d %d", &cx, &cy);

	point c(cx,cy);
	vector<point> v;
	for (int i=0; i<n; i++) {
		v.push_back({ix[i]-cx,iy[i]-cy,ip[i]});
	}
	sort(begin(v), end(v),[](const point& a,const point& b) {
		if(a.sgn()!=b.sgn()) return a.sgn()<b.sgn();
		return a/b>0;
	});
	ld ans=0,cur=0;
	int j=0,zero=0;
	for (int i=0; i<n; i++) {
		if(v[i].p<1)cur+=log10l(1-v[i].p);
		else zero++;
	}
	if(!zero)ans+=powl(10,cur);
	cur=0;zero=0;
	auto nxt = [&](int i){return (i+1)%n;};
	for (int i=0; i<n; i++) {
		while(v[i]/v[nxt(j)]>0) {
			j=nxt(j);
			if(v[j].p<1)cur+=log10l(1-v[j].p);
			else zero++;
		}
		if(!zero)ans+=powl(10,cur+log10l(v[i].p));
		if(i==j)j=nxt(j);
		else {
			if(v[nxt(i)].p<1)cur-=log10l(1-v[nxt(i)].p);
			else zero--;
		}
	}
	printf("%.10Lf\n", 1.L-ans);
}

int main() {
	// setbuf(stdout, NULL);
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		printf("Case #%d\n",i);
		solve();
	}
}