[2020-09-10] Codeforces Round 534 (Div.1)

오늘은 그래도 나쁘지 않았다. 일단 두 문제 다 한 번에 맞았다는 게 다행. 업솔빙 무조건 하나는 하고 넘어가고 싶었는데, C번은 에디토리얼을 봐도 뭔 소린지 이해도 안 되고, 증명이 제일 중요한 파트인데 이거 대충 읽고 구현한다고 해서 뭐 실력에 도움이 될 것 같지도 않아서 패스.

 

A. Grid game

지워지는 규칙이 단순해서, 그냥 1번 줄에는 1x2, 3번줄에는 2x1을 순서대로 배치하는 걸 반복하면 된다. 한 줄 지워지면 다시 맨 처음으로 돌아가서 배치하는 식. 이렇게 하면 어차피 양쪽 배치의 동작이 독립적이고 무조건 첫줄은 4개 채울 때마다 삭제, 세번째줄은 2개 채울 때마다 삭제 반복이기 때문에 간단하게 풀린다.

 

B. Game with modulo

좀 더 풀이를 빨리 생각할 법도 했는데, 자세하게 케이스 분류를 안 하고 머릿속으로만 고민하다 시간을 많이 날렸다. 이런 경험이 좀 많은데, 뭔가 생각난 방법이 있으면 그걸 한 번은 좀 자세히 파고 들어보는게 좋을 것 같다. 이런거 식 정리에서 시간이 오래 걸리다보니 생각한 걸 구체화하는 시도를 하는거에 주저하는 습관이 있는데, 이 때문에 올바른 방향을 떠올리고도 그걸 제대로 검증 안해서 시간 낭비를 많이 하는 듯.

 

우선, (0, 1), (1, 2), (2, 4), (4, 8), ... pair들에 대해 쿼리를 해보자. 각 쿼리를 할 때마다 y가 나오면 a가 가질 수 있는 값의 하한을 높일 수 있다. 예를 들어 (0, 1), (1, 2), (2, 4)에 대해 전부 y가 나왔다면 a는 5 이상이어야 한다. 반대로, x가 나오면 a의 상하한이 전부 결정된다. 예를 들어 (4, 8) 쿼리를 했을 때 x가 나왔으면 a는 5이상 8 이하이다.

 

a의 상한과 하한이 결정되면 여기서부터는 binary search를 할 수 있다. 하한이 항상 홀수고 상한이 항상 짝수라고 가정하자. 중간 지점 mid를 잡고 (하한 -1, mid) 쿼리를 했을 때 x가 나오면 상한을 mid로, y가 나오면 하한을 mid + 1로 바꿔주는 걸 상한값과 하한값이 같아질 때까지 반복한다. 이렇게 하면 이분탐색에서 최대 30번 정도의 쿼리, 처음 상하한 정하는 것에서 최대 30번 정도의 쿼리가 각각 필요하므로 문제에 주어진 제한인 60번 이내에 해결할 수 있다.

 

 분명히 2^n, 2^(n+1)에 대해 쿼리를 하는 생각을 꽤 빨리 떠올렸는데, 이걸 (0, 1), (1, 2), ... 페어 순서대로 실행했을 때 어떤 결과가 되는지 검사하는 걸 너무 늦게 해서 시간이 오래 걸렸다. 발상을 하고 구현을 좀 일찍 했으면 두 배쯤 일찍 풀었을 것 같은데. 이게 아쉽다.