Google Codejam Round 1A 2016

• 혼자 꽤나 박진감 넘쳤던(?) 경기였다. 결국 round 2에 안착함
  
• 밖에 나갔다가 30분넘겨 경기를 시작한 상황-_- 근데 어이없게도 A, B가 어렵지 않아 B-large를 냈을 때 1700명가량이 A, B를 풀었더라. C를 안풀면 안되겠다 하고 C를 들여다보고 여러 접근을 시도했다.
• 우선 문제는 N개의 vertex와 N개의 edge로 이루어진 그래프가 주어진다. 여기에서 원형으로 vertex들을 배치해야 하는데, 각 vertex는 양옆 중 하나와 연결되어 있어야 배치할 수 있다. 이 조건을 만족시킬 때 가능한 최대 size를 구하는 것.
• 2SAT이 되나?싶어서 boolean식을 써보니까 3SAT이 나오더라ㅋㅋㅋ 최적화 문제가 되나 싶어서 시작/끝번호를 정한 dp를 생각해봐도 포함시키는 순서를 정할 수가 없었고 커버할 수 없는 케이스도 존재했다. 결국 가장 피하고싶은 ad-hoc의 case별 풀이를 시도.
• (1) 가장 간단하게는 그냥 원형으로 이어진 component를 생각할 수 있다. 이경우 다른 것은 끼워넣기가 불가능하기 때문에(그럼 원이 끊어진다) 딱 크기만큼밖에 만들 수 없다.
• (2) 두번째는 서로 연결된 pair에 각각의 vertex를 끝으로 하는 path가 연결된 형태를 생각할 수 있다. 근데 이경우는 한쪽이 뚫렸는데도 완전한 형태이기 때문에, 이러한 component는 함께 포함시켜 답안을 만들어낼 수 있다!
• (1)은 최대사이클을 구하면 되고, (2)는 위상정렬해준다음 각 vertex로 통하는 최대path의 depth를 구해준 다음 모든 이런 component의 합을 구해주면 된다. 이 둘 중 큰 것이 답.
• 사실 아이디어는 어렵지 않은데 ad-hoc을 써야겠다!까지 과정이 오래걸렸고, 코딩도 꽤 시간이 걸렸으며(그래프ㅠㅠ) (2)의 경우를 잘못생각하는 바람에 small을 틀려먹고 디버깅하는 데 시간이 따로 걸렸다. 때문에 좀 간당간당하게 패스한듯..ㅠㅠ