더불어민규당 2019년 신년 연습

1월 1일

심야: Petrozavodsk Winter 2018. ITMO Contest

좋은 셋이냐 하면 그건 잘 모르겠는데... 확실히 배울 건 많은 셋이었다. 그래도 이번 신년 연습 중에서는 이게 그나마 제일 정상이었던 거 같다 (...)

• A는 적분 식을 찾았으나 너무 복잡해서 포기했다. 하지만 그 복잡한 적분을 노가다하는게 정해였다고 한다(...) 우웩
• F는 connection 정보를 관리하는 DP를 짜면, 가능한 연결 상태가 약 3000개 ~ 4000개 정도이다. 이걸 directed graph로 모델링하면, 결국 여기서 거리가 $K$ 인 walk를 찾는 문제가 된다. 이는 Berlekamp-Massey를 사용해서 해결할 수 있다. 곧 블로그에 글을 쓸 지도 모름.
• H는 directed mst라고 하는데 대회 때 생각해봤어야 했던 문제다. L에 스노우볼링 당한게 큰 듯.
• K는 Chordal graph에서 maximum feedback vertex set을 찾는 문제이다. 신이시여... Chordal Graph는 maximal clique들이 트리를 이루는 것이고, 이러한 트리를 찾는 방법은 Perfect elimination ordering을 사용하면 가능함이 잘 알려져 있다 (Interval Graph는 maximal clique들이 직선을 이루는 것이라는 걸 상기해 보면 대충 무슨 기작인지 알 수 있음). 하지만 elimination ordering을 어떻게 구하고 구조화는 어떻게 하며 흐음... New Year Contest로 지금 열려 있으니 업솔빙을 해봐야 겠다.
• L을 못푼게 정말 정말 너무 아쉽다. 수찬이가 문제를 푸는 과정에서 올바른 식을 찾았는데, 조금 더 편해질 거라고 생각했는지 이걸 약간 복잡하게 변형해서 팀원들에게 전달했다. 약간이라고 생각했겠지만, 분석하는 입장에서 그 식은 매우 복잡하다! 변형된 식은 성질 분석이나 풀이 찾기가 완전히 불가능한 식. 1시간 정도 때려박았고 내가 그 식의 암호화를 어떻게 풀 뻔도 했으나 (...) 최종적으로는 실패했다. 수찬이가 원래 적혀있는 식을 줬으면 그냥 슥삭하는 문제. 이 문제가 완전히 대회의 운명을 결정했다. 정말 너무 너무 아쉽다.

 

1월 2일

오전: ARC 068

	C	D	E	F
tncks0121	7:19	20:23	27:19	58:03
koosaga	2:56	10:28	25:44	70:13
alex9801	5:20	15:47	38:09	89:20

문제는 별로였다.

• E는 소인수분해 하듯이 각 쿼리를 루트에 하거나, 세그먼트 트리 써서 로그제곱에 하거나, 하는 문제였다. 노잼풀이 자강두천
• F는 백트래킹 돌리면 간단한 규칙이 나온다 카더라 (...) 나만 증명하고 풀었다. 하지만 노잼이라 딱히 증명할 이유는 없는 것 같다. 

오후: MIPT Autumn 2018 Day3

• E는 쉬운 문제인데 말렸다. 복잡한 자료구조인가 생각했으나, 까 보니 깔끔하고 좋은 문제였던 것 같다.
• G는 수찬이가 푼 문제. N <= 15일 때 independent set이 1 ~ 2000개인 정점 15개 이하의 트리를 찍는 문제이다. 15개 이하는 전부 돌기에는 너무 많다 ($n^{n-2}$ 내지는 $n!$). 하지만 집합 개수를 목표로 해서 Hill Climbing을 하면 "대충 잘" 찾을 수 있다. 로컬에서 이걸 몇 분 돌려보면 1700개 정도의 숫자에 대해서 트리를 찾을 수 있고 나머지는 못 찾는다. 탐색이 문제인지, 아니면 정말 저게 끝인지가 의심될 때는, 저런 문제를 낸 세터가 나보다 잘 찾았을 리가 없다고 생각하고 submit. 그리고 AC. 최근에 Petr도 GCJ에 이런 류의 문제를 낸 적이 있다. PS판을 그만 오염시켰으면 좋겠다.
• K는 풀이에 가까웠으나 I랑 같이 하다가 시간이 약간 오버되었다.
• I는 예제부터 문제 조건을 매치하지 않는다. 데이터가 틀렸다고 생각한다. 다른 팀도 많이 틀려서 등수 장난은 의미 없는듯.

심야: ACM-ICPC Singapore 2018

Kattis를 한번 써 봤다. 버추얼 안되는거 빼고 상당히 괜찮았다.

E/H 외에는 typing contest라고 생각한다. 하지만 난 I에서 하드하게 말렸다.. ㅠㅠ 그래도 속도가 생각보다 빨라서 자신감을 얻었다.

E를 푸는 데 시간을 많이 썼는데 그 시간이 정말 아깝다. 그냥 허락 맡고 탈주하는 게 이득이었을 듯.

 

1월 3일

오후: ARC 077

	C	D	E	F
koosaga	1:56	6:39	15:41	59:08
tncks0121	2:52	7:17	23:20	64:17
alex9801	2:20	9:56	24:10	-

문제들이 매우 재밌었다. F가 매우 아름다운 문제이다.

그나저나, D는 내가 카카오 코페 예선에 냈던 "부스터" 랑 매우 비슷한 문제 (약간 더 쉬운 버전) 이었다. 이뭐병; 

심야: MIPT Autumn 2018 Day5

• E는 다음과 같은 문제이다.

  • Simple Polygon, 고정된 정수 $R$, 그리고 쿼리가 주어진다. 각 쿼리는 $X_i, Y_i$ 형태인데, $(X_i, Y_i)$ 에 위치한 반지름 $R$ 의 원을 Simple polygon 내부에 완전히 들어가게 움직여야 한다. 원은 자유롭게 움직일 수 있으며 거리는 유클리드 거리를 기준으로 한다. 원이 움직여야 하는 최소 거리를 출력하라. 절대 오차 0.1 이하면 OK. $R$ 을 0.1 이하로 바꿔도 답은 동일. 항상 원이 Polygon 안에 들어가게 할 수 있음을 보장함. 좌표 범위는 $10^6$ 이하, 다각형 크기 / 쿼리 각각 200 이하.

  풀이가 간단하다고 생각해서 극초반부터 잡았고 3시간을 썼으나 결국 풀지 못했다. 제일 신기했던 건 다른 팀들이 최후반부까지 거의 제출을 안 했고 no solve로 남은 문제였다는 것이다. 그 때 다른 팀들에 주어진 선택지에 비해서 풀이가 매우 간단하다고 생각해서, 무슨 이유였는지 궁금하다. 오차가 빡빡했고 그 팀들에게 그 사실이 명확했거나, 아니면 데이터가 틀려서 clar가 가지 않았을까 생각된다. (자꾸 데이터 얘기를 왜 하냐면.. 이번에도 예제가 문제 조건을 매치하지 않았다)

• B는 아름다운 문제. ARC 101F 를 최근 푼게 도움이 됐다.

• D는 민규가 공식을 찍어서 맞췄다. 입력이 커서 그럴듯한 공식을 찍어보고 계산기로 검증해 볼 수 있다.

• G는 문제를 잘못 읽어서 못 풀었다 ㅠㅠ.. 확실치는 않은데 그냥 귀찮은 tree dp라고 생각하고 있다.

• H는 확실하게 귀찮은 tree dp다 (...) 케이스를 몇 개를 나눠야 할까..

• I는 흥미로운 문제 같은데 풀이는 모르겠다.

• C J는 쓰레기. 팀원들이 4시간동안 미적분을 정말 열심히 하고 있었다. 눈물이 났다..

나의 경우에는 E 때문에 시간과 멘탈을 완전히 소모했고, E를 포기하면서 대회를 같이 포기했다. 이 때부터 그냥 재밌어 보이는 문제만 잡자고 생각했고, B I를 스코어보드 상관없이 풀려 시도했으나, 결국 B만 풀 수 있었다. 빡겜하려고 했으면 G 디스크립션을 한번쯤 다시 봤을 거 같긴 하다..

이렇게 MIPT Autumn Camp 연습을 다 돌았다. 야호! 함께해서 x같았고 다시는 만나지 말자

 

1월 4일

오전: ARC 063

	C	D	E	F
tncks0121	7:58	22:28	39:11	-
alex9801	4:50	11:41	45:04	-
koosaga	4:58	13:48	45:47	-

나는 E가 구현하기 빡센 문제라고 생각했는데 나만 그렇게 생각한 거 같다 ㅠㅠ

수찬이는 110:32 에 F를 풀었다. 수찬이 풀이에는 증명하지 않은 Lemma 하나가 있었는데, 그대로는 반례가 있었으나 약간 강하게 바꾸니까 쉽게 증명이 되었다 (구현은 강한 형태로 해서 상관 없었음). Lemma의 내용은, 최적해가 항상 바운딩 박스를 반으로 나누는 축평행 직선 둘 중 하나를 지난다는 것이다. 이 Lemma는 공식 풀이에도 없었던 것인데, 이걸 사용하면 구현량과 복잡도가 크게 줄어든다. 나는 Lemma 없이 깡으로 F를 구현하다가 이것 저것 문제만 생기고 대회가 끝났으나, 수찬이는 약간의 추가 시간 이후 무난하게 F를 해결할 수 있었다. 갓.

점심: CERC 2018

• B는 잘 알려진 Dynamic Connectivity 연습 문제였다. 민규가 Path compression을 해서 TLE를 받았다 (...)
• D는 물리였다. 수찬이보다 빨리 풀었다 (자랑 맞음)
• F는 "정의를 이 정도로까지 생략할 수 있구나" 싶은 정도의 문제였다.
• 모든 5개의 말에 대해서 서로 다른 케이스를 구현해야 하는 H의 갓문제성에 감탄했다. 심지어 말의 이동 방향은 정의를 안 줬다. 체스를 안 해봐서 이것도 걍 sensible하게 찍었다..

독해가 상당히 어려운 셋이었다. 특히, 제대로 정의된 것들이 거의 없어서 문제를 어느 정도 찍어야 했다. 풀이 난이도는 꽤 쉽고, 코딩량은 그저 그런 정도. 역대급 노잼 CERC였다.