콘테스트 기록

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

A	B	C	D	E	F
00:02	00:07	00:43	0

1697A Parkway Walk

적어도 의 에너지^energy가 필요하고, 적어도 만큼의 회복이 필요하다. 회복이 필요한 만큼 언제든지 회복할 수 있으므로 답은 이다.

1697B Promo

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

1697C awoo’s Favorite Problem

문자열 , 에 대해 로 이루어진 부분 문자열을 각각 라고 하자. 가 주어진 조작을 통해 로 변할 수 있는 것은 다음 세 조건 모두를 만족하는 것과 동치이다.

2. 는 ab를 ba로 바꾸는 조작을 통해 로 변할 수 있다.
3. 는 bc를 cb로 바꾸는 조작을 통해 로 변할 수 있다.

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

1697D Guess The String

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

복원하려는 문자열을 라고 하자. 는 문자 로 이루어져 있고, 유형 1 쿼리를 사용하여 이 문자를 라틴 소문자에 대응시킬 것이다. 의 첫번째 문자가 이라고 하자. 이라고 하자. 의 처음부터 번째 문자가 종류라고 하자. 의 결과를 라고 하면, 이다.

1. 인 경우, 의 번째 문자는 이전에 등장하지 않은 문자인 이다.
2. 인 경우, 의 번째 문자는 이전에 등장한 문자인 중 하나이다. 각 문자에 대해, 그 문자가 가장 마지막으로 등장한 위치를 기억한다. 위치를 정렬하였을 때 번째 위치를 각각 라고 하고, 그 위치에 대응하는 문자를 라고 하자. 의 결과가 인 중 가장 큰 것을 라고 하면, 의 번째 문자는 이다. 이러한 는 이분탐색을 통해 최대 다섯 번의 쿼리를 사용하여 찾을 수 있다.

각 상황에 대해 유형 2 쿼리를 많아야 번 사용한다.

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