송도고 코드마스터 2024 Open Contest 후기

https://www.acmicpc.net/contest/view/1340

 

9월 8일 일요일에 수학 PS 대회인 MatKor컵을 온사이트에서 치기로 해서, 토요일에 연습으로 칠 만한 대회가 있을까 살펴보던 중에 이 대회가 보였다.

 

사실 이 대회는 총대가 예전에 알고 지냈던 junse2님이라 온사이트를 쳐보려고 했는데, 중/고등학생 전용 대회라 치지 못했다.

 

암튼 그래서 MatKor컵의 연습으로 이 대회를 치게 되었는데, 생각보다 퍼포먼스가 좋게 나왔다.

 

 

 

A - 코드마스터 2024 (2', +1)

A번은 코드가 단순하겠지라는 마인드를 가지고 시작했다.

예제가 하나밖에 없어서 문제를 잘못 해석해 버렸고 1틀을 해 버렸다...

1틀당 패널티가 5분밖에 안 돼서 그나마 다행?이었다고 생각한다.

 

 

 

B - 찬물 샤워 (5')

문제를 자세히 읽어 보면, 현재 온도가 어떻든 목표 온도로 정확하게 조절한다는 사실을 알 수 있고, 이 때문에 조절해야 하는 온도의 총합은 변화한 온도의 총합이 된다.

잠깐, 변화한 온도?

n, k, T 모두 필요없이 d를 모두 합해서 출력하면 된다.

 

 

 

C - 광선 다각형 만들기 (9', +3)

입력은 입사각만 주는데 출력은 각 전체를 출력해야 한다.

이거때문에 좀 말았다. 예제 좀만 더 주지..

 

 

 

D - 반려동물 준세 (12')

왠지 불가능한 경우가 없을 것 같았고, 시뮬레이션 코드 냈더니 맞았다.

 

 

 

E - 코드마스터, 슬라이딩 퍼즐 마스터, 보드게임 마스터 (16', +1)

두 개의 방향이 있는 게임에서 선공이 이기기 위해서는 두 개의 방향의 크기가 같게 해야 한다는 것은 게임이론에서 웰노운이다.

문제를 '한 번에 한 칸만 움직일 수 있다' 고 해석해서 한 번 틀렸는데, 다들 같은 이유로 틀렸다고 한다. 빨리 풀려다 보니 문제도 제대로 안 읽었던 것 같다.

 

 

 

F1 - 연강은 힘들어(Easy) (27')

이 문제부터 이 대회의 시작이었던 것 같다.

 

누가봐도 DP다. 약간 말긴 했으나, 포함-배제의 원리 비슷하게 해서 맞았다.

3차원 DP를 구현한 사람들이 있던데, 나는 아직도 포함-배제 DP들에서 (Ex: 계단 수) 3차원 DP로 어떻게 답을 구할 수 있는지 모르겠다.

알아두긴 해야 할 듯

 

사실 '필수교과'가 있는 것까지 고려해서 F2를 한번에 맞으려고 했었다.

그래서 F2에 냈는데...

 

 

 

F2 - 연강은 힘들어(Hard) (58', +1)

TLE를 맞았다.

다시 제한을 살펴보니 '필수교과'만 있는 게 아니라, 입력되는 수의 범위가 변화해 있더라.

한참 고민하다, 이미 쓴 부분을 다시 쓰면서, 현재 DP에 저장되어 있는 수들의 총합을 따로 관리해 준다는 아이디어를 떠올렸고, 이걸 구현하는 데는 10분 정도 걸렸다.

근데 Off-by-one이 계속 나서 고치는데 애를 좀 먹었다. 아니었으면 오래 안 걸렸을 듯

 

 

 

G - 도시농부

그리디하게 될 것 같았는데 아닌 경우가 자꾸 생각나서 'BFS인가?' 라는 생각을 했는데, 이건 또 입력 범위와 시간이 안 맞았다.

결국 일단 포기하고 넘어갔다.

 

 

 

H - 송도고 레일 정비 사업

특정 레일에 대해서, 어떤 레일 R을 지나고 있으면 다음 레일은 S로 가게 된다고 하면, R -> S와 같은 간선을 만들어서 트리 형태로 만들 수 있다고 생각했다.

예제를 보기 전까지는.

 

예제를 보고서는 감도 안 와서 던졌다.

 

 

 

I1 - 물탱크 알바(Easy) (104', First Solve)

범위가 작아서 트리의 모든 정점에 대해서 구한 다음 그들의 최솟값을 구하는 풀이가 충분히 먹힐 것이라고 봤다.

그래서 그렇게 했다.

 

모든 정점에 대해서 몇 개의 물통을 채울 수 있는가를 찾는 방법을, 처음에는 아래로 내려보낼 생각만 했는데 (DFS로),

내려보내기만 하면 올바른 답이 나오지 않았고, 다시 보니 어떤 물탱크 A에 물을 넣었을 때 A의 상위 정점으로 물이 이동할 수 있었다.

 

이것까지 고려해서 코드를 다시 만들기에는 퍼솔을 못 먹을 것 같아서, 퍼솔을 먹기 위해서라도 코드를 누더기같이 기워서 어떻게든 답을 구했다.

그래서 내 I1 코드는 너무 더러워졌지만, 아무튼 맞았으니 된 게 아닐까?

 

 

 

I2 - 물탱크 알바(Hard)

누가봐도 씹덕트릭인 것 같아서 걸렀다.

 

 

 

G - 도시농부 (155', +9)

거를 거 다 거르니 얘만 남았다. 얘까지 풀면 그때 시점으로 1등인 상황이었어서, 바로 잡았다.

 

그리디한 풀이가 생각났는데, 왠지 웬만한 경우에 대해서 전부 되는 것 같아서 내 봤고, 틀렸다.

 

반례를 찾았다. 조건 분기 하나로 해결했다. 근데도 틀렸다.

 

반례를 또 찾았다. 조건 분기를 하나 더 넣었다. 근데도 틀렸다.

 

반례를 또 또 찾았다. 조건 분기를 하나 더 넣었다. 그래도 여전히 틀렸다.

 

반례를 또 또 또 찾았다. 조건 분기를 하나 더 넣었다. 그제서야 맞더라.

 #greedy #case_work

 

 

얘까지 풀고 나니 스코어보드에는 3등이 찍혀있었고, 내가 H나 I2를 남은 시간 25분 내에 생각할 수 있을 것 같지 않았다.

그렇다고 다른 사람들 (4등이 7솔이었다) 이 9솔을 해서 나를 역전할 것 같지도 않아서, 여기서 문제를 그만 풀고 저녁을 먹으러 갔다.

 

대회는 이변 없이 3등으로 마무리되었으며, 나중에 알았지만 I1 퍼솔에 상품이 걸려있었다고 한다.

3등상과 I1 퍼솔을 전부 얻어서 기분이 좋았지만, 다른 한편으로는 다음 날 칠 대회였던 MatKor 컵에서 쓸 퍼포먼스를 다 끌어다 쓴 것 같아서 걱정됐다.