2023 IamCoder Qualification Test Open

2023 IamCoder Qualification Test Open

A - 옷걸이

(상의의 개수) >= (상의 걸이의 개수) and (하의의 개수) >= (하의 걸이의 개수)를 만족해야 한다.

00:04 WA

공용 옷걸이에 아무 옷이나 걸면 안 된다.

상의 걸이와 하의 걸이를 모두 사용한 후 남은 옷만 걸어야 한다.

00:08 AC

 

B - 보디빌딩

루틴은 하루에 몇 번이고 진행할 수 있으므로 마지막 날에 몰아서 진행하면 된다.

00:15 AC

 

C - 공룡 게임

다음과 같은 점화식을 세울 수 있다.

dp[i][j][k] = i번째 장애물을 (j ? "슬라이딩" : "점프") 동작으로 피하였고

                 (j ? "점프" : "슬라이딩") 동작을 마지막으로 한 시점이

                 k번째 장애물일 때 패널티의 최솟값

조금 복잡해 보이지만 경찰차 dp와 동일한 점화식이다.

00:35 AC

 

D - 낱말 퍼즐

가장 기초적인 관찰은 구간 뒤집기를 O(log N)에 수행 가능한 자료 구조로 문제를 해결할 수 있다는 것이다.

이러한 연산을 제공하는 자료 구조로는 Splay Tree와 Treap 등이 있다.

두 자료 구조 모두 풍문으로만 들어서 당장 사용할 수는 없었다.

 

분명히 다른 풀이가 있을 것이라고 생각하였다.

첫 번째 이유로 경곽의 엘리트 학생들이 'do you know blah blah ds?' 문제를 출제하지는 않았을 것 같았다.

두 번째 이유로 뒤집는 구간이 상당히 특수하였다.

하지만 대충 봤을 때 다른 풀이가 딱히 생각나지 않아 Treap을 급하게 공부하고 왔다.

01:40 AC

3000 ms 제한에 2812 ms로 겨우 AC를 받았다.

 

정해는 당연히 이러한 고인물 자료 구조를 요구하지 않는다.

예제를 몇 개 그려보면 주어지는 연산을 전체 배열 밀기 + 180도 돌리기로 치환할 수 있음을 관찰할 수 있다.

가상으로 밀고 돌리다가 2번 query가 들어왔을 때에만 제대로 출력해주면 된다.

 

머릿 속으로만 생각하지 말고 간단한 예제만 그려봤더라도 금방 풀었을 것 같다.

'구간 뒤집기 연산을 지원하는 고인물 자료 구조'에 너무 정신이 팔렸다.

 

추가적으로 출력량이 매우 많기 때문에 FastIO를 이용하면 시간을 많이 단축할 수 있다.

일반적인 코드는 대략 1400 ms가 소요되지만 쌓아 놓고 한 번에 출력하기만 해도 500 ms로 줄어든다.

여기에 모듈러 연산까지 제거하면 300 ms까지 줄어든다.

 

E - 외계 분자 (not solved)

hashing으로 푸는 문제 같았는데 지금까지 hashing 코드를 짜본 적이 없었다.

급하게 공부하고 오니 LzSeg + hashing으로 풀 수 있음이 명확히 보였다.

 

대회 종료 10분 전 코딩을 마쳤지만 예제가 나오지 않았다.

30분 동안 디버깅하다가 정체 모를 코드 한 줄을 발견하였고 지우자마자 예제가 나왔다.

며칠 후 boj에 문제가 업로드되어 제출하였더니 바로 AC를 받았다.

전혀 아쉽지는 않고 당일에 배운 개념 치고 오히려 선방하였다고 생각한다.

 

hashing을 비롯하여 대부분의 고오급 문자열 알고리즘에 아직 익숙하지가 않다.

언제 한 번 시간 내서 문자열 알고리즘만 진득하게 공부해봐야겠다.

 

F - 정화조 (not solved)

Pass

 

G - 성벽 쌓기 (not solved)

Pass

 

끝

끝