Semi-Game Cup 2 후기

Semi-Game Cup 2

 

특별상 정말 감사합니다!

 

 

A번 밖에 풀지 못해서 후기를 쓸 생각이 없었으나, 모종의 이유로 마음이 바뀌었다. ㅎ

 

개학이 다가와서 심란하던 차에 마음을 정화할 수 있게 해준 대회였다. 문제들이 재미있으니 업솔빙 해보는 것을 추천.

 

Prob. A

대충 수형도를 그려보니 겹치는 부분이 많아서 Kali가 이길 수 있는 경우가 한정될 것으로 추측했다. 그래서 뻔히 보이는 2만 예외로 두는 코드를 제출했고 맞았다. 아니, 맞았었다. 일단은 스코어보드 상에서 내가 퍼솔이어서 너무 기뻤고, 바로 다음 문제를 고민하러 떠났다. 그러다 한 20분쯤 지나서 스코어보드를 다시 봤더니 코드가 터져 있었고, 데이터가 약해서 재채점했다는 공지를 발견했다.

stonejjun님의 후기를 보면 "결국 굉장히 약한 랜덤 데이터와 함께 첫 솔브가 if(k==2) kali 가 되었다." 라는 문구가 있는데 이거 나다. ㅠ

솔직히 데이터가 어떻게 약해야 이 코드가 뚫리는지 이해가 안 가서 한참을 고민했다.... 예외가 6도 있다는 걸 금방 발견하긴 했는데, '설마 예외가 두 개 뿐인데 하나만 넣었겠어' 하는 생각에 제출하지는 않고 있었으나 그게 맞았다. ㅜㅜ

 

Prob. B

특별상을 받게 해준 문제다. 다양한 관찰을 했으나 답을 이끌어내기엔 무리였고, 출제자님께 죄송할 정도로 찍다시피 낸 코드가 틀렸다. 정말 풀이가 상상이 안 가는 문제.

 

Prob. C, D

C는 그냥 어려워 보여서 깊이 생각하지 않았다. D는 출제자가 빤히 보여서 고민하지 않았다.

 

Prob. E

naive DP를 짜서 돌려봤더니 1, 2, 6, 10만 예외로 나오길래 A번과 비슷한 문제라고 생각했다가 망했다. 후기글에 그런디 수가 언급된 걸 보니 그냥 DP를 잘못 짠 것 같다.

 

Prob. F

$2^{16}\times \frac{2}{3}$ 의 값이 $44,444$ 보다 조금 작다. $K$를 고정하고 나머지 세 수를 겹치지 않게 검사하려면 $\frac{N}{3}$ 정도의 쿼리가 필요하고, 각각의 쿼리마다 최대 한 번의 쿼리를 더 쓴다고 생각할 수 있다. 일반성을 잃지 않고 $K$의 고유 모양을 '묵'으로 고정하자. $K$를 1번 자리에 배치하는 것이 최적임은 자명하다. $K$는 '묵' 또는 '찌'를 내는 사람만 이길 수 있고, $K$가 우승하는 대진표를 짤 수 있는지를 판별하려면 '묵'과 '찌'를 내는 사람이 각각 몇 명인지를 알 필요가 있다. 참고로 $K$는 $N$번의 게임에서 승리해야 한다. '빠'는 '묵'을 이기고, '찌'는 '빠'를 이긴다. 이로 인해 '찌'를 내는 사람의 하위 대진표를 찌...찌빠...빠묵...묵"과 같은 형태로 구성한다면 '찌' 또는 '묵'이 항상 진출할 수 있다. 따라서 '찌'를 내는 사람이 $N$명 이상이라면 $K$는 항상 우승할 수 있다. '찌'를 내는 사람이 $N$명 미만이라고 가정하자. $K$는 '찌'를 내는 사람과 최대한 늦게 만나는 것이 최적이다. 왜냐하면 '묵'을 내는 사람의 하위 대진표는 모두 '묵'을 내는 사람이어야 하기 때문이다. 따라서 '묵'을 내는 사람을 $X$명, '찌'를 내는 사람을 $Y$명이라 하면 $X\geq 2^{N-Y}-1$를 만족해야 한다. 이제 '묵'을 내는 사람과 '찌'를 내는 사람이 각각 몇 명인지만 구한다면 $K$의 우승 여부 판별은 $O(1)$ 에 가능하다.

쿼리를 생각해보자. $K, a, b, c$ 를 물었을 때 나올 수 있는 대답은 14가지이고, 최대 한 번의 추가 질문으로 $a, b, c$ 가 각각 무엇을 내는지 결정할 수 있어야 한다. 여기서 13가지의 대답에 대해서는 Case-Work가 가능한데, 나머지 하나는 추가 질문을 뭘로 해도 결정할 수 없는 것 같아 그냥 포기했다. 내 풀이가 맞는지는 모르겠지만, 아마 $K, a, b, c$ 가 아닌 다른 질문을 한다면 쉽게 풀리지 않을까 추측해본다.

 

Prob. G, H, I

감이 안 온다.

 

Prob. J

충전 - 사용 - 충전 - 사용 - $\cdots$ 이 반복될 때 '사용'을 최대화하는 문제다. 먼저 시간 순으로 정렬해주고, 각 노트마다 어디서부터 충전해야 완충되는지, 여기까지 사용하려면 어디서부터 사용해야 되는지를 투포인터로 전처리할 수 있다. 남은 건 simple $O(N)$ DP. 인 줄 알았는데 11%에서 틀렸다. 이리저리 생각해봐도 딱히 잘못된 점을 찾을 수 없어서 포기했다.

 

 

Semi-Game Cup 1 을 업솔빙하며 '내가 참가했었다면 한 문제도 못 풀었을 것 같다'고 생각했는데 이번 대회도 역시 만만치 않았다. 그렇지만 지문도 재밌었고, 풀이를 찾아가는 과정도 상당히 흥미로워서 시간 가는 줄 모르고 대회를 즐길 수 있었다.