Little Piplup 8월 2일 팀연습

UCPC 전날이기도 하니, 팀연습을 해야할 것 같아서 2017 대전 리저널을 돌았다. 

내일 UCPC에 제 컨디션으로 가려면 빠르게 쓰고 자야 할 것 같으니 그냥 위치만 잡아놓고 나중에 쓸 생각이지만...

@dlwocks31 의 I HATE PS 팀에게 참교육 당했다. 같이 돈 건 아니지만. 

---

D. Happy Numbers 

Solve : Gratus907

Code : Gratus907

 

10만 번 시도해서 4로 한 번이라도 가면 안되는거니까 그냥 끊어버리고, 중간에 1로 한 번이라도 가면 성공.

사실 수백 번 안에 다 갈텐데, 그냥 넉넉-히 잡자.

---

C. Game Map

Solve : Diordhd, Gratus907

Code : Gratus907

 

주어진 그래프에서, 무방향 간선처럼 보이지만 사실은 갈 수 있는 방향이 항상 정해져 있다. 따라서 방향 그래프로 바꾼 다음, 방향 그래프에서 최대한 멀리 갈 수 있는 체인을 찾으면 된다. 들어오는 간선의 수가 0개인 점에서 시작해서, 나에게 들어오는 간선을 다 처리했을 때마다 정점을 큐에 넣는 식으로 테이블을 갱신해 주면 충분히 빠르게 처리해 줄 수 있다.  

---

F. Philosopher's Walk

Solve : Coffeetea, Diordhd

Code : Coffeetea

재귀적으로 정의된 커브 위에서의 위치를 묻는 문제이므로, 재귀적으로 내려가면 된다. 인풋의 의미를 잘못 생각해서 ($2^k = n$인 $n$이 들어오는데, 해당하는 $k$가 들어온다고 착각해서 2의 지수를 취한 것 때문에 이상한 값이 나왔다) 상당한 시간을 날려 먹었지만, 결과적으로는 그동안 우리가 코딩할게 딱히 없었으므로 큰 문제는 없었다. K번을 코딩할 수 있게 된 건 상당한 시간 후라서...

---

K. Untangling Chain

Solve : Gratus907

Code : Gratus907

그동안 Diordhd와 내가 같이 H번, I번을 읽고 40분 가까이 생각을 했는데 별 진전이 없었다. 그래서 일단 뒤로 쭉 읽으면서 무슨 문제가 있는지 보기로 했고, K번이 대충 적당히 항상 "지금까지 나온 점들 중 가장 먼 점 + 1" 로만 계속 가면 잘 풀린다는걸 깨닫고 그냥 내가 빠르게 코딩했다. 

이거 코딩 하고 나서 상당한 시간 동안 H번, I번을 팀원 둘이 같이 고민했지만 여전히 별 진전이 없었고, 상관이 있는지 없는지도 사실 잘 모르겠는 관찰을 하고 있었는데... 결과적으로는 허무해졌다. 이유는 후술.

---

L. Vacation Plans

Solve : Coffeetea, Gratus907 (Coffeetea가 핵심 아이디어를 거의 다 냈다)

Code : Gratus907 (Coffeetea가 navigator 역할을 해줬다)

H번과 I번을 계속 쳐다보다가 지쳐서, 다른 문제는 뭐가 있는지 마저 읽어보자고 했다가, 내가 문제 설명을 하면서 "너무 어려울 거 같지? 던지자. 최단경로문제같은데 못 풀겠다" 라고 말했는데, Coffeetea가 바로 "어 이거 2차원 dp를 시간에 따라 갱신하면서 풀면 되지 않냐?" 라고 말하고 $\mathcal{O}(pmn^3)$ 풀이를 제시했다. 

아니 이거 어떻게 그렇게 빨리 생각하지..?

아무튼, Coffeetea가 던져준 아이디어를 보고, 처음에는 메모리 제한을 맞출 수 있을지에 대해 약간 의문이 있었는데 (3 * 50 * 125,000 칸의 메모리를 잡고, 그보다 사실 조금 더 써야 했다)

내가 어차피 $t-1$ 시간의 정보만 있으면 되니까 3*50칸 배열 2개로 그냥 toggle 하는 식으로 짜면 된다고 하고 컴퓨터 잡았다. 그런데 사실 어차피 Coffeetea가 옆에와서 같이 페어코딩했는데, 코딩 기여도가 상당히 높았기 때문에 (내가 잔실수가 워낙에 많아서...) 그냥 컴퓨터 주고 내가 나와서 H나 I로 돌아가는게 나았을까 싶기도 했다. (어차피 그랬어도 못 풀었을 문제라서 결과적으론 의미는 없지만, Coffeetea가 짜는게 빨랐으려나)

---

G. Rectilinear Regions

Solve : Gratus907, Diordhd, Coffeetea

Code : Gratus907 (사실 셋 다 앉아서 같이 생각했다. 타이핑을 내가 했을 뿐...)

은근히 구현량이 빡센 문제.

축에 평행한 체인이 주어질 때, $L$체인으로 아래, $U$체인으로 위가 둘러싸인 직사각형을 찾는 문제인데..

첫 교점부터 마지막 교점 사이까지의 구간만 봐야 한다든가, 이런 생각들을 처음에 내가 못하고 막 짰다가 반례가 우르르 쏟아지는 이상한 코드를 작성했고, 이걸 셋이 같이 보면서 디버깅했다. 아무리 생각해도 내가 실수하는게 답이 없어서, 조금 천천히 생각하고 코딩을 하는 습관을 들여야 할 것 같다. 

코드를 누덕누덕 깁다 보니 (이거 잡고, 저거 잡고...) 결국은 코드 비슷하게 생긴 무언가? 가 되어서, 그냥 개꼬였지만 맞았으니 그러려니 하고 받아들이기로 했다. 팀원들이 TC를 잘 만들어줘서 그거만 통과하게 짜니까 맞았다.

---

페어코딩을 특히 많이 활용해 봤는데, 나쁘진 않았다. 이번에는 Diordhd가 H와 I에 좀 많이 말린 느낌이 있는데, 그래도 수요일 연습때의 Coffeetea에 비하면 훨씬 나았기 때문에... 

아쉬운 건, H번은 FFT를 이용해서 간단히 풀 수 있는 문제였고, I번은 KMP를 이용하면 거의 연습문제 수준이라는 평가를 들었다. 우리 팀이 KMP 활용을 전혀 못 한다는걸 깨닫고, 내일 UCPC를 위해 급히 KMP에 관한 글을 몇개 읽고 팀노트에 베낄 수 있는 KMP 코드를 넣어서 가져가기로 했다.

 

 

내일 UCPC 한 40등 이상만 했으면 좋겠다 :) 본선 나갔으니 티셔츠 받은걸로 만족하긴 하지만, 그래도 예선 등수보단..ㅋㅋㅋ