Codeforces Round #804 (Div. 2) ABC

[12번째 Contest]

방학 안에 100개의 콘테스트에 참가할 수 있을까..?

대회 준비로 코포에 집중을 못하고 있다. 이전에 1일 1버추얼 돌리다가 그린까지 떨어지는 대참사를 겪었기에 버추얼을 함부로 못하겠다..

오늘 코포는 AB가 굉장히 쉬웠는데, C가 C답지 않게 어려웠다.

A. The Third Three Number Problem

$n$이 주어진다. 우리는 다음 수식을 만족하는 $a, b, c$를 결정해야 한다.

$(a \oplus b)+(b \oplus c)+(c \oplus a)=n$

풀이

$n$이 홀수면, 조건을 만족하는 정답은 없다. $return -1$
이건 $a, b, c$에 홀수, 짝수를 잘 조합해보면 바로 알 수 있다.

$a, b$ 를 $0$으로 고정시키고 풀면 간단하다. 전형적인 코포스타일 문제.
$a=0, b=0$으로 두면, 위 식은 간단하게 정리된다. $2*c=n$ 이고, $c = n/2$이다

코드

def solve():
    n = int(input())
    if n%2:
        print(-1)
    else:
        print(0, 0, n//2)

for __ in range(int(input())):
    solve()

B. Almost Ternary Matrix

$n, m$이 주어진다. $n*m$짜리 그리드를 $0$과 $1$로 채워야 한다. 문제는, 이웃한 숫자들 중에 다른 숫자가 딱 $2$개 존재하게 채워야 한다. 예를 들면, $0$으로 채워진 칸은 이웃한 칸에 $1$이 딱 $2$개 존재해야 한다.

풀이

구성적 느낌의 문제다. 다음 패턴을 확장, 반복해서 출력하면 된다.
직접 그림을 그려가며 패턴을 찾아야 한다.

1 0 0 1
0 1 1 0 
0 1 1 0
1 0 0 1

코드

dp = [[1, 0, 0, 1]*50, [0, 1, 1, 0]*50, [0, 1, 1, 0]*50, [1, 0, 0, 1]*50]*50
 
def solve():
    a, b = map(int, input().split())
    for d in dp[:a]:
        print(*d[:b])  

    
for __ in range(int(input())):
    solve()

C. The Third Problem

길이가 $n$인 $permutation$ $a$가 주어진다. 우리는 모든 구간에서 $a$와 $similar$한 $permutation$ $b$를 만들어야 한다. $similar$의 조건은 다음과 같다.

모든 구간 $[l, r]$에 대해서 $MEX([a_l, a_{l+1}, ..., a_{r}]) = MEX([b_l, b_{l+1}, ..., b_{r}])$를 만족하면 $similar$하다.

풀이

$a$에서 $i$의 위치를 $p[i]$라고 가정하자. $b$에서 $0$의 위치를 잘 생각해보자. $b$에서 $0$의 위치는 반드시 $p[0]$이다. $MEX([a_{p[0]}])=1$ 이기 때문이다. $b$에서 $1$의 위치도 고민해보자. $1$ 역시 $p[1]$에 위치한다.

구간 $[l, r]$을 정의해보자. $l=p[0], r=p[1] \;\ (p[0]<p[1])$이라고 가정하자. 이때, $a$에서 $2$의 위치를 생각해보자.

$l < p[2] < r$ 이라면, $b$에서 $2$는 구간 $[l,r]$ 안에 존재해야 한다. 이거에 대한 정당성은 에디토리얼에 자세히 적혀 있다. 이 경우에, $ans \; *= (r-l+1-i)$ 해준다. $(r-l+1-i)$은 구간 $[l,r]$에서 $2$가 위치할 수 있는 경우의 수다.

$p[2]$가 구간 밖에 존재한다면, 구간 $[l,r]$을 $p[2]$를 포함하는 구간으로 적절히 갱신해준다.

코드

MOD = 1_000_000_007

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 1

    p = [0]*n
    for i in range(n):
        p[a[i]] = i
        
    l, r = p[0], p[0]

    for i in range(1, n):
        idx = p[i]
        if l < idx < r:
            ans *= (r-l+1-i)
            ans %= MOD
        l = min(l, idx)
        r = max(r, idx)
        
    print(ans)
    
for __ in range(int(input())):
    solve()