Educational Codeforces Round 114 (Rated for Div. 2)-B. Combinatorics Homework

문제 설명

당신에게 4개 정수 $a$, $b$, $c$ 와 $m$가 주어진다.
다음 조건을 만족하는 문자열이 존재하는지 확인하는것이 문제이다.

• $a$개의 'A'문자
• $b$개의 'B'문자
• $c$개의 'C'문자
• 다른 문자는 없다.
• 정확히 인접한 문자가 같은쌍이 $m$개 있어야한다. ($i$번째 문자열과 $(i+1)$번째 문자열이 같은 쌍이 정확히 $m$개가 있어야한다.)

Input
첫번째 줄에는 테스트 케이스의 개수 $t$가 주어진다. $(1 \le t \le 10^4)$
다음 t개의 줄에는 각 4개의 정수 $a, b, c$와 $m$이 주어진다. $(1 \le a, b, c \le 10^8, 0 \le m \le 10^8)$

Output
각 테스트케이스마다 위에서 말한 모든 조건이 만족하는 문자열이 존재하면 "YES"를, 그런 문자열이 없으면 "NO"를 출력한다.
출력할때 모든 단어는 소문자, 대문자 모두 상관 없다. EX) yEs, yes, Yes, YES 모두 가능하다.

Example
input
3
2 2 1 0
1 1 1 1
1 2 3 2

output
YES
NO
YES

문제 접근

사용한 알고리즘: 조합론
걸린 시간 : 00:13
못풀었다. 코드포스에서는 거의 대부분 B번 유형에서 경우의 수를 나누는 수학 문제나 조합론을 주로 출제하는것 같은데 이쪽 부분에 익숙해지도록 많은 반복이 필요할 것 같다. 먼저 이해하기 쉬운 부분부터 보자.
testcase 2 2 1 0의 경우 어떤 문자열이 해당할까? 'A'문자가 2개, 'B'문자가 2개, 'C'문자가 1개 필요하고 이 문자로 만들 수 있는 문자열은 0개의 인접한 문자 쌍을 가져야한다. ABABC가 가능할 것이다. 왜냐하면 'A'문자가 2개, 'B'문자가 2개, 'C'문자가 1개 사용했고, 문자열에서 인접한 4쌍의 두 문자가 같지 않기 때문이다. (AB, BA, AB, BC) 이 예시를 보면 이 문제에서 목표로 하는것이 무엇인지 이해할 수 있을거라 믿는다.
그렇다면 이 테스트케이스에서 최대로 만들 수 있는 m의 값은 몇개일까? 답은 2이다. 왜냐하면 AABBC의 경우 인접한 두 문자가 같은 2쌍의 문자가 있기 때문이다. (AA, BB) 이 경우를 일반화하면 'A'문자가 a개, 'B'문자가 b개, 'C'문자가 c개 사용할때 만들 수 있는 최대 m값은 a + b + c - 3 일것 이다. 문자열 aa...aabb...bbcc....cc가 답이 될 것이다. 'A'문자가 a개 연속으로 붙어있으면 a-1쌍의 "aa"문자열이 만들어지기 때문이다.
이번에는 testcase 1 2 3 2에서 가장 m값을 작게 만들어 보자. 위에서 말한 예시를 이해했으면 대충 어떻게 할지 감이라도 올 것이다. 뭔가 가장 많은 문자에 나머지 문자를 끼워넣으면 되지 않을까? 1 2 3중에서 제일 값이 큰 3을 기준으로 먼저 문자열을 배치하면 ^c^c^c^이다. 이때 ^은 공백을 의미한다. 이 공백 4개에 'A' 1개와 'B' 2개를 끼워 넣으면 인접한 문자쌍이 같은 경우를 최소화 할 수 있을 것 같다. ACBCBC, CBCACB같은 경우 m이 0이기 때문에 최소의 경우가 될 것이다. 그렇다면 사이 빈칸이 2개인데, 사용해야하는 문자열이 2개보다 많은 경우는 어떻게 할까? 그것은 문제가 안된다. 왜냐하면 남은 문자가 2개밖에 안남았기 때문에 두 문자를 번갈아가면서 문자열을 만들면 인접한 문자가 같지 않게 만들 수 있다.
위에서 말한 설명을 일반화해보자 a, b, c (a $\le$ b $\le$ c) 일때, c를 나열했을때 나오는 사이 빈칸의 개수는 c - 1개이다. 이 빈칸에 나머지 문자열을 넣으면 되기 때문에 최소값은 c - 1 - a - b이다. testcase 1 2 3 2의 경우 3 - 1 - 1 - 2이므로 최소의 개수는 0이다. (음수의 경우는 말이 안되므로 0으로 취급하자)
c - 1 - a - b가 보기 안좋기 때문에 c - (a + b + 1)로 바꾸자. 그렇다면 testcase가 a b c (a $\le$ b $\le$ c) 일때 나올 수 있는 m의 값은
c - (a + b + 1) $\le$ m $\le$ a + b + c - 3 이다. 그리고 m값이 이 부등식을 만족하면 조건에 만족하는 문자열이 존재하기 때문에 YES를 출력하면 된다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int t; cin >> t;
    while(t--){
        int arr[3];
        for(int i = 0; i < 3; i++) cin >> arr[i];
        int m; cin >> m;
        sort(arr, arr + 3);
        cout << ((arr[2] - (arr[0] + arr[1] + 1) <= m && m <= (arr[0] + arr[1] + arr[2] - 3)) ? "YES" : "NO") << "\n";;
    }
}