220422 팀 연습 (LARC 2018)

일정상의 관계로 slah007 선배와 둘이 진행하였다.

셋은 Latin America Regional Contests 2018을 사용하였다.

 

~00:06

A가 쉽다는 소식을 듣고 코딩 컴퓨터를 잡은 내가 바로 짰다. 실수 오차때문에 2번 틀리고, 입력을 string으로 받아서 AC를 띄웠다.

 

~00:08

뒤부터 문제를 보다 보니 M도 그냥 쉬웠고, 바로 짜서 맞았다.

 

~00:23

선배가 B가 쉽다고 하셔서 컴퓨터를 넘겼다가, 맞왜틀을 당하시길래 D를 금방 짤 수 있던 내가 들어가서 바로 짰다.

 

~00:31

같이 틀릴 이유가 없는 B 코드를 열심히 보았고, 내가 반례를 찾아서 if문 한 줄을 추가했더니 맞았다.

 

~00:45

M을 볼 때 슬쩍 봐둔 L을 선배한테 드렸는데, 굉장히 빨리 푸셨다. 그냥 뇌 비우고 에라토스테네스의 체+머지소트트리를 박으면 풀리는 문제이다.

 

~01:29

꽤 오랫동안 노솔브 상태를 유지히다가, 남은 문제중 그나마 쉬워보인 H를 한가지 관찰을 통해 맞았다. N-1개의 간선만 남겨도 된다는 관찰하면 쉽게 풀 수 있는 다익스트라 응용문제인데, 같은 정점 쌍 사이에 간선이 여러 개 있을 수 있어서 이를 전처리하는 과정이 상당히 귀찮다.

 

~02:10

너무 해석하기 힘들었던 C의 지문을 결국 알아내버렸고, 짜서 맞았다. 문제 자체는 Simple DP이다.

 

~02:50

거의 마지막까지 G와 I를 5분 간격으로 바꿔가며 코딩했는데, 결국 선배가 I를 맞아오셨다. 문제는 케이스워크가 까다로운 트리 DP인 것 같았다.

 

이렇게 8/13솔로 연습을 마무리하였다. 3시간에 2명이라는 조건 치고는 괜찮은 결과 같다.

 

문제별 정리

 

A (S3, solved by leo020630) - 단순 수학 문제인데, 입력을 실수로 받으면 오차때문에 틀린다. 문자열로 받아준 후 정수로 바꿔 풀면 쉽게 AC를 받을 수 있다.

B (G5, solved by slah007) - 누적 합과 이분 탐색을 잘 사용해주면 문제를 해결할 수 있다. 

C (G3, solved by leo020630) - 문제 자체는 단순 DP인데, 지문이 좀 해석하기 어렵게 쓰여 있다.

D (S4, solved by leo020630) - 단순한 문자열 구현 문제이다.

E (P2, Upsolved by leo020630 & slah007)- 귀찮아보이는 기하 문제인데, 연습 중에는 큐가 비지 않아 잡지 않았다. 연습이 끝나고 업솔빙하였고, 여집합을 세는 방식으로 접근하면 짧은 코드로 AC를 받을 수 있었다.

F (P1, Upsolved by slah007) - Functional Graph의 구조를 파악한 후, 중국인의 나머지 정리를 열심히 짜면 된다고 한다. 난 아직 CRT에 대해 깊은 이해를 하지 않았기 때문에 조만간 공부한 후 풀어볼 예정이다.

G (D4, Not solved)- 예제가 상당히 허술해서 연습중에 코드를 대충 짠 후 개돌했는데, 알고 보니 틀린 식이었다. 티어가 티어이니만큼 어렵지 않을까 싶다.

H (G2, solved by leo020630) - 다익스트라에서 필수적인 간선의 개수가 \(N-1\)개라는 것을 이용하는 문제이다. 간선이 중복될 수 있어서 전처리가 조금 필요하다.

I (P3, solved by slah007) - Case Work가 더러운 트리 DP라고 한다.

J (D3, Not solved)- 안 읽었다.

K (P2, Upsolved by slah007) - Constructive 문제인데, 한 5분 생각한 후 풀이가 안 보이길래 빨리 접었다.

L (P3, solved by slah007) - 노잼 자료구조 문제이다. 에라토스테네스의 체와 머지 소트 트리를 알면 풀이는 금방 찾을 수 있다.

M (B1, solved by leo020630) - 그냥 구현 문제였던 것 같다.

 

느낀 점

코딩을 깔끔히 하자

어려운 문제도 풀 수 있도록 해보자

제출 막하지 말자