Codeforces Round #735 후기

+38 gg

 

난도는 A<D<B<C<E라는 것이 정설이다. B와 C는 정말 참신했다. 특히 n^k = x 와 n^x = k가 동치인 것이 매우 신기하다.

문제에 주어진 범위 자체가 힌트가 될 수도 있다.

 

굉장히 말려있다가 마지막에 @pentagon03이 D를 풀자고 북돋워 주어서 아이디어를 간신히 찾았다.

역시 god

 

유튜브 보다가 시작을 1분 늦게 했다;;

 

A. Cherry

 

3분컷!!

 

Sol)

lemma) 길이 n짜리 구간을 고르는 것이 최적이라고 해 보자. 구간 내 최댓값을 포함하는 모든 부분 구간들은 다 최적이다.

pf) 구간의 길이가 짧아지면 최솟값은 반드시 증가한다. 따라서 최적이다.

 

따라서 모든 경우에 대해 사실 길이 2짜리 구간만 봐도 충분하다. 시간복잡도는 $O(N)$ 이다.

 

D. Diane

Sol)

'연속한 문자열'에 집중하자. 알파벳이 N번 반복된 것을 Na와 같이 표시하자.

Na의 부분 문자열에는 Na가 하나, N-1a가 두개, N-2a가 세개, ..., a가 N개 있다.

짝수인 것을 없애주기 위해 '독립적인' N-1a 홀수개, N-3a 홀수개...가 필요하다.

 

놀랍게도 이는 N-1a 하나만 있으면 다 채워진다. 당연한 것이, 하나만 빼면 기우성이 다 반대가 된다.결론적으로, Na b N-1a와 같은 문자열은 독립된 Na와 N-1a가 존재하므로 Ka들의 개수는 다 짝수가 된다.또한, b가 포함된 부분문자열들은 자명하게 유일하다.

 

 

오랜만에 돌아서 긴장했는데 그래도 쉬운 관찰은 꽤 빨리 하는 것 같다. 

그러나 조금만 어려워지면 전혀 못 푸는 고질병은 여전하고 좀 진득하게 했으면 좋겠다.