콘테스트 기록

A, B를 어렵지 않게 풀었고 C는 아이디어를 생각해내는데 시간을 좀 썼다. D, E, F는 무진장 어려웠다. A는 00:04, B는 00:11, C는 00:35에 풀었다. D, E, F는 풀지 못했다.

1550A Find The Array

길이 인 수열로 최대 까지 만들 수 있다. 길이 인 수열의 합이 일 때, 가장 큰 항의 값을 1 줄임으로써 길이 이고 합이 인 수열을 만들 수 있다. 가 원하는 답이 된다.

1550B Maximum Cost Deletion

연속하는 문자열을 지운 횟수를 라고 할 때, 전체 점수는 이다. 연속하는 조각의 개수가 일 때, 이는 최소 번 지워야 하고, 최대 번까지 지울 수 있다. 이 원하는 답이 된다.

1550C Manhattan Subarrays

인 경우, 는 와 사이에 있다. 를 가정하면, 이다. 또한 는 사이에 있고, 는 단조증가 혹은 단조감소이다.

Erdős-Szekeres 정리에 의해 길이가 5인 수열은 항상 길이 3인 단조증가하는 부분수열 또는 길이 3인 단조감소하는 부분수열을 포함하고, 따라서 이는 항상 나쁜 수열이다. 각 에 대해 의 좋은 부분 수열의 개수를 찾아서 더하면 원하는 답이 된다.