APIO 2015

APIO 2015

작성중인 지금 시간은 토요일 오후 8시. NDA가 있어서 공개는 좀 늦을듯.

A : 만들어 놓을 값을 정해놓은 후 (parametric 엇비슷) dp를 돌리면 된다. APIO 역대 문제를 감안하면 제일 쉬웠던 문제인듯. 섭테 케이스 나눠서 짜게 한거 뭐 이해는 간다만 좀 별로였다. (C번도 그런 식이긴 하지만 뭐..)
여담으로 아무 생각없이 짜서 아직 내 풀이가 왜 되는지 모른다. 그냥 어셉먹기에 그런 줄 알았다.

B : N^2 다익스트라 + NM 그래프 생성으로 57점 긁었다. 개인적으로 그 57점이 이번 대회 가장 쉬운 섭테였다.

N = 30000은 풀이가 정말 다양했다. 내가 본 복잡도가 N^1.5 / N^1.5lgN / Nlg^3M / N^2 (...) 인데 N^2 커팅은 AC고 N^1.5lgN은 TLE라는 경험담을 봤을 때 Problemsetter가 아무리 생각해도 성의없이 대회를 준비한거 같다. constraint를 바꾸거나 저격을 넣거나 해야 하는데 ㅡㅡ;;

대회 당시. subquadratic 솔루션에 대해 아무 생각이 없었다. 나는 dummy node를 잡는 식으로 생각을 했는데 실패했다. 실제로 그렇게 짠 사람도 많았지만 아닌 사람들도 많았다. 강한필 선배의 meta graph 비슷한 솔루션을 듣고 오는 길인데 가장 괜찮은 솔루션인거 같다. 나중에는 저걸로 시도해봐야 겠다.

C : 굉장히 노력했는데 63점에 그쳤다. K = 2일 때 도저히 인자를 2개 미만으로 못 줄였다. 난 N^2lgN 풀이가 130줄이 나왔는데 정해는 이것보다 훨씬 쉬운듯 (...) 풀이를 보니까 진짜 거의 다 왔던거 같은데 아무튼 아쉬움이 정말 크게 남는다. 나중에 꼭 다시 풀어보고 싶은 문제다.

총평
내가 잘 풀었다는 말은 아니지만 (^^;) 전반적으로 APIO 치고는 매우 쉬웠고 대회 준비가 굉장히 미흡했다. 1. 난이도 조절이 실패했고 2. 문제 테스트 케이스도 약했으며 3. 서버도 툭하면 날아가고 4. 자체 그레이딩 시스템 수준이 상당히 떨어졌다. 안 좋은 선례로 남을듯한 APIO이다...

개인 성적에 대해서 평론을 하자면 지금까지 내 위에 딱 5명 있는 걸 확인했다. 6등이라는 뜻인데 어디까지나 내가 본 걸로만 얘기하는 거라서 확실치가 않음. 한명이 더 발견되면 정말 ㅠㅠ 발견 안된다면 동메달 정도 나올거 같다.

어째 열심히 한다고 하는데도 영 신통치가 않은 거 같아서 좀 아쉽다. 특히 요즘 그게 심하다. 작성중인 지금은 코드잼을 안 봤는데 그것까지 못보면 요근래 너 잘본게 뭐니 ( = 잘본게 없음) 적어도 IOI 때는 다른 대표분들께 누가 안되도록 해야겠다.

(APIO 2015 오픈 컨테스트 종료는 한국 시간으로 월요일 오후 10시입니다. 다들 수고하셨어요.)

(C번 문제는 아까 풀이를 이해했습니다. 그리디 문제에 약하다는 생각을 자꾸 하게 되네요 (...) 코딩은 금방 될 거 같습니다. 링크 남깁니다. http://amugelab.tistory.com/ent…/Palembang-Bridges-APIO-2015)