Educational Codeforces Round 136 (Rated for Div. 2) 참가 후기

대회 링크: https://codeforces.com/contest/1739

결과

처음으로 코드포스 코테에 참여해 보았다.
영어로 된 문제를 처음 풀어서 지문 해석하는데 시간을 많이 쓴거 같다.
A, B는 쉽게 풀었고 C는 좀 생각한 후에 풀었는데 D부터는 감도 안 잡혔던 것 같다.

A. Immobile Knight

첫 문제다운 쉬운 문제였다.
체스판이 있고 Knight가 이동할 수 있는 위치가 없는(isolated) 칸을 찾아내는 문제였다.

# (y, x)가 보드 밖이라면 True를 반환하는 함수
def out(y, x): return y < 1 or y > a or x < 1 or x > b

# 나이트가 이동할 수 있는 8방향을 나타내는 변수 dy, dx
dy = [-2, -2, -1, -1, 1, 1, 2, 2]
dx = [-1, 1, -2, 2, -2, 2, -1, 1]

n = int(input())
for i in range(n):
    a, b = map(int, input().split())

    ret = False
    # 보드의 가능한 모든 위치 순회
    for i in range(1, a+1):
        for j in range(1, b+1):
            isIsolated = True
            # Knight가 갈 수 있는 8방향 순회
            for k in range(8):
                ny = i + dy[k]; nx = j + dx[k]
                # 보드 밖이 아닌 곳이 있다면(= Knight가 갈 수 있는 곳이 있다면)
                if not out(ny, nx):
                    isIsolated = False
                    break

            if isIsolated: ret = (i, j)

    # 출력
    if ret: print(*ret)
    else: print(a, b)

B. Array Recovery

A_array에서 만들어진 D_array를 통해 원본인 A_array를 추론하는 문제인데, 가능한 두 가지 경우(+, -) 중 하나만 가능하다면 계속 진행해나가면 되고, 둘 다 가능하다면 break하는 간단한 과정이었다.
쉬운 문제.

t = int(input())

for i in range(t):
    n = int(input())
    d_array = [int(x) for x in input().split()]
    a_array = [d_array[0]]

    for i in range(1, n):
        cand_1 = a_array[-1] + d_array[i]
        cand_2 = a_array[-1] - d_array[i]
        if cand_1 == cand_2: a_array.append(cand_1)
        elif cand_1 >= 0 and cand_2 >= 0: break
        elif cand_1 >= 0: a_array.append(cand_1)
        else: a_array.append(cand_2)

    if len(a_array) == n: print(*a_array)
    else: print(-1)    
    print()

C. Card Game

최근 Div. 2의 C번 문제가 9천~만명의 정답자가 있는 것을 볼 때, 3천명대인 이 문제는 꽤나 어려웠던 것 같다.

실제로도 좀 당황스러웠는데, 익숙치 않은 게임 이론 분야의 문제였기 때문이다.
침착하게 보니 (선공 승리 경우의 수, 후공 승리 경우의 수, 무승부 경우의 수)를 구하는 문제였는데 전체 경우의 수는 n Combination (n//2)로 쉽게 구할 수 있고, 무승부 경우의 수는 1가지임이 쉽게 보여서 선공 승리 경우의 수만 구하면 되겠다는 생각이 들었다.

선공 승리 경우의 수는 크게 2가지였는데,
1. 가장 큰 수(n)를 가지고 있을 때
2. n이 없다면 n-1, n-2, n-3의 3개를 가지고 있을 때
였다.

가장 큰 수를 가지고 있다면 첫 공격 턴에 가장 큰 수를 내면 승리하는 것이 자명하고,

만약 가장 큰 수(n)이 없다면 첫 공격 턴에 n-1을 내서 상대의 n 카드를 소비시키고 상대의 n-4 공격을 n-3으로 막은 후 n-2 카드로 공격해서 승리하는 것.

만약 n과 n-3이 없고 n-1과 n-2만 가지고 있다면
첫 공격 n-1(나) / 상대 n(방어)
첫 방어 n-2(방어) / 상대 n-3(공격)

후에 다시 가장 큰 수가 n-4인 상태로 내 선공이 돌아오기 때문에, n-4 기준으로 다시 승리 경우의 수를 계산하는 방법으로 계산하였다.

def combi(a, b):
    if a <= 0: return 0
    up = 1; down = 1

    for i in range(1, b+1): down *= i
    for i in range(a, a-b, -1): up *= i

    return up // down

t = int(input())
for i in range(t):
    n = int(input())
    total = combi(n, n//2)
    
    ans = 0
    while n > 0:
        ans += combi(n-1, (n//2)-1)
        ans += combi(n-4, (n//2)-3)
        n -= 4
    
    print(ans % 998244353, (total-ans-1) % 998244353, 1)