[Codeforces] Educational Round #93

문제 바로가기 : https://codeforces.com/contest/1398
문제 설명은 위 링크에서 확인해주시길 바랍니다.

A solution

non-degenerate triangle 가 대체 뭐지? 제시문을 읽어도 무슨 말인지 잘 모르겠네.. 하면서 당황했었다.
다행스럽게도 검색이 허용돼서 뭘 말하는건지 찾아보니 변 a, b, c가 있을 때 a+b>c를 만족하는 삼각형이었다.
뭔가 둔각, 예각삼각형 조건이랑 닮았다.

impossible to construct a non-degenerate triangle 이니까 a+b<=c를 만족하는 경우를 찾아보면 된다.
물론 안되는걸 다 찾아봐도 되겠지만, array a가 오름차순으로 주어지기 때문에 제일 작은거 2개랑 큰 것만 비교하면 된다.
얘네가 만족못하면 다른 것들도 다 만족을 못한다. 뭔가 A번 답다.
그리고 등호 안써서 패널티 먹었다. 역시 내 실력 답다!

B solution

그냥 간단한 그리디 문제다. 구현을 어떻게 할지 좋은 방법을 모르겠어서 제시문을 따라갔다.
Alice의 점수를 출력해야 하니 turn이 true일 때마다 갱신되도록 했고 처리된 문자열은 erase로 지워줬다.

C solution

Prefix sum 문제다. 알고보니 Atcoder, Codeforces에서 자주 나오는 유형이라고 하더라.
그치만 나는 모르기도 했고.. 결국 제출하지 못했다ㅜㅜ
공부하는 차원에서 찾아보고 이해하는데 시간이 좀 많이 걸렸다. 그래도 내용은 생각보다 간단하다!


구하려고 하는 구간을 [l, r]이라고 하면 구간합과 길이가 같은 구간의 개수를 세는 문제다.
조건을 가지고 이항을 하면 위와 같은 식을 얻을 수 있다. 일단 합을 이용해야 하니 각 인덱스까지 부분합을 만들어주자.

pre[0] = 0;
for (int i = 0; i < n; i++) {
	pre[i+1] += pre[i] + (s[i] - '0');
}

여기가 중요한데, 아까 얻었던 식을 보자. 저 식을 이용해야하는데 양변이 한 변수로 이루어져 있다.
저 식이 성립하는 구간을 모두 일일이 탐색하면 O(n^2)가 걸린다! 시간 초과에 걸리기 좋다.
그래서 이걸 더 빠르게 체크하기 위해서 미리 구해놓은 부분합을 이용할거고 O(n)만에 답을 구할 수 있다.
map에 left 변수가 포함된 식을 먼저 표시해놓고 그 다음 right이 포함된 식을 체크해가며 답을 갱신한다.

for (int i = 1; i <= n; i++) {
	key[pre[i-1] - i]++;
	res += key[pre[i] - i - 1];
}

D solution

red, blue, green 색상의 막대기 쌍들이 존재하며 각 길이가 주어진다.
색이 다른 쌍을 선택해 직사각형을 만든다. 최대한의 넓이를 얻을 수 있도록 해보자. 같은 쌍은 선택할 수 없다.

처음에 그리디로 시작했는데 그리디로는 풀 수 없다는걸 알고 멘붕이 왔다. DP로 풀 수 있는 문제다.
입력받은 각 색상의 길이들을 정렬한 후 모든 경우의 수를 돌면서 dp를 갱신하고 최종적으로 얻은 dp[r][g][b]를 출력한다.