엘리스 알고리즘 코드 챌린지, 본선 후기 및 문제 풀이

정보

"오프라인 본선: 외부 IDE, 라이브러리 사용 가능, 인터넷 검색 불가능. 온라인 예선: 제한 없음"이라고 예선 안내에서 명시한 것과 달리 본선 안내에 따르면 외부 IDE, 라이브러리, 인터넷 검색이 불가능하다. 오프라인 교육장에 있는 맥 컴퓨터와 엘리스 사이트의 내장 에디터(프로그래머스와 동일하다고 보면 된다.)를 사용하게 된다.

기타 사항은 예선 때와 동일하다. https://leeingyun96.tistory.com/35 참고.

총 참여자는 60명 정도이고 3번 문제를 제외한 만점자는 8명 정도이다.

샌드위치와 과자와 음료를 제공한다. 콜라는 없고 오렌지 주스, 포도 주스만 있었다. 뻔뻔하다면 조금 일찍 와 식사 대용으로 샌드위치를 두세 개 먹는 것도 괜찮아보인다.

 

소감

1	2	3	4
엘리스 토끼의 자취 도전기 (==)	엘리스 토끼의 연구 (==)	엘리스 토끼의 게임 체험 (==)	엘리스 토끼의 요금제 (==)
.	.	음수 사이클이 중도 해소되는 최단 경로	.
플4	파이썬 골3, 나머지 플4	플1	플3
수학, 삼각함수, 브루트포스, 기하학	수학, 정수론, 조합론	벨만-포드	트라이

문제는 요약하자면 위와 같다. 난이도는 플1~플4 수준이다.

문제의 핵심적인 퀄리티는 만족한다. 왜냐하면 이미 검증된 문제들을 4문제 전부 표절했기 때문이다. 예선이 끝날 무렵 표절 사과문을 올린 데에 이어 다시 본선 오프닝 세션 때 사과를 하고 출제를 맡은 엘리스 직원이 얼굴과 이름을 공개하면서 직접 자신의 옛날 시스템이 미비했던 시절의 PS/CP 경험을 말함과 동시에 문제에 신경썼다는 말을 했는데도 또 표절이 발생했다. 해당 인물은 블로그, 깃허브를 터트렸다는 소문이 있다. 표절된 백준의 문제들에 대해 대회 직전에 제출이 이루어진 것이 확인되었고 표절자로 추측되고 있다.

문제의 부차적인 퀄리티는 만족하지 않는다. 표절한 원문에 비해 문제 2의 불필요한 수의 정의가 지나치게 불친절했다. 문제 다시 보기가 불가능하고 기억이 흐릿해 확실하진 않지만 문제 3이 표절한 문제의 원문은 round up, 즉 올림인데 번역은 반올림으로 되어있어서 문제를 푸는 게 불가능했고 이 때문에 시상은 문제 3을 논외로 하고 이루어졌다. 잘 들리지 않아서 구체적인 사항은 모르겠으나 문제 3에 대해 다른 사항을 강하게 오래 지적한 사람도 있었다.

진행은 만족하지 않는다. 말 해줬어도 못 풀었겠지만 문제 3의 논란을 공개적으로 말해줬으면 어땠을까 싶다.

나에 대해서는 만족하지 않는다. 난이도를 보면 놀랄 일은 아니지만 한 문제는커녕 부분 점수조차 아예 받지 못한 점이 아쉽다. 미숙한 트라이를 쓰는 문제 4를 포기한 건 그렇다치고 문제 1, 2, 3 중에서 가장 어려운 문제 3에 두 시간을 쓰고 그 다음으로 어려운 문제 1에 삼십 분을 쓰고 가장 쉬운 문제 2는 훑어보고 넘긴 것이 아쉽다. 다음부터는 막히면 다른 문제를 푼다든지 순서대로 푼다든지 하는 방식을 써야겠다.

 

문제들

문제 1.

문제는 엘리스 토끼의 자취 도전기(Move Away, https://www.acmicpc.net/problem/15126, 플4)이고 백준 문제와 동일하다.

잘 관찰을 해보면 정답이 되는 지점은 원과 원의 교점이거나 원의 원점으로부터 가장 먼 점임을 알 수 있다. 브루트포스로 해당 지점들을 모두 구한 후 조건을 충족하는 경우에만 최댓값을 갱신하면 된다.
해당 지점의 좌표를 구하는 데에는 코사인 법칙과 삼각함수를 이용하는 방법이 있고 직선의 방정식을 이용하는 방법이 있다. 이때 원이 (0, 0)을 중심으로 한다면 이 원의 원점으로부터 가장 먼 지점은 무한하므로 예외 처리를 해줘야 한다. 그러한 원의 중심을 EPS만큼 옮겨주거나(정답 확인) 풀이가 ans = -INF, ans=max(ans, dist(candidate))와 같은 꼴일 때 ans 초기값을 그러한 원의 반지름으로 설정해주면 (정답 미확인) 된다.
TODO.

 

문제 2.

문제는 엘리스 토끼의 연구(불필요한 수, https://www.acmicpc.net/problem/2378, 파이썬 골3, 나머지 플4)이고 백준 문제와 동일하다.

첫 몇 항을 손으로 공책에 써보면 이항계수임을 파악하기는 어렵지 않다.
하지만 손으로 적은 수들에 이끌려 파스칼의 삼각형을 구현하면 메모리와 시간이 터진다. 따라서 삼각형의 마지막 행만 나이브하게 nCr로 O(개수*큰수연산, N=1e5일 때 최대 3만 자리)로 구해야 한다. 그렇다고 이걸 다 저장하면 메모리가 터진다. 따라서 그때그때 불필요한 수인지만 판별해야 한다. 불필요한 수인지 아닌지 판별은 모듈러 성질에 따라 x%M==0이면 x는 불필요하기 때문에 간단한 모듈러 연산으로 판별할 수 있다. (골3, PyPy3 8001ms).
x%M==0이라는 건 x의 소인수분해의 지수들이 M의 소인수분해의 지수들보다 크다는 걸 뜻한다. x=nCr=n!/(n-r)!/r!이니 n!, (n-r)!, r!, M의 소인수분해를 빠르게 하고 각 소인수마다 지수의 대소를 비교하면 된다. (이항 계수 5, https://www.acmicpc.net/problem/11439와 동일한 플4, PyPy3 200ms).
x=nCr=(nCr-1)*(n-r+1)/r이니 (n-r+1), r의 소인수분해를 빠르게 하고 각 소인수마다 지수를 갱신한 뒤 지수의 대소를 비교하면 된다. (골2?, PyPy3 ?ms).

 

문제 3.

문제는 엘리스 토끼의 게임 체험(Wormholes, https://www.acmicpc.net/problem/3680, 플1)이고 백준 문제와 동일하다.

음수 간선과 음수 사이클이 중간에 해소가 되는 최단 경로 문제이다. 나이브하게 사이클을 한 번씩 돌며 해소될 때까지 반복하는 것은 시간 초과가 나기 때문에 현재까지 찾은 음수 사이클을 해소할 때까지 반복할 수 있는 최대 횟수 N번을 찾은 뒤 사이클을 한 번의 계산으로 해소시켜야 한다.
벨만 포드를 한 번 돌리고 정점 V개에는 사이클이 V개가 있을 수 있는데 그러한 사이클 하나마다 간선 E를 돌며 사이클 유무를 판별 후 정점 V개를 역추적해서 사이클 재구성 및 반복 가능 최대 횟수 탐색 및 사이클 해소를 하면 된다. O(VE + V^2(E+V)) = O(V^4).
TODO.

 

문제 4.

문제는 엘리스 토끼의 요금제(Billing Tables, https://www.acmicpc.net/problem/3605, 플3)이고 백준 문제와 동일하다.

트라이를 쓰면 된다.
Not TODO.