"I'm Pretty much fucked"
그것이 내가 라운드 시작 15분 뒤 내린 결론이다.
나는 좆됐다.
1. Task
쉬운문젠데 또 "Case" 문자 잘 못 출력해서 20분은 날렸다. 정말 잘 못 된 습관이라 신경써야지 생각은 했는데...
문자열이 주어지는데, 각 문자를 2번씩 쓸 수 있는 기회가 주어질 때, 알아서 기회를 잘 써서 사전순으로 가장 작은 문자열을 만들어서 출력하는 문제다.
$n$이 매우 작기 때문에 무지성 O($n^2$)으로 해결했는데, 업솔빙 하면서 좀 정리해보니 O($n$)으로도 풀리겠다.
먼저, 만약 모든 문자가 distinct하다고 가정하면, 문자를 복사해서 사전순으로 작아지는 경우는 다음 문자가 현재 문자보다 더 큰 경우 뿐이다. 길이가 길어지더라도 더 작은 문자가 나오기 때문에 무조건 이득이다. 반면, 더 큰 경우는 당연히 무조건 손해다.
여기서 문자가 distinct하다는 가정을 없애버리면, 다음 문자가 같은 문자인 경우를 고려 해야한다. 다음 문자가 같은 경우는 모두 뛰어넘고, 가장 가까운 다른 문자와 비교하여 위의 로직을 돌아야한다.
그냥 무지성으로 for loop 2개 돌면서 다음 문자를 찾아도 되고, 전처리로 다음 문자 index를 전처리 해도 되고, 같은 문자들끼리는 묶어서 cnt로 처리해도 가능하다.
백준 기준 골드 4~5 예상
2. Equal Sum
진짜 쉬운데 왜 못 풀었는지 이해가 안 된다. 문제 이해에 조금 오래 걸렸고, 문제 이해하자마자 1분만에 풀이가 나왔는데 구현하다가 이래저래 꼬여서 터졌다.
우리가 $n$개의 서로 다른 수를 입력으로 주면, 상대가 그것과도 서로 다른 $n$개의 수를 보내준다. 총 $2n$개의 수를 2개의 그룹에 개수 상관없이 적당히 배분해서 두 그룹의 숫자의 합이 같게 만드는 문제다. 우리가 $n$개의 수를 어떻게 보내주든지 $2n$개의 수는 짝수임을 보장해준다. 다만 반드시, 두 그룹의 숫자의 합이 같도록 만들 수 있음을 보장하지는 않는다.
당연히 bit단위로 쪼개서 30개 보내면(수 범위가 $10^9$이므로 $2^0~2^29$까지)모든 수를 표현할 수 있으므로 30개를 2의 배수로 쭉 보내주면 된다. 문제는 나머지 70개를 어떻게 보내느냐인데, 여기서 많이 꼬여서 1시간을 날렸다.
먼저, 상대방이 보내준 수를 모두 같은 그룹에 넣어버리면 $10^11$가 되어버리므로 우리가 무슨 수를 보내든지 합이 같도록 못 만든다. 따라서, 상대방이 보내준 수를 어떻게든 두 그룹에 나눠야한다. 상대방이 보내준 수를 정렬해서 순서대로 2개씩 보면서 작은 수는 그룹 $l$에, 큰 수는 그룹 $r$에 넣어주면 두 그룹의 차가 최소가 된다. 이렇게 해주면 두 그룹의 차의 최대값은 $5 * 10^8$이 된다. 따라서, 이제 $2^0~2^29$의 수로 표현해줄 수 있다.
30개의 $2^0~2^29$중 두 그룹의 차를 표현할 bit를 $l$에 넣어주면 두 그룹의 합이 같아진다. 문제는 여기서 발생하는데, 나머지 bit를 표현하는 수와 나머지 70개를 어떻게 잘 섞어서 두 그룹에 넣어서 합이 0이 되도록 만들지 이다.
내가 푼 방법은 일단 두 그룹의 차를 $diff$라 할 때, 먼저 70개의 수를 $diff$에 더해준다.(그룹 $r$에 추가해준다.) 70개의 수를 적당히 작은 수로 해주면 범위내에 들어올 수 있다. 나는 10000~10070까지 넣어줬다.
그리고 $diff$의 bit를 확인해 줄 때, 큰 bit부터 확인하면서 그 bit가 LSB이면 $l$에 추가해주고, 아니라면 $r$에 추가해준다. 그러면 $diff$가 절대로 남아있는 가장 큰 bit * 2 보다 클 수가 없으므로, $diff$가 얼마가 되던지 표현해줄 수 있다.
조금만 생각해보면 엄청 쉬운 문젠데... 위에서 bold처리한 "나머지 70개를 어떻게 보내느냐"와 $diff$에서 0인 bit들을 나타내는 수는 어떻게 보내느냐를 고민하다가 "70개와 0인 bit 수를 섞어서 어떻게 0을 만들지"로 가버리는 바람에 문제가 많이 복잡해졌다.
백준기준 플레 4~5 예상
3. Weightlifting
매 판마다 들어야할 각 원판의 개수가 주어진다. 원판은 stack의 형태로 쌓아진다. 제일 처음엔 stack이 비어있고, 모든 판이 끝나고 나면 stack을 비워야한다. stack에 push하거나 pop하는 연산의 합을 최소화 시키는 문제이다.
== 작성중
