SCPC 삼성 프로그래밍 경진대회
결과
- 다이어트: 100/100점
- 카드 게임: 150/150점
- 사다리 게임: 150/150점
- 범위 안의 숫자: 200/200점
- 우범 지역: 0/200점
먼저 쓰는 느낀 점
무난하게 Round 2로 갈것같다. All solve하고 싶었지만 마지막 문제 풀이를 전혀 생각 못했다. 5번은 기하 문제였는데 기하 연습좀 해야겠다. 만점이 45명 정도인데 scpc수상하려면 5번 정도 수준의 문제를 대회시간에 풀 실력을 키워야겠다. 나름 할만큼 했는데 주변에 올솔이 너무 많다 ㅠ
디스크립션이 살짝 이상한 부분이 있었다.
cgiosy, 파이도, rkm0959 님의 후기를 참고하여 작성했습니다.
다이어트
길이 $N$인 배열 $A$와 $B$에서 각각 $K$개의 수를 골라 그 합의 최댓값을 최소화하여라. $A$와 $B$의 순서는 마음대로 바꿀 수 있고 한 번 쓴 수는 다시 쓸 수 없다.
- 제한조건
다이어트-풀이
- 그리디
- 정렬
- $A$와 $B$에서 가장 작은 $K$개의 수만 사용해야 한다.
- $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])$ 이기 때문이다.
- $A[2..K]$ 와 $B[1..K-1]$ 에 대해서도 2번을 동일하게 적용하면 된다.
시간 복잡도는 $K$개를 정렬하는데 드는 속도인 $O(NlogK)$이다.
다이어트-여담
가장 쉬운 문제. 보자마자 풀었다. 부분 점수는 모든 경우를 다 해보면 얻을 수 있었던걸로 기억한다.
다이어트-코드
실제 제출한 코드와는 다르다
1 |
|
카드 게임
두 사람이 길이 $N$의 배열 $X$와 $Y$로 게임을 한다. 둘이 번갈아 가며 턴을 진행하며, 각 턴에선 원하는 배열 하나에서 맨 뒤의 수들을 여러 개 지울 수 있다. $X$와 $Y$의 수는 모두 $K$ 이하고 지우는 수들의 합이 $K$ 이하여야 한다. 둘은 최선의 전략으로 게임을 하며, 자신의 턴에서 남아있는 수가 없는 사람이 이긴다.
X와 Y에 남아있는 수의 개수를 $i$, $j$개라고 할 때, 해당 상태에서 선공이 이길지 후공이 이길지는 정해져 있다. 모든 가능한 상태 $(N+1)^2$ 개 중 $(i, j)$에서 선공이 이기는 상태의 수와 후공이 이기는 상태의 수를 구하시오. 단, 상태 $(0, 0)$은 선공이 이긴 상태로 본다.
- 제한 조건
카드 게임-풀이
- DP
부분 점수
- $(i, j)$ 상태 값이 $WIN$인지 $LOSE$인지 알려면 상대방에게 $(i’, j’)$ 로 바뀌어 넘겨주었을 때의 값들을 이용해 알 수 있다.
- 만약 $(i’, j’) = LOSE$로 변환할 수 있다면 $(i, j) = WIN$, 없다면 $(i, j) = LOSE$ 이다.
이때 채워야할 값은 $(N+1)^2$ 이고 각 칸 마다 최대 $2N$개의 값을 확인해야하기 때문에 시간 복잡도는 $O(N^3)$이다.
만점
- 한번에 하나의 배열만 건드릴 수 있으므로 $(i’, j’)$ 는 $(i, j’)$ 이거나, $(i’, j)$이다. 이때 $i’$의 최솟값을 $a$, $j’$의 최솟값을 $b$라고 할수 있다.
- 그렇다면 $(i, [b..j-1])$, $([a..i-1], j)$에 $LOSE$가 있는지 빠르게 판별하면 $(i, j)$의 값을 알 수 있다.
- 연결된 구간이므로 prefix sum을 통해 $O(1)$ 만에 구할 수 있다.
시간 복잡도는 $O(N^2)$이다.
카드 게임-여담
친구들을 보니 Grundy 게임으로 많이 접근을 해서 시간초과가 난것 같다.
카드 게임-코드
실제 제출한 코드와는 다르다
1 |
|
사다리 게임
$N$개의 세로선이 있고 $M$개의 가로선이 있다. 가로선은 $(a, b)$ 순서쌍으로 이루어지며, 세로선 $a$와 세로선 $b$를 양방향으로 연결한다. $i$번째 세로선에서 모든 가로선을 타며 내려가면 $j$번째 세로선에 도착하게 되는데, 가로선을 최소한으로 지워 원하는 세로선으로 도착하도록 만드려고 한다.
즉, 사다리가 주어지면 $Q$개의 쿼리에 대해 $i$번째 세로선에서 시작해 $j$번째 세로선에 도착하도록 만들 때 최소한으로 지워야 하는 가로선의 개수의 합을 출력해야 한다. 만약 $i$에서 $j$로 갈 수 없다면 $-1$을 더한다.
- 제한 조건
사다리 게임-풀이
- DP
- 최단 경로
- 0-1 BFS
여러가지 풀이가 있는 것으로 알고 있다. 나는 DP로 풀었다.
-
$i$ 에서 $j$로 가기 위한 최소 제거 횟수를 $dp[i][j]$라 하자. dp 테이블의 초기값은 $dp[i][i] = 0$이고 $dp[i][j]=\infty (j \ne i)$
-
$(u, v)$ 간선을 만나면 값을 $1$ 올리고 그대로 있거나, 값을 그대로 하고 바꾸는 선택이 가능하다. 최솟값을 계속 저장한다. 두 값을 동시 업데이트하는거에 주의를 해야한다.
시간 복잡도는 $O(N^2 + NM + Q)$ 이다.
사다리 게임-여담
$-1$을 더하라는건 정말 :thinking_face: 이다.
사다리 게임-코드
실제 제출한 코드와는 다르다
구현에서는 업데이트가 필요한 것만 관리하기 위해서 큐를 사용했는데 그냥 $2N$개를 봐도 무방하다.
1 |
|
범위 안의 숫자
숫자로 이루어진 길이 $N$의 문자열 $S$가 주어진다. $S$에서 임의의 숫자를 골라 1로 바꾸고, 연속한 $K$개의 숫자로 이루어진 수를 모두 나열했을 때 적절한 수 $a$를 골라 $[a, a + M]$에 있는 수의 개수를 최대화하여라.
- 제한 조건
범위 안의 숫자-풀이
- 세그먼트 트리
- 좌표 압축
- $K$값이 작은 것에 주목한다. 총 나올 수 있는 길이 $K$의 수는 $N(K+1)$개 보다 작다. 이를 모두 구해 $V$에 저장한다.
- $V$를 정렬하고 좌표 압축을 한다.
- $V$에 있는 각 원소 $a$에 대해서 $[a, a+M]$에 포함되는 $V$의 최대 인덱스 번호를 저장한다.
- range update를 지원하는 maximum segment tree를 만든 다음, 아무것도 바꾸지 않은 $S$에 대해서 $K$개의 연속된 숫자로 이루어진 수를 모두 업데이트를 한다. 이 때 업데이트를 할때 그 수의 인덱스 번호부터 3에서 구한 최대 인덱스 번호까지 구간 업데이트를 한다. 이를 통해 각 node의 말단에는 그 수를 마지막으로 하는 구간에 해당하는 개수를 알 수 있다.
- $S$의 $i$번째 숫자를 $1$로 바꾸었을때 바귀는 값을 빼고 넣고하는 과정을 반복하며 최대값을 갱신한다.
시간 복잡도는 $O(NKlog(NK))$이다.
제한시간이 10초지만 상수가 크고 테스트케이스가 있기 때문에 최적화를 조금 해야 할 수 있다.
범위안의 숫자-여담
구현을 정말 애먹었다.무려 7번 틀렸다. 인덱스 실수 하고 시간초과 나고, 대회 때는 나만 그런줄 알았는데 끝나고 보니 다들 그래서 조금 안심이다.
세그먼트트리를 안쓰고도 풀 수 있다는데 나중에 다시 봐야겠다.
범위안의 숫자-코드
공개하기 정말 부끄러운 코드인데(real_solve
등) 다시 짜기는 또 귀찮다.
1 |
|
우범 지역
N개의 점 $(x_i, y_i)$들이 주어지는데, 각 점에는 선택될 확률 $p_i$이 있다. 선택된 점들의 컨벡스 헐에 점 $q$가 포함될 확률을 구하시오. 단, $q$와 임의의 서로 다른 두 점을 골랐을 때 직선 상에 놓여있지 않는다.
- 제한 조건
우범 지역-풀이
풀이를 알려주신 @Miren0923님께 감사드립니다.
- 기하
- Sliding window
- 컨벡스 헐에 점이 있는 경우를 생각하는 것보다 컨벡스헐에 점이 없는 경우를 생각하는 것이 더 쉽다.
- “점 $q$가 컨벡스헐에 들어가지 않는다.”와 “점 $q$와 나머지 선택된 점을 가르는 직선이 있다”가 동치
- 점 $q$를 중심으로 나머지 점을 (각도를 기준으로) 원주에 올리면, 점이 하나도 없는 180도 길이의 구간이 있는 확률이 답
- 선택된 점이 없는 경우의 확률 + 선택된 점이 있는 경우의 확률을 더하면 된다.
- 점이 없는 경우: 모든 점마다 선택되지 않을 경우 확률 곱
- 점이 있는 경우: 모든 점마다 (자신이 선택될 확률) * (180도 이후에 점이 선택되지 않을 확률의 곱)
- (180도 이후에 점이 선택되지 않을 확률의 곱)을 구하려면 sliding window를 통해서 구할 수 있다.
- 여기서 실수 오차가 나는걸 방지 하기 위해서(나눗셈 없이) sparse table을 사용하면 된다.
- 그밖에도 세그먼트트리를 사용하거나 로그값을 이용해서 실수오차를 방지할 수 있다.
확률 자체는 빠르게 구하면 $O(N)$만에 구할 수도 있지만 결국 정렬을 해야해서 전체 시간 복잡도는 $O(NlogN)$이다.
우범 지역-여담
못 풀었다. 전혀 접근 자체를 하지 못했고 확률 문제다 보니 몬테 카를로로 비벼라도 볼까 했으나 여의치 않았다. 0번을 생각하면 2번까지 생각하고, 점이 있는 경우 처리하면서 재밌게 고민햇을텐데 0번을 생각하지 못했다.
브루트 포스로 $O(NlogN * 2^N)$ 에 짜는것 밖에 생각이 안났다. 저 2^N을 줄이기 위해서 생각을 많이 했다. 들로네 삼각분할을 쓰고 전처리? meet-in-the-middle? 스위핑? 전혀 아니었다.
우범 지역-코드
Juno의 코드를 변형했다.
1 |
|