UCPC 2023 예선 후기
결과가 좋으므로 후기를 써야겠다.
팀적으로는 예선 6등을 먹었고, 개인적으로는 H 퍼솔을 먹어서 상당히 기분이 좋다.
개인적으로 UCPC 2022의 문제들이 상당히 좋았다고 생각하기에 즐거운 마음으로 참가했다.
작년에 예선에 광탈한 기억이 있어서 조금 쫄리기도 했다.
시작할 때 ABCD/EFG/HIJK로 나누어서 보았기에 난 시작하자마자 H를 읽었다.
H. 팔찌
조금만 작업을 해보면 팔찌를 무조건 1칸 혹은 2칸으로 바꿀 수 있다.
그리고 작업 특성상 1칸이 되었을 때의 색깔이 무조건 시작하자마자 결정된다는 사실을 알 수 있다.
2칸의 경우 RR -> RBG -> GG의 방법으로 서로간에 변환이 가능하다.
이걸 떠올렸기 때문에 이미 10분이 되기도 전에 첫 번째 팔찌를 두 번째 팔찌로 바꾸는게 가능한지 여부는 판단하였다.
-> 단순하게 1칸, 혹은 2칸으로 만들어버리고 같은지만 판단해주면 된다.
이제 첫 번째 팔찌 S를 두 번째 팔찌 T와 같게 만들어 주어야 한다.
그래서 우선 S, T를 모두 똑같은 1칸 혹은 2칸짜리인 U로 만들어주었다.
그러면 답이 되는 과정은 S -> U의 과정을 한 다음에 T -> U의 과정을 역행시키면 된다.
1 a b는 2 a ? ?로 역행하면 되고, 2 a x y도 1 a a + 1로 역행하면 된다.
그러면 팔찌가 원형이라는 사실도 안 쓰고, 돌리거나 뒤집어도 된다는 사실도 안 쓰고 문제가 풀린다.
딱봐도 조금 복잡한 문제를 처음부터 잡고 있었으니 당연히 퍼솔을 먹었다.
H를 풀면서 준서와 성현이가 E가 수학이라면서 버렸다는 이야기를 했다.
일반적인 PS 수준에서의 수학은 어느 정도 자신이 있어서 E를 시작했다. (다이아 이상의 씹덕 제외)
E. 반전수
제곱의 평균을 보면 바로 V(X) = E(X^2) - E(X)^2이 생각나기 마련이다.
따라서 문제를 바로 V(X)와 E(X)를 구하라는 문제로 바꾸어 생각하였다.
V도 구한다는게 사실 말이 안된다.
그래서 이제 V(X + Y) = V(X) + V(Y) (단, X, Y는 독립하다)를 이용해서 구할 생각을 했다.
솔직히 공분산 구해서 어떻게 하겠다는 것은 말이 안되기에 독립한 두 확률변수들을 찾아다니기 시작했다.
오랜 고민 끝에 다음을 생각해냈다.
배열을 만들 때 제일 작은 숫자부터 차례대로 insert한다고 생각해보자.
어떤 숫자 i가 q개 있고, i보다 작은게 p개 있다고 가정하자.
그렇다면 q개의 숫자가 차례로 들어갈 때, 반전을 만드는 확률변수는 등분포이다.
즉 0, 1, 2, ..., p에 대해서 모두 1 / (p + 1)의 확률로 선택한다는 것이다.
그러면 이 확률분포에 대해서 어렵지 않게 E, V 값을 구할 수 있다.
독립하다면 sum(q * V), sum(q * E)를 이용해서 답을 구할 수 있다.
하지만 이것은 맞지 않다.
첫 번째 i가 0개 만들고 두 번째가 1개 만드는 상황과 첫 번째가 1개, 두 번째가 0개 만드는 것은 중복이기 때문이다.
그래서 전략을 수정했다.
모든 숫자가 다르다고 가정하고 V, E를 구하고 거기서 같은 숫자들 간의 반전에 대해 V', E'을 구하는 것으로 수정했다.
V, E는 그냥 자기가 x번째 숫자라면 0, 1, 2, ... x - 1이 대해서 모두 1 / x의 확률로 선택하니 쉽게 구할 수 있다.
V', E ' 또한 자기가 동일 숫자들 중 x번째 숫자라면 0, 1, ... x - 1에 대해 모두 1 / x의 확률로 선택하니 쉽게 구할 수 있다.
-> 따라서 V, E, V', E'을 구할 수 있고, 최종 답안은 V - V' + (E - E')^2을 구하면 답이 나온다.
이제 남은 문제가 G, J로 두 문제였다.
J가 노솔이기에, 그리고 성현이가 J를 보고 있었기에 G를 접근하였다.
G. 은하 온라인 마케팅 프로젝트
1시간 정도 잡고 있었는데 풀지 못했다.
사실 미리 고민하던 준서의 설명을 듣고 있었는데 잘 이해를 못해서 내가 도움이 되지 못한 것 같다.
오히려 나도 그 시간에 조급해지면서 나 자신에게도 악영향을 끼친 것 같다.
이 문제를 따로 업솔빙을 했다.
이벤트를 여는 것을 조금 고민하면 다음과 같은 성질이 나온다.
1) 각 국가에서 이벤트를 유치할 도시를 선택했다면 무조건 사람이 제일 적은 도시에서 오프라인 대회를 연다
2) 각 국가에서는 적당한 상한선 밑으로 최대한의 인원을 선택하는 것이 무조건 이득이다.
제일 많은 사람을 모으는 방식은 각 국가에서 최대한의 인원을 선택할 경우이다.
이후에는 사람이 제일 많은 국가에서 사람 수를 줄이는 방식으로 이벤트 방식을 갱신해나가면 된다.
예를 들어 {10, 11, 12}명으로 이벤트를 개최한다면, 이후에는 {10, 11, (이 국가의 다음 최대인원)}으로 갱신한다는 것이다.
이제 C를 고려해주자.
만일 (최소인원 + C)가 (최대인원)을 넘지 못한다면, 그냥 C명 전부를 투입하는 것이 제일 이득이다.
만일 넘는다면, 적당한 범위 [L, R]의 p에 대해서 불균등도는 적당한 K에 대해 p - K가 된다.
그러면 Event라는 벡터에 다음과 같은 정보를 전부 넣어주자.
1) 특정값 P에서의 불균등도의 최솟값이 Q이다.
2) [L, R]에서는 p - K이기에 R부터는 K를 사용할 수 있다.
3) [L, R]에서는 p - K이기에 L - 1부터는 K를 사용할 수 없다.
4) 특정값 P에 대해서 묻는 쿼리가 존재한다.
이들을 크기 역순으로 모두 정렬해주자.
J = (현재까지 나온 값들에서 불균등도의 최솟값)
minus = {현재 지점에서 사용할 수 있는 모든 K의 집합}
P에 대해서 묻는 쿼리가 나온다면, 답은 min(J, P - (집합 minus에서 K의 최대값))이 된다.
뒤늦게 J가 다3로 내려왔다. 다2라면 안했을 텐데 다3라니까 업솔브를 시도했다.
J. 다섯 용사의 검
사실 기본적인 DP식 세우기가 그렇게 어렵지 않다.
dp[L][R] = (공격력 [L, R] 범위 내에서 최고의 칼을 찾는데 필요한 검사의 횟수)
어떤 범위 [L, R]에 대해서 MID에서 검사를 한다면 이후 구간이 [L, MID], [MID + 1, R]로 쪼개진다.
즉 [L, R]을 위해 필요한 검사의 횟수는 대충 max([L, MID], [MID + 1, R]) + 1이다.
언뜻 생각하면 단순한 O(N^3)이다. 이것도 이미 너무 오래 걸린다.
하지만 또 생각해야하는 것이 남은 칼의 조합에 따라서 [L, R]에 필요한 검사의 횟수가 바뀐다는 것이다.
dp[s][L][R] = (s 집합 내의 칼 중에서, [L, R] 범위 내의 공격력이 있을 때 최고의 칼을 찾을 때 필요한 횟수)
단순히 생각하면 칼이 많이 남으면 최고의 칼을 찾기 어려울 것 같지만, 더 남아서 더 빨리 찾는 경우도 있다.
그래서 남아있는 칼들의 set을 고려한다면 상태의 개수만 32*N^2이고, DP도 대충 1000 * N^3이 될 것이다.
칼은 더 많아지면 찾기 쉬워질 수 있지만, 구간의 경우 그렇지 않다.
구간이 넓어지면 최고의 칼을 찾는 작업이 무조건 더 어려워진다.
따라서 [L, R]에 대한 최적의 MID는 대충 [L, MID] = [MID + 1, R]이 되는 시점일 것이다.
이 사실에 이분탐색을 덧붙인다면 대량 1000 * N^2 lgN 정도까지는 줄일 수 있다.
과정은 생략하겠지만, 이 문제의 답이 커봤자 14 언저리라는 사실을 알게 되었다.
(간략하게 언급하자면, 매우 보수적인 방식으로 최고의 칼을 찾는 틀린 프로그램이 14 정도의 답을 뱉는다)
dp[s][L][R]의 모든 값들이 진짜 많이 커봐야 20 안으로 모두 잡힌다는 것이다.
그래서 위의 방식을 사용하는 dp는 포기하고 새로운 dp를 설정했다.
맨 밑의 제출은 O(N^3)을 그냥 제출한 것이고, 그 이후로는 위의 관찰을 기반으로 만든 새로운 풀이였다.
이래서 그냥 답지를 봤다.
대충 접근은 비슷했으니... 씁쓸하지만 만족한다.
dp[i][s][L] = (s 집합 내에서 i번 이내로 [L, R]에서 제일 강한 칼을 찾을 수 있는 최대의 R)
이러면 대충 오래걸려도 답을 찾을 수 있다.
왜냐하면 dp[i][s][L]을 O(32) 정도로 구할 수 있기 때문에 아주 길어봤자 1024 * N * lgN 이다.
-> t in s인 모든 t에 대해서 dp[i][s][L] = min(dp[t][dp[i-1][s][L]]) 이기 때문이다.
-> i, s, L에서 mid 값은 무조건 dp[i - 1][s][L]을 뽑아야 하니, 그 뒤에서 t가 줄 수 있는 최악의 값을 고려하면 된다.