AtCoder Regular Contest 112

AtCoder Regular Contest 112

AtCoder Regular Contest 112

 

AtCoder Regular Contest 112에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다.

 

atcoder.jp/contests/arc112

AtCoder Regular Contest 112 - AtCoder

 

[2021.02.14] 초판 발행

 

 ARC112에 대한 해설입니다. 제가 해결한 두 문제에 대한 해설을 올립니다.

 

[A번] A - B = C

 

[문제 및 풀이]

 

 $A-B=C$를 만족하면서, $ \{ A, B, C \} \subset [L,R]$를 만족하는 순서쌍 $(A,B,C)$의 개수를 구하는 문제이다.

 

 먼저, $C$가 될 수 있는 값은 $L+L=2L, 2L+1, \cdots ,R$이다. 그리고 $C=2L$인 경우는 $(A,B)=(L,L)$로 유일하다. $C$를 늘려가면서 가능한 $(A,B)$의 순서쌍을 나열해보자.

 

 1. $C=2L$인 경우, $(L,L)$

 2. $C=2L+1$인 경우, $(L,L+1), (L+1,L)$

 3. $C=2L+2$인 경우, $(L,L+2), (L+1,L+1), (L+2,L)$

 

 일반적으로, $C=2L+k$인 경우에 $(L,L+k), (L+1,L+k-1,), \cdots, (L+k,L)$로 $k+1$개의 순서쌍이 만들어지는 것을 알 수 있다. 그리고 여기서 $C \leq R$이기 때문에, $2L+k \leq R$에서 $k \leq R- 2L$임을 알 수 있다.

 

 $k = R-2L$일 때, $R-2L+1$의 순서쌍이 만들어지기 때문에, $1, 2, \cdots, (R-2L+1)$을 합한 값이 정답이 된다. 

 (정의에 따라 알 수 있는 사항이지만, $R-2L+1$이 $0$이하면 가능한 순서쌍이 존재하지 않는다.)

 

[구현]

 

 풀이에 따른 값을 잘 구현하면 된다. 다만, 결과값이 64 bit 정수형 범위라는 점과, $(R-2L+1)$이 음수가 되는 경우에 대한 예외 처리를 해야된다는 점을 유의해야 한다.

 

[예시 답안]

 

#include <stdio.h>
 
long long T, L, R, a;
 
int main() {
    scanf("%d", &T);
 
    while (T--) {
        scanf("%d%d", &L, &R);
        a = R - 2 * L + 1;
        printf("%lld\n", (a > 0) ? a * (a + 1) / 2 : 0);
    }
 
    return 0;
}
 

 

[B번] -- - B

 

[문제 및 풀이]

 

 정수 $A$과 이용할 수 있는 비용 $B$가 주어진다. 이용할 수 있는 비용의 범위 안에서 다음 두 동작을 통해서 만들 수 있는 정수의 종류를 구하는 문제이다.

 

 1. $1$의 비용을 이용해서 주어진 값에 $-1$을 곱한다.

 2. $2$의 비용을 이용해서 주어진 값에 $1$을 뺀다.

 

 이 문제는 이용할 수 있는 비용이 $B$이고 시작값이 $0$인 경우와 그 이외의 경우로 나누어서 생각하면 쉽다.

 

 1) 시작값이 $0$인 경우 : 가능한 정수의 종류는 $B$이다.

 

 (증명)

 

 $B=1$이면, 새로운 정수를 만들 수가 없다. $1$의 비용을 이용해서 $-1$을 곱해도 $0$만 만들어지기 때문이다.

 $n( \{ 0 \} ) = 1$

 

 $B=2$이면, $2$의 비용을 이용해서 $1$을 빼서 $-1$을 만들 수 있다.

 $n( \{ 0,-1 \} ) = 2$

 

 $B=3$이면, $2$의 비용을 이용해서 $1$을 빼서 $-1$을 만들고, 여기에 $1$의 비용을 이용해서 $-1$을 곱해서 $1$을 만들 수 있다.

 $n( \{ 0,-1,1 \} ) = 3$

 

 이 과정을 아래와 같은 아이디어로 일반화시킬 수 있다.

 

일반화 과정을 설명한 그림이다. 큰 숫자는 만들고자 하는 숫자이고, 간선은 만드는 방법을 나타낸 것이다. 간선에 표시된 작은 숫자는 그 만드는 방법에 드는 비용이다. 노란 사각형에 적힌 수는 그 수를 만드는 데에 드는 최소 비용이다.

 

 이 아이디어를 바탕으로 $B=2k-1$의 비용을 이용해서, $ \{ 0, \pm 1, \pm 2, \cdots, \pm (k-1) \} $를 만들어서 $2k-1$개의 정수를 만들었다고 하자. 이 때, $B=2k$과 $B=2k+1$인 경우 각각에 대해서도 $2k$개와 $2k+1$개의 정수를 만들 수 있음을 보이면 된다.

 

 $B=2k$이면, $2k-2$의 비용을 이용해서 $-(k-1)$를 만들었기 때문에, 여기에 $2$의 비용을 이용해서 $-k$를 만들 수 있다.

$n( \{  0, \pm \pm 1, \pm 2, \cdots, \pm (k-1), -k \} ) = 2k$

 

 $B=2k+1$이면, $2k$의 비용을 이용해서 $-k$를 만들었기 때문에, 여기에 $1$의 비용을 이용해서 $k$를 만들 수 있다.

$n( \{  0, \pm \pm 1, \pm 2, \cdots, \pm (k-1), \pm k \} ) = 2k+1$

 

 수학적 귀납법에 의해서 임의의 $B$에 대해서 성립한다. 이 문제에서는 $B=0$인 경우는 주어지지 안았지만, 만약 $B=0$인 경우가 들어오면 이에 대한 예외처리($B=0$인 경우는 $1$)를 해야 한다. (*1)

 

2) 시작값이 $0$이 아닌 경우

 

 (a) 이 문제를 세는 과정은 크게 절댓값에 따라 두 개로 나누어서 푸는 것이 좋다. 1)에서 한 것과 마찬가지로 기본적으로 $-1$을 곱하는 작업과 $1$을 빼는 작업을 반복하는 것을 통해 수를 만들 수 있다. 다만, 조금 더 쉽게 세기 위해서, 아래와 같이 절댓값이 $a$이상인 경우와 $a$미만인 경우로 나누어서 생각해보자.

 

 만약 절댓값이 $a$이상인 경우는 $-a$을 1)과 마찬가지 방법으로 만들 수 있다. $-a$에서 $1$의 비용을 곱해서 $a$를 만들고, $2$의 비용을 곱해서 $-(a+1)$을 만들 수 있다. 이런 식으로 만들면 1)과 마찬가지로 비용이 $B$라면 $B$개의 정수를 만들 수 있다.

 

 절댓값이 $a$미만인 경우에도 비슷한 방식으로 수를 만들 수 있지만 한계가 있다. 즉, $0$이 된 이후에는 그 이후로 만들어진 수는 중복된 수만 만들어지기 때문에 더 이상 새로운 수가 만들어질 수 없다. 이 경우는 $(a-1) \times 2 + 1 = 2a-1$개만 만들 수 있다. 일종의 상한을 지정할 필요가 있다.

 

절댓값에 따라 범위를 나누어서 생각할 수 있다.

 

 설명을 하는 과정에서 편의상 절댓값이 $a$이상인 경우와 $a$미만인 경우로 나누었지만, 이것은 구현 과정에서 편하게 생각하면 된다. 다만, 중요한 것은 확산하는 방향으로는 무한히 수를 만들 수 있지만, 수렴하는 방향으로는 유하난 수만 만들 수 있다는 개념을 유념하면 된다.

 

 (b) 시작값의 부호에 대해서는 대칭이다. 함수 $f$가 $a<0$이면, $f(a,b)=b$이고, 그 이외의 경우는 $f(a,b)= \min ( b, 2a ) $로 정의했다고 하자. 그러면 시작값이 $A$이고 이용할 수 있는 비용이 $B$인 문제의 정답은 다음과 같다.

 

$f(A,B) + f(-A,B-1)$

 

 시작값의 부호와 상관 없이 $1$의 비용을 이용해서 $-A$를 만든다고 생각한다면 위의 식을 이용하면 된다. 즉, 부호에 대해서 일종의 대칭을 갖는 문제이다.

 

 (c) 작은 값에 대한 예외처리에 대해서 유념해야 한다. 1)에서 (*1)의 내용은 이 경우에서는 구현에 반영해야 한다. 즉, 이용할 수 있는 비용이 $1$이면 

 

[구현]

 

 풀이에서 설명한 바를 적절히 구현하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
long long A, B, Ans;
 
long long f(long long a, long long b) {
    if (a < 0) return b;
    return (b < 2 * a) ? b : 2 * a;
}
 
int main() {
    scanf("%lld%lld", &A, &B);
 
    if (A == 0) Ans = B;
 
    else {
        if (B == 1) Ans = 2;
        else Ans = f(A, B) + f(-A, B - 1);
    }
 
    printf("%lld", Ans);
 
    return 0;
}
 

 

[C번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[D번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[E번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]