서울대학교 프로그래밍 경시대회 (SNUPC) Division 2 후기

대회가 끝났으니 Whining할 시간

 

작년에 이어 두 번째로 SNUPC에 참가했다. Division 1은 상위 10명 대부분이 World Final 참가경험이 있는 미친 고인물 집단이므로 당연히 Div 2에 참가했고, 현재 레이팅 1949라서 약간 양심에 찔리긴 했지만 아무튼 Div1에서 1~2문제풀고 3시간동안 스코어보드 구경하기 싫었기 때문에 Div2로 신청했는데, 이거 내년에는 뭔가 Div1에 나가야 할거 같긴 하고... 풀 자신은 없고...

 

뭐 아무튼 나는 Codeforces 레이팅에 비해, (그리고 평소 문제풀이 한거에 비해) 성적은 많이 안 나왔다. ㅠㅠ

내가 9등, Little-Piplup 팀으로 같이 뛴 (그리고 앞으로도 꽤 오랫동안 같이 할) Diordhd가 Div2 1등을 (:dhk: :fan:이예요!) Coffeetea가 10등 (9등까지 상 주는데 너무 아쉽다).

 

특히 뭔가 Div2에서는 꼭 상위권에 들고 싶어서 나름 빡세게 쳤는데, 그래서 망함;;;

---

A. 과자 사기

$S, N, U$ 세 종류의 과자의 봉지당 가격과 무게가 주어지는데, 5000원어치 이상을 사면 500원을 무조건 할인해 준다. 이때 세 종류의 과자를 10봉지 씩 살 때 기준으로, 무게당 가격이 가장 싼 과자를 고르는 문제.

 

그냥 시키는대로 당연히 구현하는 문제인데, 오타 나서 ( $\texttt{-=}$ 써야 할 것을 $\texttt{-}$ 썼다. ㅋㅋㅋㅋㅋ 아니 이런건 평소에 IDE가 다 잡아 주는데 ㅠㅠㅠ) 1틀. 뭔가 이거 1틀할때부터 'X발 망했네' 라는 생각이 들면서 멘탈이 살짝 나갔다. 

---

B. 평행 우주

그리디하게, 맨 뒤에서부터 "남은 점을 전부 다 밟으려면 이 점에서 최소 얼마 속력을 가져야 한다" 라는 것을 파악하면, 뒤에서부터 거꾸로 답을 계산해 줄 수 있다. 이렇게 계산한 배열의 0번째가 그냥 답이 된다.

이건 왜 1틀했는지 잘 기억이 안난다. A번 때문에 페널티 많이 밀려서 너무 급하게 짠거 같다.

---

B번까지 맞았을 때 2솔브 중에 거의 최하였고 (1번 1번씩 틀렸으니까 페널티가 일단...) 그래서 빨리 다른 문제를 풀 수 있는걸 찾으려고 쭉 읽었는데 바로 보이는게 없어서 C랑 E 중에 하나를 먼저 풀어야겠다는 생각이 들었다. 일단은 E가 조금 더 쉬울거 같아서 생각하다가 잘 안되어서 C로 다시 돌아갔는데, 뭔가 풀어야 할 문제가 많고 시간이 제한되어 있으며 빨리 풀어야 하는 경우에 내가 한 문제에 집중해서 딱 잡고 앉는걸 잘 못하는 것 같다. (이거 수능 공부할 때도 그랬는데...)

---

C. Christmalo.win

두 단어에 공통으로 들어있는 문자가 있으면 두 단어를 붙일 수 있는데, 붙일 때 그 공통 문자의 앞 (뒤에 오는 단어) 과 뒤 (앞에 오는 단어) 가 날아간다. 즉, Halloween 과 Christmas를 붙일 때 Christmas에서 뒤의 s와 Halloween의 H를 날리고 Christmalloween 으로 붙인다.

 

최소한의 문자를 잃으면서 주어진 단어들 중 두 개를 붙일 수 있는 방법을 찾아야 한다.

 

답이 어떤 문자가 될지를 먼저 찾았다고 해 보자. 만약 답이 b를 이용해서 붙이는 거라면, 모든 단어에 대해서 최대한 앞에 오는 b와 최대한 뒤에 오는 b가 어디에 있는지를 찾은 다음 (즉, b를 이용해서 이 단어를 다른 단어의 앞에 붙일 때 잃는 문자의 개수와 뒤에 붙일 때 잃는 문자의 개수를 센다) 이걸 이용해서 최소로 잃는 경우를 센다 (앞에서 잃는 것과 뒤에서 잃는 것의 최소가 답이겠지만, 두 경우가 같은 단어라면 차선을 골라야 할 수 있다). 

 

이걸 26번 하면 된다. 정확히는 단어들을 읽으면서 각 문자의 최대 / 최소 인덱스를 저장하면 된다.

구현에서 약간 막힌점들이 있었는데 이건 문자열 구현이 그냥 안 익숙해서 그렇기도 하고, 충분히 생각을 못 하고 들어간 문제가 있었던것 같다.

---

E. 순위 계산

E번은 뭔가 케이스를 열심히 나눠야 하는 문제라서, 조금 오래 걸렸다.

플레이어 X가 $r$과 $R$등 사이에 있다면, 적어도 $r-1$ 명은 이 플레이어보다 높은 점수를 받았다는 뜻이고, $R - r$ 명은 알 수 없다는 뜻이다. 새로운 참가자의 등수가 주어질 때마다 $r$ 보다 작다면 플레이어보다 확실히 높은 점수를 받았다는 뜻이고, $R$ 보다 큰 등수를 받았다면 아예 고려할 필요가 없다.

 

그 사이에서는 약간 복잡한데, 나는 "플레이어 X가 $r$ 등이기 위해 X와 동점자여야 하는 사람의 수" 를 유지해서 찾았다. 약간 실수해서 1틀하긴 했지만 E번을 푸는 과정은 뭐 그냥저냥...

---

F. 갓

조건을 잘못 쓰고 (...) 내가 정의한 변수들이 헷갈려서 (...) 2틀했다.

 

이때쯤 대회가 말리기도 했고, 성적이 생각보다 안 나올 것 같다는 느낌이 거의 확실해져서 그런지 오히려 더 조급해진것 같다. 이럴때 스코어보드 보는게 정말 안 좋은거 같은데 계속 보고 있었던듯... 

 

문제를 해석해서 수식으로 쓰면 다음과 같다.

$a, b, c, d, e, f$ 가 주어졌을 때, 적당한 자연수 $p, q, r$ 에 대하여 $x, y, z$ 를 다음과 같이 정의하자.

$$x = cq + fr$$

$$y = ap + fr$$

$$z = bp + dq$$

이때, $x > y$ 이고 $x > z$ 가 되게 할 수 있는 $p, q, r$의 존재 여부를 판단하는 문제.

 

먼저 $p$가 큰 것은 전혀 도움이 되지 않고, 항상 답에 안 좋은 영향을 미치므로 $p = 1$ 을 고정하자. 그러면 $y = a + fr$, $z = b + dq$ 가 되는데, 어떤 적당한 $q, r$에 대하여 $x > fr$, $x > dq$ 가 성립한다면 $q$와 $r$을 충분히 키워서 그 차를 $a$나 $b$보다 크게 만들 수 있으므로, 다음과 같은 부등식을 해결하는 것으로 충분하다.

$$cq + er > fr$$

$$cq + er > dq$$

만약 $c$가 $d$보다 크거나 같다면, $q$를 엄청 크게 만들면 반드시 조건을 만족하며 $e \geq f$ 의 경우도 마찬가지이므로 항상 가능하다.

만약 $c < d$ 이고 $e < f$ 라면, 위 두 부등식이 성립하기 위한 $r$의 범위를 $q$의 몇 배여야 하는지를 기준으로 구할 수 있고 그렇게 해 보면, 

$$\frac{e}{d-c} q < r < \frac{c}{f-e}q$$

그리고 $q$와 $r$은 임의의 자연수이므로 저 안에 유리수가 하나만 들어가면 되고, 좌우의 대소만 보장되면 사이에는 반드시 유리수가 있으므로 저 두개만 비교하면 된다.

---

G. KDH9949

이거 구현에 이렇게 긴 시간이 필요하고 10번을 틀릴줄은 몰랐는데 사실 왜인지 잘 모르겠다 ㅠㅠ

각 노드에 K D H 중 하나가 쓰여 있고, 반드시 KDH 순서로 밟아야 한다. (H 다음에는 다시 K) 가능한 경로의 최댓값을 찾으면 된다.

 

그래프의 간선이 양방향으로 주어져 있으나, 실제로는 $K \to D$, $D \to H$, $H \to K$ 만 이동할 수 있으므로 주어진 그래프는 사실 방향 그래프이다. 이러한 그래프에서 $K$에서 시작하여 $H$에서 끝나는 가장 긴 경로의 길이를 찾는 문제이므로, 위상 정렬로 풀 수 있다.

 

주어진 그래프를 $K$들에서만 시작해서 위상 정렬한 다음, 어떤 $K$에서 출발하여도 절대 도달할 수 없는 점들 (위상 정렬 과정에서 한번도 밟지 못한 점) 은 모두 버리고 시작한다.

위상 정렬에 실패한건 사이클이 있는거니까 길이가 무한대인 상황임을 알 수 있다.

 

그리고 위상 정렬된 그래프의 뒤에 있는 H들 부터 부터 거리를 거꾸로 세면, 반드시 중간에 한번은 $K$를 밟게 된다. (그렇지 못했으면 아까 버렸을 테니까) 따라서 뒤에서부터 거꾸로 올라가면서 센 거리 중 가장 긴 값을 찾은 다음, 그 값보다 작거나 같은 가장 큰 3의 배수가 답. (D나 H까지 올라갔을 수 있어서 마지막 처리를 해줘야 한다.)

 

DFS 한 번에 사이클도 판정하고, 거리도 갱신하고, visit도 체크하려다가 망해버리고 (....) 위상정렬을 해야겠다는 생각은 생각보다 빨리 했는데 그냥 아예 위상정렬하고 시작해야겠다는 생각을 못해서 한 5~6번 정도 틀렸다. 그리고 마지막 처리 안해서 두세번 더 틀리고...

 

그래프 구현 문제에 약하긴 했지만 그런것 치고도 많이 말렸다. 아무튼 10틀 끝에 간신히 03:30 시점쯤 맞춰서 다음 문제인 D번을 짜 보지도 못했다. 

---

여러가지 측면에서 많이 부족하다는걸 느낀 대회. 그래프나 String 구현 (각각 G번, C번) 에서 말린것도 좀 있지만, 사실 문제는 침착하게 하나씩 못 잡고 스코어보드 보면서 멘탈을 잃어버린게 문제인것 같다. 팀 대회때는 내가 멘탈을 좀 잃어도 회복할 시간이 있고, 특히 다른 두명이 풀이를 던져준 문제를 코딩하면서 멘탈을 회복할 수도 있는데 비해 이건 그게 안되다보니 그냥 끝도 없이 뇌절;;

 

당분간은 코포 칠때도 스코어보드 안보는걸 습관으로 들여야 할 것 같다. 약간 다른 상황이랑 상관없이 내 페이스에 맞추는것도 연습해야 될거 같고, 조금 침착하게 천천히 코딩하는것도 생각하고..

 

랭작은 지금까지 꽤 많이 한거 같아서, 앞으로는 OI류의 생각 많이 하는 문제들도 많이 풀어보고 새로운 알고리즘 익히면서 ICPC 준비해야지...

 

+ ICPC는 Div2 우승먹은 Diordhd가 버스 태워줄테니 리저널은 가지 않을까? :dhk: