IPSC 2015

http://codeforces.com/blog/entry/18009?#comment-232968

이번에 ALREADY HAVE DONE이라는 팀으로 참가해서 전체 62등, Secondary 9등으로 마무리지었다.

탑텐에 떴으니 만족함 ㅎㅎ

그냥 문제 수기 쓰고 정리하려고 한다. 정리해보니 내가 이렇게 심하게 버스를 탔다는 것을 다시 한번 느낌 (...)

A : 쉬운 그리디가 존재한다. 내가 짰고 금방 풀었다.

B : 욕하는 문제인데 난 초기에 여기서 완전 말렸다 ㅠㅠ m^3개의 가능성이 존재하는데, 일단 이 중 m^2 쌍을 precomputing하고, 쿼리당 O(m) 번 brute forcing하면 딱 시간 안에 나오는 문제다. 되게 열심히 체크하고 깔끔히 짰는데 아주 기본적인 부분에서 틀리고 완전 말림. 디버깅을 죽도록 했는데 난 아직도 왜 답이 안나오는지 모르겠다. 1시간 조금 넘어서 GG치고 HYEA보고 다시 짜라 그랬는데,

C : 체스를 잘 두면 풀리는 문제인거 같다. 난 체스를 못해서.. 초기에 HYEA가 어셉먹였다.

D : 다익스트라를 돌렸을 때 정확히 X개의 정점을 방문하고 끝나는 그래프를 만들라는 문제. 음수 간선은 되지만 사이클은 안된다. 난 무섭게 생겨서 안 건들려고 했다. HYEA가 D1을 품.

E : 우리 팀이 맥이 두명인데 맥에서 이상하게 Pygame이 잘 안 깔리는 문제가 있어서 우분투 환경을 쓰는 HYEA가 어쩔 수 없이 떠맡게 됐다. 하다보니까 어셉을 먹였다는 기록이... E2 정해가 참 신박하다고 하니 볼 사람은 보자.

F : 개 이상한 풀이를 떠올렸지만 반례가 나와서 자살했다. 정해 보니까 내가 그 문제에 심하게 말렸다는걸 느낌. 어차피 못 풀었을 문제라 후회는 안감 ㅎ

G : 처음에 당연히 트리 분할정복 아닌가 하다가 분할 정복이 안 되는 것을 확인, 그 다음에 HLD를 생각했더니 세그먼트 트리가 잘 안 나오는 것을 확인. 마지막에 생각한게 2D 세그먼트 트리인데, 더 좋은 풀이가 있을 거라는 의문 + 시간 부족으로 포기. 사실 메모리만 해도 3GB는 거뜬히 먹을 거 같아서 진짜 말도 안된다고 생각했는데.. (윤모군 컴이 16GB라 실행 가능하긴 함.) 교훈은 "짜라면 짜" 인거 같다.

H : H1을 brute force로 돌려서 맞았다. H2는 깊게 생각 안했는데 첫번째 섭테는 걍 min cut이 맞는듯. 두번째 섭테는 애석하게 스포를 당했는데, 아무튼 재밌는 풀이다.

J : 윤모군이 .com 을 보고 DOS인 걸 눈치챈거 같은데 이상하게 본인은 안 돌아갔다고 하더라. 그 이후 바이너리를 뒤지고 별 짓을 해봤는데 성과는 없었음. 아무튼 재밌는 문제다. 바이너리와 실행 결과를 비교해 보면 참 신기한 문제.

(여담으로 바이너리에 써져 있는 RED HERRING이라는 말이 참 무섭다. 항상 문제 풀다 말리는 입장에서 느끼지만 말리는 건 비극적인 일이다 ㅠㅠ.. 말린거 같아서 반성하면 G같은 걸 못풀고... G같은 걸 풀고 머리가 굳으면 F를 못풀고... 반복인듯. 난 둘다 못품 ㅎㅎ)

K : 노래 듣는 문제였나? 윤모군이 풀었다.

M : 지금 description을 읽어봤는데 본격 JS 까는 문제인거 같다. 팀에서 JS를 쓸 줄 아는 윤모군이 삽질 끝에 어셉시켰다.