240121 팀 연습 (NWERC 2021)

각자 바쁜 일정이 대강 끝나 월파 진출을 위해 팀 연습을 열심히 돌리기로 했다. 세 명 각각의 현재 위치가 서로 너무 먼 관계로 원격 1컴 체제로 진행하였다.

 

셋 : https://codeforces.com/gym/104064 (https://www.acmicpc.net/category/detail/2887)

 

 

내가 뒤, petamingks가 앞을 보고 시작했다. kwoncycle은 10분쯤 뒤에 와서 그냥 우리가 주는 문제를 잡았다.

 

~0:20

뒤 문제들을 훑다 K 제출이 나오길래 잡았다. 구현을 잘못해 한 번 틀리고 맞았다. 이후 B를 보던 petamingks에게 수학 문제인 L을 던져 주었다. kwoncycle은 petamingks가 귀찮다고 넘긴 A를 잡았다.

 

~0:40

kwoncycle이 A를 좀 틀리고 맞았다. 나는 제출이 많이 나온 J를 잡았고, kwoncycle한테는 G를 던져주었다.

 

~0:50

이후 petamingks가 L을 금방 짜서 맞았다.

 

~1:01

J도 실수를 해 한 번 틀리고 맞았다. 다른 팀들도 많이 틀린 것을 보며 안심한 후 H로 넘어갔다. 좀 구데기였던 다른 문제들과는 다르게 H는 지문도 깔끔하고 문제도 괜찮았는데, 풀이가 당장 나오지 않아 조금 생각해보기로 했다.

 

~1:43

컴퓨터를 넘겨받은 kwoncycle이 G를 맞아왔다. 나는 D, H를 보고 있었지만 잘 모르겠었고, 솔브수가 너무 많아 풀고 넘어가야 한다고 생각해 kwoncycle에게 H를, petamingks에게 D를 같이 보라고 했다.

 

~2:19

D에 컨벡스 헐을 박으려던 찰나 petamingks가 깔끔하고 확실한 풀이를 찾았다고 해 넘겼다. 다행히 한 번에 맞아왔다.

 

~3:01

그 동안 kwoncycle이 H 사풀 비슷한 것을 냈고, 컴퓨터가 비어 있었기에 짜라고 한 후 나는 E, F를 보러 갔다. F는 웰노운 기하라 어렵지 않게 풀이를 찾을 수 있었고, E를 생각해보기로 했다. 열심히 생각해 본 결과, 가장 작은 원소는 어차피 1칸씩밖에 움직이지 못하니 이를 먼저 처리해주는 것이 최적이라는 생각이 들었다. 여기까지 생각해놓은 후 컴퓨터를 기다렸다.

 

~3:50

H 풀이가 사풀이었다는 것이 밝혀졌다. 이후 컴퓨터를 넘겨 받은 petamingks가 B를 코딩했지만, 틀렸다. E, F 2문제가 밀려 있었기에 바로 컴퓨터를 넘겨받았다. 

 

~4:08

F를 최대한 빨리 짰고, 몇 번 틀린 후 맞았다. 이후 바로 E를 짜러 갔다.

 

~5:00

E를 다 짰지만 안타깝게도 틀렸다. 이후 B, E 모두 유의미한 몇 번의 제출이 있었지만 결국 해결하지 못한 채로 시간이 끝났다. 

 

문제별 요약

A (S1, solved by kwoncycle) : 인터랙티브 딱지가 붙어 있긴 한데 그냥 귀찮은 문제라고 한다. 

B (D3, Not solved) : petamingks가 오래 잡은 인터랙티브 문제이다. 풀이는 대강 맞다고 한다. 나는 읽지 않아 잘 모른다.

C (?, Not solved) : 아무도 문제를 읽지 않았다.

D (P5, solved by petamingks) : petamingks가 핵심적인 관찰을 해 풀었다. 울타리의 모양을 항상 대각 직사각형으로 바꾸어줄 수 있다는 것이 핵심이다.

E (P2, upsolved by leo020630) : 구체적인 증명은 아니더라도, 작은 것부터 옮기는 것에 대한 직관을 가질 수 있다. 횟수는 쉽고 역추적이 좀 귀찮은데, 이 때 같은 높이를 가진 원소 처리를 잘 해주어야 한다. 무작정 하면 불가능한 move를 사용해버릴 수 있다. 이는 같은 높이 원소들에 대해 (G에서의 위치<H에서의 위치)  라면 위치 역순으로, 반대라면 위치 정방향으로 진행해주면 해결된다.

F (P2, solved by leo020630) : 웰노운 기하 문제이다. 각 점을 기준으로 정렬해 번호를 매긴 후 inversion counting과 같은 것을 해주면 된다. 디테일이 좀 필요하긴 하다.

G (P3, solved by kwoncycle) : 귀찮아보여서 넘겼다. 대충 DP 비슷하게 하면 된다고 한다.

H (P2, Not solved) : 많은 팀이 풀었지만 세 명 모두 풀이를 찾지 못했다. 어디서 본 세팅이고 심지어 비슷한 문제가 작년 교내대회 큐에 있었다. 풀이 슬라이드를 봤음에도 아직 잘 모르겠다. 좋은 문제라고는 생각해 업솔빙 예정이다.

I (?, Not solved) : petamingks가 읽었다. 나는 문제를 읽지 않았다.

J (G5, solved by leo020630) : 문제가 좀 똥이다. 지문을 꼼꼼히 읽고 나눗셈을 잘 하자.

K (S1, solved by leo020630) : 아이디어는 어렵지 않은데 구현이 귀찮다.

L (D5, solved by petamingks) : 어려운 확률 문제던데 뚝딱하더니 풀어왔다. 최고

 

 

느낀 점 + 피드백

유럽쪽 셋은 셋 퀄리티 편차가 심한 것 같다. 이 셋에도 구린 문제가 꽤 있었다. 아시아 셋으로도 연습해보자.

 

서울 리저널 H도 그렇고 다른 팀이 다 푸는 문제를 셋 다 모르는 경우가 있다. 해결법은 잘 모르겠다. 아마 내가 문제를 더 풀어야 하지 않을까..

 

후반 문제 코딩에 들어갈 때는 풀이 교차검증이 필요할 것 같다. H 코딩을 안 하거나 늦게 했으면 적어도 페널티를 줄이거나, E를 맞았을 수 있을 것 같다.

 

결과적으로 이 셋 기준 9솔은 했어야 월파에 가까운 것 같다. 우선은 실패했지만, 막 멀지도 않은 것 같아서 좀 다행이다. 

 

연습을 열심히 하자.

 

+팀연습 같이 하실 팀은 연락주세요!