2024 SW-IT Contest 문제 풀이 요약

에디토리얼이 빠르게 만들어질거 같지는 않아서 약간 시간 할애해서 문제 풀이를 할까합니다. 
제가 만든 문제에 한해서는 TMI도 살짝 들어가 있습니다.
 

(A) 햄버거 정렬

경우의 수가 6개 있으므로 6개에 대해서 케이스워크를 하면 됩니다.
관찰을 했다면 (1) 일때는 0번, )1(일때는 2번, 그외의 나머지 경우는 1번이라는 것을 알 수 있으므로 케이스워크를 3개로 줄일 수 있습니다.
 

(B) 다트판 

20이랑 인접한 두개의 수를 a, b라고 하면 $\frac{(a+b+20)}{3}$ 이 Alice의 점수입니다. 이 값과 Bob의 점수$(=10.5)$와 비교해서 더 큰 쪽을 출력하시면 됩니다.
 

(C) ANA는 회문이야

가장 앞에있는 A를 찾고 그 다음에 위치한 A를 찾은 다음에 그 사이에 N이 있는지를 확인해보는 식으로 구현하면 됩니다. 이 과정에서 한번 확인해봤던 문자열은 이후에 다시 확인해보지 않으므로 시간복잡도가 $O(N)$이 됩니다.
 

(D) TPS

플레이어의 위치 - 카메라의 방향 = 카메라의 위치입니다. 따라서 플레이어 기준으로 명령을 처리해주고 출력할 때는 보고있는 위치에서 한칸 뒤로 이동한 위치를 출력해주면 됩니다.처음에 바라보는 방향이 위쪽이므로 시계방향으로 위쪽, 오른쪽, 아래쪽, 왼쪽으로의 벡터값을 저장한 배열을 만들어 놨다면 구현이 편합니다.
 

(E) 전구 주기 맞추기

모든 $a_i$가 $T$의 약수면 됩니다.따라서 답은 모든 $a_i$에 가장 가까운 $T$의 약수를 $v_i$라고 한다면 $\sum_{i=N}{|a_i-v_i|}$가 답이 됩니다.약수의 개수는 $2\sqrt{T}$개를 넘을 수 없으므로 시간복잡도는 $O(N\sqrt{T})$입니다.
 
원래는 $T$가 $10^9$로 좀 더 컸으나 너프당했습니다. 
 

(F) 일이 커졌어

$\frac{N}{2}$이상으로는 홀수번째에 오름차순으로, 그 외의 수는 짝수번째에 내림차순으로 놓고 출력하면 됩니다.
 

(G) 배틀 로얄

지금까지의 누적 데미지를 저장하는 변수를 $D$라고 합시다.큐를 이용해서 가장 앞에 있는 플레이어를 뽑은 후 해당 플레이어의 체력이 $D$보다 크다면 플레이어의 공격력만큼 $D$에 누적시켜주고 플레이어의 체력을 공격력만큼 올려준 후에 다시 큐에 넣어주는 과정을 반복하면 됩니다. 플레이어가 가질 수 있는 최대체력은 $H$이므로 시간복잡도는 $O(\max(H,N))$이 됩니다.
 

(H) 의좋은 형제

$N-1$을 제외한 나머지는 $a$와 $b$를 서로 뒤바꿔도 상관이 없습니다. 뒤집어서 넣고 싶다면 $N$에, 그대로 넣고 싶다면 $N-1$에서 한번 거치고 $N$에 넣으면 되기 때문입니다. 따라서 $N-1$번 볏짚을 $N$번 볏짚에 옮기고 이후로는 둘의 차이를 크게하는 쪽으로 계속해서 합쳐나가면 됩니다.
 
이전 지문에서는 $a_n \times b_n$의 최솟값을 출력하라고 했지만 지문 수정을 거치면서 둘의 차를 크게하는 걸로 바꼈습니다. 풀이가 달라지지는 않지만 개인적으로 아쉬운 일입니다.
 

(I) 식물 기르기

모든 $a_i$를 $\frac{1}{a_i}$로 고친 후에 다 더해주고 올림하면 답입니다. double 기준으로는 오차걱정 없이 푸는게 가능합니다.
 
그림을 보면 아시겠지만 문제의 주인공은 이부키 스이카였습니다. 역시 지문 수정 후에 다른 사람이 들어갔습니다. 뭔가 그림이 혼자 노는 느낌이기도 하고 제가 그린거라 창피합니다.
 

(J) 대전 도시철도 1호선

$1$번 정점과 $N$번 정점을 잇는 정점들을 미리 방문해둡니다.이후에 방문 안한 정점 i가 있다면 dfs를 돌리면서 i를 포함하는 가장 큰 서브트리의 크기를 구하는걸 반복합니다. 이렇게 해서 구한 서브트리들의 크기를 각각 $p_1, p_2, \cdots, p_k$라고 합시다.문제의 답은 $\frac{1}{2} \{ ( \sum_{i=1}{p_i} )^2 -$  $\sum_{i=1}{p_i}^2 \}$가 됩니다.

(K) 멜로디

$1$번을 전부 방문할때까지 $1$번, $2$번을 반복해서 이동합니다. $1$번을 전부 방문했다면 $2$번으로 간 다음 이번에는 $2$번과 $3$번을 반복해서 이동합니다.
이걸 계속 반복했을 때 N 또는 N-1에서 끝낼 수 있다면 YES, 그렇지 않다면 NO입니다.

지그재그로 이동하는 것과 YES가 나오는 입력이 동치라는걸 증명하는 거는 여러분에게 맡깁니다.

이 문제의 원래 제목은 투어리스트였고 원래는 인접한 도시 방문하는 식으로 지문이 작성됐었습니다.

(L) 용감한 용사 수호

$dp(i,j)=$공격력이 $i$고 방어력이 $j$기 위해서 수호가 써야하는 장비의 최소 갯수로 놓고 냅색을 합시다.
몬스터는 $A[i][j]=$ 공격력이 $i$이하고 방어력이 $j$이하인 몬스터의 수를 저장하는 배열에 넣읍시다. 일단은 몬스터를 저장해두고 누적합을 사용하면 가능합니다.

두 개 모두 전부 구해놨으니 이제 $dp[i][j]<=k$일때 $A[i][j]$의 최댓값을 구하면 답이 됩니다.

원래 지문은 장난 아니네요☆(<- 별 붙이는게 중요함) 였고 주인공도 페코린느였습니다. 먹는걸 좋아하는 이유가 여기에 있습니다.

바로 십덕지문 정상화

(M) 계단 수열과 쿼리

 

안풀어봤지만 제가 생각하는 풀이는 다음과 같습니다.
구간에 $x$를 더하면 그 구간 내에서는 변화가 생기지 않습니다. 따라서 구간 왼쪽 끝과 오른쪽 끝만 변화가 있으므로 두 부분을 잘 갱신시켜주면서 2번 쿼리를 처리해주면 됩니다.
$seg[i][p]=$ 공차가 $i$라고 할때 왼쪽 최대길이, 오른쪽 최대길이, 현재 최대길이를 담는 구조체 세그를 만들었다고 치면 이제 1번 쿼리 나올때마다 반복문 10번씩 돌려주면서 갱신시켜주고 2번 쿼리가 들어오면 공차에 해당하는 세그트리에서 최댓값을 가져오는걸로 문제를 풀 수 있습니다.

역시 귀찮습니다

(N) 카드 뒤집기 1

망한문제특

특수한 경우부터 고려해봅시다.
우선 $a_1$은 반드시 앞면입니다. 이후에 나오는 카드들은 $a_1$보다 작다면 뒷면, 크다면 앞면이 됩니다. 뒷면이라면 어떠한 카드도 뒤집지 못하므로 뒷면은 생각하지 않고 앞면, 다시 말해서 $a_1<a_2$인 경우만 보겠습니다.
$a_2$보다 크다면 앞면, $a_1$과 $a_2$ 사이에 있다면 뒷면, $a_1$보다 작다면 앞면이게 됩니다. 우연히 $a_3$이 $a_2$보다 크다고 가정합시다. 그러면 $a_3$도 앞면입니다. 이렇게 우연치 않게 계속해서 뒤에 더 큰 수가 붙을 수 있다면 단조성을 띄어서 이분탐색을 통해 위치를 확인하는걸로 카드의 앞뒷면 판별을 로그시간에 가능하게 됩니다.

단조증가하는 특수한 조건에서 벗어나 이제 이분탐색으로 앞면인 것을 알아냈지만 이전의 수보다 작은 수일때의 상황을 봅시다.
현재 보고 있는 카드는 $a_k$가 적혀져 있고  $a_1<a_2<a_3<\cdots<a_s$까지 봤다고 가정합시다. 여기서 $a_k<a_s$를 만족합니다. 관찰을 해보면 $a_k$보다 큰 수들은 이전에 몇 번 뒤집혔는지에 상관없이 $a_k$를 만나게 되면 반드시 앞면이 됩니다. (이건 2가지 경우 다 따져보면 자명합니다.) 따라서 $a_1<a_2<a_3<\cdots<a_s$를 $a_1<a_2<a_3<\cdots<a_k$로 줄여버려도 무방합니다.
항상 짝수개의 수(앞뒷면의 홀짝성 때문)를 지운 다음에 $a_k$를 뒤에 추가하기 때문에 변화량이 홀수라
$a_k$보다 작은 수가 뒤집히는 것도 보장할 수가 있습니다.

이론적으로 문제가 풀림을 보였습니다. 구체적인 풀이는 다음과 같습니다.

$a_i$가 들어오면 스택에서 이분탐색을 해서 $i$번째 카드의 앞뒷면을 판단합니다. 만약 앞면이라면 $a_i$보다 작은 값이 나올때까지 스택에서 이전에 넣은 수들을 빼낸후에 $a_i$를 추가합니다.

끝. 실제로 구현해보면 cpp기준 500바이트 이내로도 가능합니다.

본인이 자료구조에 자신이 있다하면 그 다음 문제인 O를 풀고 오버킬을 하는게 더 쉽습니다.
본인이 비트셋을 알고있다면 비트셋으로 시뮬레이션 돌리는게 가장 쉽습니다.

(O) 카드 뒤집기 2

뒷면이 0이라서 가능했던 단조성이 이 문제에서는 불가능합니다. 십덕자구의 힘을 빌립시다.
이 문제에서도 비슷하게 카드에 적혀있는 수를 $x,y(x<=y)$라고 할 때 $x$보다 크고 $y$보다 작은 수를 만난다면 그 카드는 항상 $y$가 윗면으로 오게 됩니다. 따라서 $x$와 $y$ 사이의 있는 수 중에서 가장 최근에 추가했을 때의 인덱스 값을 구해놓고 그 이후부터 $y$보다 큰값의 개수를 세서 카드가 얼마나 뒤집혔는가를 알아내면 됩니다.
$x$보다 크고 $y$보다 작은 원소 중에서 인덱스의 최대는 세그먼트 트리를 이용하면 알아낼 수 있습니다. 찾아낸 인덱스의 값을 k라고 놓는다면 이제 k번째부터 지금까지 $y$보다 큰 값이 몇개나 있는가를 세줘야합니다. 이 과정은 퍼시스턴트 세그트리, 제곱근 분할법 그리고 놀랍게도 머지소트 트리(일반적으로 머지소트트리는 정적이지만 여기서는 뒤에 추가만 하므로, 머지를 늦게 함으로써 시간복잡도를 유지시킬 수 있습니다.)등을 사용하면 풀 수가 있습니다.

확실히 관찰할게 N보다 적어서 더 쉽습니다. 오버킬 한 사람이 승자입니다.

후기

대회 시작 3달전에 제가 군대를 갔기 때문에 추가적인 작업을 못하고 미리 만들어뒀던 문제로 어케어케 해본거라 그렇게 문제퀄이 좋다고는 생각 안듭니다...
내년부터는 아마 교내대회 열린다고 해도 저도 공부할게 있기 때문에 따로 관여는 안할거 같네요.
내년 스위트콘을 원하시는 분은 교내 루비분을 닥달해 보시는 것을 추천드립니다.

대회에 참여해주신분들, 검수진분들, 출제진분들, 그리고 마지막으로 22년부터 꾸준하게 SW-IT Contest의 책임자를 맡으셨던 ygonepiece님께 감사인사를 드립니다.