콘테스트 기록

A, B, C를 풀었다. D는 대회 이후 풀이를 보고 풀었다. E, F는 어려워 보인다.

1697A Parkway Walk

적어도 $S = \sum_{i = 1}^n a_i$의 에너지^energy가 필요하고, 적어도 $\max \{0, S - m\}$만큼의 회복이 필요하다. 회복이 필요한 만큼 언제든지 회복할 수 있으므로 답은 $\max \{0, S - m\}$이다.

1697B Promo

가장 비싼 물건 $x$개를 샀을 때 그 중 가장 싼 물건 $y$개의 가격이 최대이다. $p$를 정렬하고 부분 합 배열을 만들어 쿼리 여러 개를 처리할 수 있다.

1697C awoo's Favorite Problem

문자열 $x = s$, $x = t$에 대해 $\{a, b\}, \{a, c\}, \{b, c\}$로 이루어진 부분 문자열을 각각 $x_{ab}, x_{ac}, x_{bc}$라고 하자. $s$가 주어진 조작을 통해 $t$로 변할 수 있는 것은 다음 세 조건 모두를 만족하는 것과 동치이다.

1. $s_{ac} = t_{ac}$
2. $s_{ab}$는 ab를 ba로 바꾸는 조작을 통해 $t_{ab}$로 변할 수 있다.
3. $s_{bc}$는 bc를 cb로 바꾸는 조작을 통해 $t_{bc}$로 변할 수 있다.

2, 3번 조건은 각 문자열을 처음부터 $i$번째 자리까지 등장하는 $a, c$의 개수를 각각 세고 이들을 각 $i$마다 비교하는 방식으로 확인할 수 있다.

1697D Guess The String

유형 2 쿼리만을 사용해서 문자열의 모양을 결정할 수 있다. 모양을 결정한 후 유형 1 쿼리를 통해 각 문자를 복원할 수 있다.

복원하려는 문자열을 $s$라고 하자. $s$는 문자 $0, 1, \cdots, 25$로 이루어져 있고, 유형 1 쿼리를 사용하여 이 문자를 라틴 소문자에 대응시킬 것이다. $s$의 첫번째 문자가 $0$이라고 하자. $2 \le i \le n$이라고 하자. $s$의 처음부터 $i - 1$번째 문자가 $c$종류라고 하자. $2 1 i$의 결과를 $k$라고 하면, $k \in \{c, c + 1\}$이다.

1. $k = c + 1$인 경우, $s$의 $i$번째 문자는 이전에 등장하지 않은 문자인 $c$이다.
2. $k = c$인 경우, $s$의 $i$번째 문자는 이전에 등장한 문자인 $0, 1, \cdots, c - 1$ 중 하나이다. 각 문자에 대해, 그 문자가 가장 마지막으로 등장한 위치를 기억한다. 위치를 정렬하였을 때 $j = 0, 1, \cdots, c - 1$번째 위치를 각각 $p_j$라고 하고, 그 위치에 대응하는 문자를 $c_j$라고 하자. $2 p_j i$의 결과가 $c - j$인 $j$ 중 가장 큰 것을 $j_0$라고 하면, $s$의 $i$번째 문자는 $c_{j_0}$이다. 이러한 $j_0$는 이분탐색을 통해 최대 다섯 번의 쿼리를 사용하여 찾을 수 있다.

각 상황에 대해 유형 2 쿼리를 많아야 $999 \cdot (1 + 5) < 6000$번 사용한다.

유형 1 쿼리를 이용하여 $0, 1, \cdots, 25$에 대응하는 라틴 소문자를 얻는다. 많아야 $26$번 사용한다.