콘테스트 기록

A, B, C를 풀었다. D는 풀지 못했다. E는 어려워 보인다.

1695A Subrectangle Guess

Michael은 갖고 있는 정보가 $a_{ij}$ 뿐이므로 이를 통해 얻어낼 수 있는 답은 $a_{ij}$ 중 가장 큰 값 $M$이고, 어떤 부분 직사각형을 설정하여도 그 안에 $M$이 들어가도록 $h, w$를 크게 설정하면 된다.

1697B Circle Game

$n$이 홀수이면 Mike가 첫번째 무더기의 돌을 모두 제거하였을 때 Joe가 패배한다.

$n$은 짝수라고 하자. Mike는 $1, 3, \cdots, n - 1$번째, Joe는 $2, 4, \cdots, n$번째 무더기의 돌만을 제거할 수 있다. 각자의 최선의 수는 각 무더기에서 돌을 한 차례에 하나씩만 제거하는 것이다. Mike와 Joe 중 돌무더기에 있는 돌의 수의 최솟값이 더 많은 쪽은 항상 이긴다. 값이 같다면, 빈 무더기를 더 늦게 만나는 쪽이 이긴다.

1697C Zero Path

1이 $\frac{n + m + 1}{2}$번 등장하는 경로를 찾을 것이다. 임의의 두 경로에 대해 ㄱ자 경로와 ㄴ자 경로 사이의 변환들을 여러 번 적용하여 하나에서 다른 하나를 만들 수 있다. 이 변형에서 1의 등장 횟수는 많아야 1만큼 변한다. 1이 가장 많이 등장하는 경로와 1이 가장 적게 등장하는 경로에서 1의 개수를 각각 $x_M, x_m$이라고 하자. $\frac{n + m + 1}{2} \in [x_m, x_M] \cap \mathbb{Z}$와 경로의 칸에 든 수의 합이 0인 경로가 존재하는 것은 동치이다.