제 2회 IDTcup 여담

https://www.acmicpc.net/contest/view/501

대회 시작 후 1670분 이후의 스코어보드를 보고 적는다.

풀이를 적은 건 아니지만 스포일러가 있을 수 있다.

출제자는 TAMREF.

 탐레프가 처음 말한 문제는 N!! = N(N - 2)(N - 4)...를 말하는 거였는데, 잘못 알아듣고 이런 문제가 되었다. 대충 K가 크면 답이 0이 되는 쉬운 문제가 될 예정이었는데, 12! = 479,001,600으로 잘 맞아떨어져서 제한을 5억으로 만들고 naive하게 계산할 수 없는 문제가 되었다. 문제에 써진 대로 N! mod P 복붙을 막기 위해 메모리 제한을 4MB로 할 까 했는데, 그냥 안 했다.

 문제 난이도는 골드로 생각했는데, 검수 때 쉽게 안 풀려서 대회 직전에는 플레로 생각하고 있었다.

 대회 시작하고 보니 실수하기 쉬운 문제더라. FFT 없이 한 번에 맞은 사람은 evenharder님 한 명 뿐이다. FFT 쓰고도 한 번에 맞은 사람은 별로 없다. 많이 나온 실수가 K가 5억 이하인 것을 간과하고 루프를 K번 돌리거나, (N! mod P) = ((N mod P)! mod P)라고 착각하는 경우였다.

 First solve는 koosaga이고, FFT 없는 First solve는 ahgus89이다.

출제자는 TAMREF.

 탐레프가 functional graph와 쿼리 얘기를 했고, 이 문제가 생겼다. 모 자료구조로 functional graph를 무한히 즐길 수 있다는 걸 알게 되어 어떤 구데기 쿼리를 줄 지 고민했는데, 그냥 합 구하기가 되었다. 사실 functional graph 님 게임? 같은 이상한 얘기를 많이 했지만 그냥 합이 제일 나은 것 같았다. 이 문제 검수를 위해 자료구조 빡공한 2명에게 애도.

 문제 난이도는 그냥 자료구조 연습문제 느낌이라 트리와 쿼리 11과 같은 다이아1로 예상했는데, 트리와 쿼리 11이 30명 푼 거 치고는 이 문제는 아직 2명밖에 안 풀려서 의외였다.

 대회에서는 루트 풀이가 몇 개 나온거 같은데, 뭐 하는 풀이인지는 모르겠다. 폴리곤에서 돌려보면 6초 안에 안 나온다. 탐레프가 마지막 날 추가한 데이터가 매우 강력했던 모양이다.

출제자는 imeimi2000.

 https://www.acmicpc.net/problem/15944 문제의 NM 풀이가 있는 것 같아서 만들었다. 근데 검수 할 때 다양한 풀이가 많이 나왔는데, 로그 붙여도 정해보다 빨라서 문제가 망했음을 느꼈다. 착한 칸의 비용을 각각 다르게 하면 해결될 거 같았는데, 지문이랑 입력 형식을 뜯어고쳐야 해서 그냥 포기했다.

 문제 난이도는 정해는 아무도 상상을 못하는거 보면 어려운거 같은데, 어차피 펑펑 뚫릴 예정이라 플레일 것 같다.

 대회에서는 예상대로 알 수 없는 풀이만 많이 나왔다. 봐도 몰라서 패스.

출제자는 TAMREF.

 쉬운 문제가 필요할 것 같아서 고민하던 중에 탐레프가 트리의 K번째 지름 얘기를 해서 만들어졌다. 처음에는 쿼리가 없었고, 경로의 사전순 K번째를 시킬지 양 끝 점 페어의 사전순 K번째를 시킬지 고민했는데, 어차피 둘이 별로 차이가 없을 것 같았다. 그러다 '이거 쿼리 됨?'이라는 말이 나오고 망했다. 쿼리가 있을 때 경로 사전순을 주면 BBST가 필수가 되는 것 같아서 양 끝 점만 주는 걸로 했다. 로그 풀이는 두 세그트리를 같이 내려가며 이분탐색하는 부분이 나름 생각하기 어려울 수도 있는데, 로그제곱은 그냥 재미없는 구현이다. 로그제곱이 빨라서 막을 수는 없었다.

 문제 난이도는 구현 몰빵. 특히 로그제곱 생각하기는 쉽다고 생각했다.

 대회 중에는 로그 풀이도 나오고 로그제곱 풀이도 나왔다.

출제자는 messi.

 메시가 처음 들고 온 문제는 골드 난이도의 쉬운 문제였는데, 그 문제가 이상하게 바뀌면서 이런 문제가 되었다. 원래 문제랑 공통점이 2가지 색의 격자판이라는 것 빼고는 없다. 처음에는 K가 홀수였다가 K가 짝수일 때도 별거 없다는 사실이 밝혀지며 조건이 사라졌다. 제한이 굉장히 널널한데, 이유는 출제자의 귀찮음으로 예상된다. 출제자가 대회 이틀 전까지 naive 코드 빼고 하나도 안 짰다는 소문이 있다.

 문제 자체는 구현 올인 셋에 그나마 지능이 필요한 문제인 것 같다.

 대회 중에는 현재 3번째로 많이 풀린 문제이다.

출제자는 imeimi2000.

 트리인 경우에는 조금 알려진 문제이다. 선인장인 경우에도 비슷하게 풀 수 있는데, 구현이 매우 길다. 올솔이 5명씩 나오는 건 막고 싶어서 만들었다. 2~3명 정도 풀거라고 생각하고 냈다.

 대회 중에는 현재 1명 풀었다.

출제자는 imeimi2000.

쿼리 종류를 바꾸는 쿼리라는 문제를 내고 싶어서 만들었다. 어려운 문제는 아니지만, Lazy PST라는 이름이 꽤나 위압감이 있는 것 같다. 안 그래도 PST 4개씩 들고 다니는데 구간 업데이트까지 있어서 메모리를 많이 먹는다. 정말 대충 짜면 1024MB를 넘기는 모습을 볼 수 있다. PST를 포인터로 만들고 전부 long long을 쓰고 정말 최악의 코드를 짰더니 1100MB를 먹었다. 가비지 컬렉션을 잘 쓰면 선형 메모리로 해결할 수 있는데, 굳이 그럴 필요는 없다. 검수 중 짠 스마트 포인터 코드는 40MB정도 먹었다.

 사실 PST 없이 일반 Lazy 세그트리로 해결할 수도 있는데, 안 짜봤다.

 대회 중에는 현재 3번째로 적게 풀렸다.

출제자는 imeimi2000.

 문제 이름은 https://www.acmicpc.net/problem/16133 패러디. 의도한 건 아닌데 기말고사인 것까지 똑같다. 이 문제의 핵심 두 가지는 두 문자열의 차이를 하나의 수로 나타내고, 이 수가 0이면 1, 아니면 0을 반환하는 함수를 만드는 것이다. 두 문자열을 차이를 하나의 수로 나타내는 것은 그냥 해싱을 하면 된다. 해싱 하라고 문제에 채점이 적응적이지 않다고도 적어주었다. 사실 이 문제를 낸 이유는 해싱 말고 결정론적 풀이가 있기 때문인데, 아무도 안 짤 것 같았지만 짠 사람이 있어서 신기했다. 0이면 1, 아니면 0을 반환하는 함수도 결정론적인 방법이 있고 아닌 방법이 있는데, 다양한 방법들이 나왔다.

 문제 난이도는 이 셋에서 가장 쉽다고 생각했다. 물론 디버깅이 힘들긴 하다.

출제자는 Diuven.

 문제 이름은 무섭게 생겼다. 2배 연산이 없을 경우에는 기저 가지고 노는 유명한 문제고, $O(n\log A+q\log^2A)$에 풀린다. 그렇다고 기저 가지고 이 문제 접근하면 망하기 쉽다. 이 문제에서 재미있는 것은 f 함수가 gcd같은 성질을 가진다는 것이다. 이게 gcd같다는 걸 안다면 풀 방법은 많다.

 이 문제는 이 대회에서 가장 데이터가 대충인데 그럼에도 불구하고 뚫을 방법은 잘 모르겠다.

 대회 중에는 은근 A가 짝수인 경우를 간과하는 경우가 많았다. 뚫으려는 시도는 없는 것 같아 다행이다.