240218 팀 연습 (LARC 2019)

개강을 해 버렸다. 포스텍이 1학기 개강을 빨리 하는 것은 플레이오프 진출팀을 위한 것이었음을 4년만에 깨달을 수 있었다.

이제부터 대면으로 진행한다. slah007과 시간을 맞춰 1대 3으로 진행하였다.

 

셋 : https://codeforces.com/gym/102428 (https://www.acmicpc.net/category/detail/2117)

 

 

내가 앞, petamingks가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:15

E와 M이 우후죽순 풀리기 시작했다. kwoncycle이 M, 내가 E를 짜서 맞았다.

 

~0:54

E를 짜고 자리로 돌아가서 D를 봤는데 그냥 웰노운 기하였다. 이런 문제를 초반에 잡지는 않는데 빨리 짤 자신도 있고 + 컴퓨터도 비어 있고 + 퍼솔을 하고 싶어서 바로 짰다. 안타깝게도 조금 덜 생각한 부분이 있었고, kwoncycle의 L에 잠시 컴퓨터를 넘긴 후 조금 고쳐서 맞았다. 그 와중 케이스 하나를 놓쳐서 1번 틀렸다.

 

~1:28

자리에 앉았더니 petamingks가 짜기 싫다고 I를 던졌다. 지문이 이상해서 해석이 좀 걸렸다. 다행히 읽으니 쉬워서 금방 맞았다. 이 과정에서 kwoncycle도 K를 잘 풀어주었다.

 

~2:29

사실 petamingks는 처음부터 F를 잡고 있었다. 잘 안 되는지 kwoncycle과 의논을 시작했고, kwoncycle이 뭔가 중요한 관찰을 해낸 듯 했다. kwoncycle이 끙끙대더니 어이없는 실수를 했다는 것을 깨닫고 1번에 맞아왔다.

 

~4:17

kwoncycle이 F를 짜는 동안 나는 다음으로 많이 풀린 문제인 G를 봤다. 이리 보고 저리 봐도 Suffix Array를 박아야 하는데 200솔이라 고민을 좀 많이 했다. 결국 SA를 쓰는 방향으로 생각하니 풀이는 쉽게 찾을 수 있었고, F 코딩이 끝나자마자 팀노트를 참고해 코드를 완성했다. 우선 인덱스 실수로 1번 틀렸고, 다시 제출했는데 TLE를 받았다. 그리고 30분간 같은 코드와 눈싸움을 했다. 하지만 잘못된 부분은 찾을 수 없었고, 이 과정에서 의미없는(test 번호를 보여주지 않는 실전에서는 절대 하면 안되는) 제출도 2번 했다. 그 와중 kwoncycle이 C 풀이를 완성했다고 해 컴퓨터를 넘겨주고 petamingks와 함께 틀린 부분을 열심히 찾았다. 다행히 petamingks가 뭔가 지적한 곳에서 영감을 얻어 1줄 고치고 맞았다.

 

 

~5:00

kwoncycle이 C를 짜다 끝났다.

 

문제별 요약

 

A (D3, Not solved) : 문제를 읽지 않았다.

B (P1, Not solved) : 문제를 읽지 않았다.

C (D5, Not solved) : 대회 중 kwoncycle이 풀이를 찾았다. 끝나고 본 결과 sparse table을 이용해 더 최적화해야 한다고 한다.

D (P2, solved by leo020630) : 이 문제와 비슷해서 풀이를 빨리 찾았다. 저 문제보다 조금 어려운 것 같다.

E (G5, solved by leo020630) : 쉬운 투 포인터 문제이다.

F (P2, solved by kwoncycle, petamingks?) : 관찰이 필요한 조합 DP 같다.

G (P2, solved by leo020630) : Suffix Array 응용 문제이다. 모든 문자열을 합친 후 Suffix Array를 만들자. 이후 가장 가까운 $C$의 suffix와의 LCP RMQ를 구해 더해주는 것을 반복하면 된다. 여담1) Suffix Automaton을 쓰면 쉬운 것 같다. 여담2) 코포에서도 언어 버전에 따라 verdict가 다르고, 백준에서도 계속 OutOfBound로 틀려서 당황했다. 뭔가 문제가 있는 것 같은데 아직 찾지 못했다.

H (D3, Not solved) : petamingks가 후반부에 열심히 봤다. 확률 DP라고 한다.

I (G4, solved by leo020630) : 지문만 이해한다면 그냥 위상정렬 DP 문제이다. 하지만 그래프가 DAG라는 말이 어디에도 없어서 당황하다 proved by ac 했다.

J (D5, Not solved) : 끝나기 20분 전에 문제를 읽었다. 관찰이 필요한 세그 문제 같다. 재미있어 보여서 업솔빙 예정

K (G3, solved by kwoncycle) : 문제를 읽지 않았다1

L (G2, solved by kwoncycle) : 문제를 읽지 않았다2

M (B2, solved by kwoncycle) : 문제를 읽지 않았다3

 

 

느낀 점 + 피드백

셋이 쉬워서 결과 자체는 나쁘지 않은데, 너무 많이 절었다. 최소 9솔, 아니면 10솔까지 했어야 했다고 생각된다.

 

우리 팀의 멤버 구성 특성상 내가 한 문제를 잡고 말려버리면 풀이를 낼 수 없는 문제가 큐에 계속 생긴다. 풀이를 못 내는 것은 그렇다 쳐도 코딩에서 말리지는 말자.

 

Suffix Array에서 뭘 할 수 있는지 잠시 까먹었다. 사전지식 예복습을 철저히 하자.

 

코너 케이스는 좀 넣어보고 제출하자.

 

진짜 조금 남았다.. 진짜 열심히 하자.

 

+팀연습 같이 하실 팀 구합니다