문제 링크 (BOJ)
풀이 슬라이드 (slideshare)
이제는 습관처럼 집을 나가는 PS 실력을 되살리기 위해 쉬운 대회를 풀어보기로 했다.
6시간 (밥 1시간) 을 세팅했고 결과는 7 / 8. B는 디스크립션을 오독해서 전혀 다른 문제를 풀어버렸다😡
A B C D E F G H
A < C = F = H < B < E < G < D
난이도는 평이한 수준. 괜찮은 문제들 + 좋은 문제 (D) 로 구성되어 있어서 퀄리티도 나쁘지 않다. 다만 돚거해온 훔친 문제 (E, H)가 2개나 들어와 있다는 게 흠이라면 흠.
문제 푸는 감을 다시 살리기에 굉장히 좋은 셋이다.
빡센 자료구조 문제 / 케이스 분석을 해보고 싶었는데 그런 문제는 안 나왔더라...
일단 B를 제외하고 모든 문제를 큰 무리 없이 푼 건 좋았다. 하지만 특유의 조심성 없는 제출로 WA 스택을 많이 쌓은 게 아쉽다... 차차 좋아지겠지.
풀이는 잡은 순서대로. 중간중간에 TMI가 있다.
A. 스텔라가 치킨을 선물했어요 (+, 5min)
주는 문제이므로 생략.
점심시간에는 C를 열심히 고민했다. Naive 생각해 놓고 안 돌 것 같아서 이상한 최적화를 했는데 전부 틀린 방법이었고, 결국 Naive를 짰더니 맞았다...
이때쯤 B 디스크립션을 한 번 잘못 읽고 Slack에 뻘질문을 했다.
C. Acka의 리듬세상 (+4, 137min)
결국 2 이상의 MOD를 다 돌면서, a[i] % MOD들 중 가장 많은 것을 찾으면 된다.
수의 범위를 \(X\)라고 하자. \(O(NX)\)는 너무 뻔하게 TLE가 난다.
가장 쉬운 관찰은 "소수인 MOD만 보자"는 것이다.
MOD가 합성수면 MOD의 모든 소인수들에서 더 좋은 해를 얻을 수 있다. 하지만 수 범위 내 소수가 약 \(1.4\times 10^{5}\)개고, \(N = 10^{3}\)을 곱하면 1억이 조금 넘는다. 나머지 연산을 이만큼? 2초 안에? 라고 생각하고 버렸다.
그 뒤로 최적화를 위해 열심히 잔머리를 굴렸다. 그러던 중 멍청하게 \(N = 1000\)으로 픽스해서 생각한 바람에 MOD = 2에서 최소 500 이상의 답이 나온다고 생각했고, 그래서 \(X/500\)까지만 돌았다가 4틀을 쌓았다.
결국 처음에 했던 불안한 관찰로 돌아왔다. 1.1초 AC. ㅋㅋㅋㅋㅋㅋㅋ
추한 코드라고 생각했는데 다행히 정해도 이거였다.
커팅을 얹으면 100ms대로 줄일 수 있다.
H. 우주선 만들기 (+, 160min)
USACO 땅따먹기의 정확한 하위호환. \(O(N^2)\)이 된다. 생략.
G. 동전 (+1, 184min)
동전의 확률 값을 \(p_{i}\)라고 두자.
그럼 죽을 확률 (동전이 짝수 개만 뒤집힐 확률)은 다음과 같다. 점화식을 써도 되고, 나는 \(N = 1,2,3\)을 손으로 해보고 얻었다.
$$ \frac{1}{2} + (1-2p_{1})(1-2p_{2})\cdots (1-2p_{N}) $$
따라서 확률이 \(1/2\)인 놈, \(1/2\)보다 큰 놈을 관리해주면 \(O(N+Q)\).
E. 토르의 여행 (+, 226min)
코포에 똑같은 문제가 있었다. 간선을 정점으로 바꾸면 끝. 심지어 풀이 포스팅도 있다! 생략.
F. 바나나나빠나나 (+, 243min)
오토마타까지 줬는데 (...) 너무 어렵게 생각했다. 재활이 필요하단 걸 절감.
그냥 오토마타를 구성하고, N번째 칸에 Accept Node에 도착하게 되는 최소 비용을 DP로 구하면 된다.
D. 복구 (+5, 323min)
이 셋에서 제일 좋은 문제라고 생각한다.
일단 문제가 덮어 놓고 이진 탐색을 하라고 시키고 있다. 답을 K로 고정하자.
그럼 가능성이 K 이하인 놈들은 지워도 되고, K보다 큰 놈은 반드시 살려야 한다. 살려야 하는 놈들을 '후보'라고 하자.
원본 수열을 편의상 A[1..N]이라고 한다.
결정 문제를 보자.
D[i]를 'i를 살렸을 때 [i,N]의 데이터를 복원할 수 있는가?'의 boolean DP로 잡자.
Base Case는 D[N+1] = 1로 둔다.
만약 i의 오른쪽에 있는 수를 하나도 안 지운다면, D[i]는 D[ i + A[i] ]에 의존한다.
만약 i의 오른쪽에 있는 수를 \(k\)개 지운다면, 당연히 D[i]는 D[ i + A[i] + k ]에 의존한다.
몇 개까지 지울 수 있을까?
i의 오른쪽에 '후보'가 A[i] - 1개 들어찬다면 더 이상 지울 수 없다.
따라서 i + A[i] + k의 최댓값은 i의 오른쪽에 있는 A[i] - 1번째 '후보'의 인덱스이다. 이 인덱스를 대충 R이라고 두자.
D[i]는 D[i + A[i]] OR ... OR D[R]이다.
결국 구간 형태의 OR이므로 부분 합으로 관리하면 DP를 \(O(N\lg N)\) 내지는 \(O(N)\)에 채울 수 있다.
결정 문제의 답은 D[1] OR D[2] OR ... D[첫번째 '후보'의 인덱스] 이다.
결국 최종 복잡도는 \(O(N\lg N)\). 나는 \(O(N\lg^{2} N)\)으로 AC를 받았다.
B. 변신 이동 게임 (+7, 371min) (Upsolved)
디스크립션 ㄴㅁㅇㄻㄴㅇㄻㄴㅇㄻㄴㅇㄻㄴㅇㄹ
나는 쿠키런마냥 '변신 게이지'가 있어서 T턴마다 게이지가 채워지고, 이동을 하면 변신이 풀린다는 말도 안 되는 망상에 기반해서 BFS를 짰고 7틀을 쌓았다.
대체 왜 예제가 나오는 거야??
실제로는
T턴의 '비용'을 지불하고 변신할 수 있고, 변신은 마음대로 풀 수 있다.
그래서 그에 대한 가중치 에지를 만들고 다익스트라를 돌리면 된다. 끝.