콘테스트 시작 전

오랜만에 참가하는 Codeforces 콘테스트이다. 근 3년간 경쟁 프로그래밍을 했다가 쉬었다가를 반복하는 것 같다.

콘테스트 기록

A, C를 콘테스트 중 풀었다. D, E, F는 포기했다. B를 못 풀었는데, 끝나고 난 후 값 초기화에서 실수했다는 것을 찾아냈다.

A	B	C	D	E	F
00:05	0	01:08

2042A Greedy Monocarp

동전이 많은 상자부터 동전의 개수를 합하였을 때 보다 작거나 같은 것 중 가장 큰 값을 라고 하면, 답은 가 된다.

2042B Game with Colored Marbles

색 에 대해,

• 구슬이 한 개 있다면, Alice는 이것을 가져갔을 때 2점을 얻는다.
• 구슬이 두 개 이상 있다면, Alice는 이 색의 구슬을 한 개 이상 가져가지만 모두 가질 수는 없다. 구슬이 한 개 있는 색 의 개수의 홀짝성을 고려한다.

2042C Competitive Fishing

에 대해, 각 물고기를 으로 나누었다고 하자. 번째 물고기를 Bob이 잡았다면 , Alice가 잡았다면 이라고 하자. 라고 하자. 점수의 차를 다음과 같이 표현할 수 있다.

각 에 대해, 마지막 항 은 각 를 가장 작은 것부터 선택했을 때 최소가 된다. 점화식 을 사용하여 각 를 계산하고 정렬하면 각 에 대해 점수 차의 최댓값을 계산할 수 있다.