7/11 팀연습 (ICPC Japan 2017)

2017 Asia Tsukuba Regional (일본꺼)

총평

아직 갈 길이 멀다.

왜 항상 04:00~05:00 구간이 제일 활발하지?

단절선 알고리즘을 까먹지 말자.

long long을 쓰자.

문제에 쫄지 말자. (5분씩은 다 생각해보자.)

피드백

초반 푸시는 괜찮았다.

1~2시간 구간 때 시간을 좀 낭비한 것 같다.

(우리가) G를 빨리 읽었어야 했다.

(내가) 단절선을 잘 알았어야 했다. + 침착하게 코딩했어야 했다. (단절선 이슈 때문에 너무 말렸다)

슈퍼-그리디를 낼 땐 한 번쯤 반례를 넣어보자?

---

시간 기록

A~D -> amel

E~H -> knon0501

I~K -> namil208

 

00:07 (A +)

- A가 가장 쉬운 문제일 리 없다고 생각했으나 놀랍게도 개쉬워서 후딱 품 (간단한 DP)

 

00:23 (B +)

- B가 2번째로 쉬운 문제일 리 없다고 생각했으나 무려 N = 16

- 그냥 2개씩 짝짓는 완탐 돌리면 되는건데 생각보다 구현이 더뎠음

 

00:37 (C +)

- C가 3번째로 쉬운 문제일 리 없다고 생각했으나 스코어보드를 보고 납득

- 남일/세윤 다 문제 이해가 안된다.. 고 GG

- 문제 이해가 안될만 했다. 간단한 그리디 후딱 짬

 

01:08 (I +1)

- (아마도) 계속 잡고 있었던 남일과 I 상의

- 강의실 배정 어떻게 푸는지 둘다 까먹어서 헤멤 ㅋㅋㅋ

-- 나는 pq라고 주장하고 남일은 multiset이라 주장해서 일단 pq로 냈다가 개같이 WA

-- 나중에 찾아보니 pq로 할거면 시작시간 기준으로 sort하면 되는 거였다.

 

01:??

- 이때까진 순위가 매우 좋아서 싱글벙글 중

- 세윤이 K를 잡고 팀노트에서 BCC 옮겨적었던 것으로 추정

- 근데 어느새 키보드에서 손 뗌

-- 끝나고 생각하니 K에 버린 시간이 매우 아까움..

 

01:57 (E -1)

- E를 세윤이 슈퍼-그리디로 냈으나 WA

02:30 (E -2)

- 반례를 찾고 다시 슈퍼-그리디를 시도했으나 WA

- 이것도 반례를 찾고(남일) 그리디 풀이 포기

 

02:36 (F 맞왜틀 시작)

- F를 남일과 다익 돌려서 minimum DAG를 구성하고 단절선을 찾자는 풀이를 냄

- 그런데 단절선 알고리즘을 아무도 모르는 이슈 발생 + 팀노트에도 없음 ㅋㅋㅋ

- 즉흥적으로 짜서 냈지만 어림도 없음

~ 02:49 (F -3)

- 무언가 고쳐서 냈지만.. 1) DAG에서 도착점에 기여하는 간선도 잘못 골랐었고 2) 중복 간선 처리도 안했었음

- 이때 진짜 미칠 것 같았다. 실전에서는 이때쯤 맞아줘야 하는데..

 

03:07 (E +1)

- F 똥꼬쇼 하는 동안 혼자 E 풀이를 알아낸 세윤이 빠르게 코딩하여 AC

- ㄹㅇ 대단한듯

 

04:17 (G +)

- G가 날먹 수학문제임을 파악했었던 남일이 서른줄 코딩 끝에 AC

- G를 좀 더 빨리 읽고 빨리 짰어야 했다. 스코어보드 + 지문 그림 보고 쫄아갖고

 

04:28 (F +5)

- 보다못한 세윤이 F를 혼자 풀고 코딩해서 맞았다..

- 단절선 문제가 아니라고 했는데, 정해는 단절선이긴 했다.

 

~ 05:00

- K에서 tree를 구성하지 않는 16개의 추가 간선에 대해 2^16의 선택 경우에 대해 슈퍼-그리디하게 count해서 내봄

 

번외

- F 다익 돌릴때 pair<int, int>를 pair<long long, int> 로 바꾸기만 했는데 맞았다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ