Atcoder Beginner Contest 266 후기

A. Middle Letter

 길이가 홀수인 문자열이 주어질 때, 중앙에 위치한 문자를 출력하는 문제이다

import sys

arr = list(sys.stdin.readline().rstrip())
print(arr[len(arr) // 2])

B. Modulo Number

 $-10^8 \leq N \leq 10^8 $인 N이 주어질 때, N - x가 998244353의 배수가 되게 하는 $0 \leq x \leq 998244352$를 찾는 문제이다. 브루트포스를 통해 x를 찾게 되면 TLE를 피할 수 없다. 그런데, 998224353의 배수가 된다는 것은, 결국 $(N - x) \  mod \  998224353$이 0이 된다는 것과 동치이다. 그런데, mod 연산은 뺄샘과 덧셈, 곱셉에 대한 분배법칙이 성립하기 때문에, $ N \ mod \  998224353 \ - x \ mod \ 998224353 = 0 $이어야 한다. 그런데, x의 범위를 생각하면 $ x \ mod \ 998224353 = x$이다. 따라서, 단순히 N을 998224353으로 나눈 나머지와 x는 같다

import sys, math

n = int(sys.stdin.readline())
val = 998244353
print(n % val)

 

C. Convex Quadrilateral

 네 점이 반시계 방향으로 주어질 때, 형성되는 사각형의 내각이 모두 180미만이라면 Yes, 그렇지 않다면 No를 출력하는 문제이다. 2차원 벡터의 외적을 이용하면 쉽게 정답을 알 수 있다. 왜냐하면 외적은 삼각형의 넓이와 관련이 있기 때문이다.

 삼각형의 넓이를 S라고 할 때, $S = \frac{1}{2} \left\| \vec{a} * \vec{b} \right\| = \frac{1}{2} \left\| \vec{a} \right\| * \left\|  \vec{b} \right\| * sin(\theta)$와 같다. 그런데, 만일 $\vec{a}$와 $\vec{b}$가 이루는 각이 180보다 커버리면, 해당 각도로는 삼각형을 만들 수 없다.

<그림 1. 벡터 a에서 벡터 b의 사이각이 180도 이상인 경우>

 위 그림 1은 외적과 삼각형의 관계에서 사이각이 180도를 넘어가는 경우를 나타내는 그림이다. 빨간색 각도가 사이각이 아니냐라고 할 수 있지만, 문제에서는 a에서 b로 반시계방향으로 하는 각이 내각이라고 정의하고 있으므로 현재 문제 상에서는 파란색 각도가 사이각임을 유의해야 한다. 따라서, 외적과 삼각형의 관계를 만족하기 위해 어쩔수 없이 문제에서 정의하지 않는 사이각인 빨간색 각도를 선택하게 된다. 

<그림 2. 사선으로 나누는 경우>

 따라서 사선으로 나누게 되면, 내각이 180도 이상인 경우, 어쩔 수 없이 새로운 삼각형이 생기게 된다. 각 내각들이 180도 미만이었다면, 일반적인 평행사변형 형태이기 때문에 새로운 삼각형이 생기지 않기 때문에 $\bigtriangleup ABC + \bigtriangleup ACD = \bigtriangleup BCD + \bigtriangleup BAD$를 만족해야 한다. 따라서, 해당 등식을 만족하는 지 여부가 곧 정답이 된다

import sys

# calc : 세 점이 이루는 삼각형의 면적을 리턴하는 함수
def calc(x, y, z):
    # 1/2이 없는 이유는 어차피 약분이 되기 때문이다
    return abs((x[0] * y[1] + y[0] * z[1] + z[0] * x[1]) - (y[0] * x[1] + z[0] * y[1] + x[0] * z[1]))

arr = []
for _ in range(4):
    a, b = map(int, sys.stdin.readline().split())
    arr.append((a, b))
A = arr[0]
B = arr[1]
C = arr[2]
D = arr[3]
print('Yes' if calc(A, B, C) + calc(A, C, D) == calc(B, C, D) + calc(A, B, D) else 'No')

 

D. Snuke Panic (1D)

 전형적인 다이나믹 프로그래밍 문제이다. 상태공간을 현재 시간이 time이고 현재 위치가 pos일 때 얻을 수 있는 가장 큰 Snuke의 크기라고 정의하자. 이 때 겹치는 time이 없다는 것이 문제에서 보장되기 때문에 현재 시간과 위치에서 단순히 snuke가 있는지 없는지만 계산하면 된다. 또한 점화식은 현재 위치에서 다른 위치로 움직이는 것밖에 없기 때문에 점화식은 아래와 같다. $$ dp[time][pos] = max(dp[time][pos], dp[nextTime][nextPos] + cache[nextTime][nextPos]) $$

단, nextPos의 경우 범위가 0이상 5이하이며, pos와 같을 수도 있음을 유의해야 한다. pos와 nextPos가 같은 경우, 즉 제자리에 가만히 있는 경우라면 그 때의 nextTime은 time+1이므로 시간에도 유의가 필요하다

// PyPy3를 쓰면 시간초과가 나기 때문에 같은 로직을 C++로 작성

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int n;
// val : snuke가 마지막으로 출현하는 시점
int val = 0;
// dp : 현재 시간이 t이고 위치가 pos일 때 얻을 수 있는 snuke의 크기의 합의 최대를 저장하는 2차원 상태 공간 배열
ll dp[100001][5];
// cache : 현재 시간이 t이고 위치가 pos일 때 얻을 수 있는 snuke의 크기를 저장하는 2차원 배열
ll cache[100001][5];

// go : 현재 시간이 t이고 위치가 pos일 때 얻을 수 있는 snuke의 크기의 합의 최대를 리턴하는 함수
ll go(int t, int pos) {
    // Base Case : 마지막 시간에 도달한 경우
    if (t == val) {
        return 0;
    }
    // Memoization
    if (dp[t][pos] != -1) {
        return dp[t][pos];
    }
    dp[t][pos] = 0;
    for (int i = 0; i < 5; i++) {
    	// 현재 위치에 머무는 경우 
        if (i == pos) {
            // 1초를 더 기다려도 최대 시간 이하인 경우
            if (t + 1 <= val) {
                dp[t][pos] = max(dp[t][pos], go(t + 1, pos) + cache[t + 1][i]);
            }
        }
        // 다른 위치로 이동하는 경우
        else {
            if (t + abs(pos - i) <= val) {
                dp[t][pos] = max(dp[t][pos], go(t + abs(pos - i), i) + cache[t + abs(pos - i)][i]);
            }
        }
    }
    return dp[t][pos];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // 입력부
    cin >> n;
    // 배열 초기화
    memset(cache, 0, sizeof(cache));
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        // snuke가 출현하는 최대 시간 갱신
        val = max(val, a);
        cache[a][b] = c;
    }
    // 정답 출력
    cout << go(0, 0) << "\n";
}

 

E. Throwing the Die

 대회 도중에 1시간을 남겨두고 문제 지문에 대한 이해 부족과 기댓값에 대한 이해 부족으로 풀지 못했던 문제이다. 우선 기댓값에 대한 정의를 살펴보면, $E(X) = \sum_{i = 1}^{n} X_{i} * P(X_{i})$이다. 이 때, $X_i$를 사건이라고 일반적으로 생각하기 쉬운데, 오히려 얻을 수 있는 점수라고 생각하면 좀 더 쉽게 이해할 수 있다.

 따라서 상태공간을 현재 차례인 idx, 현재 나온 눈을 num이라고 할 때 얻을 수 있는 기댓값의 최댓값이라고 정의하자. 이 때 점화식은 아래와 같다.

$$ dp[idx][num] = \frac{1}{6} * max(num, \sum_{i = 1}^{6} dp[idx + 1][i]) $$

<그림 3. N=2인 경우>

 위 그림 3은 전체 2턴으로 이루어진 게임에서 현재 상태가 1번째 턴이고 나온 주사위의 눈이 3인 상황을 나타낸 그림이다. 따라서, 현재 상태에서 그냥 점수를 3으로 하고 완전히 게임을 중단하느냐, 그렇지 않다면 마지막 턴인 2번째 턴으로 계속 할 건지를 결정해야 한다. 우선 멈춘다면, 확정적으로 3이 점수가 된다. 그러나, 턴을 한 번 더 이어갈 경우, 얻을 수 있는 점수는 얼마인가? 잘은 몰라도 그것은 다음 2번째 턴에서의 모든 경우 (눈이 1이 나오는 경우부터 눈이 6이 나오는 경우까지)를 고려해야 함을 알 수 있다. 왜냐하면 다음 차례에서 어떤 눈이 나올지 현재 상태에서는 전혀 모르기 때문이다.

 따라서, 위에서 언급한 기댓값의 정의에 따라 얻을 수 있는 점수의 경우를 생각했을 때, $X_{stay} = 3, X_{go} = Expected \ Value \  Of \ Turn \ 2$임을 알 수 있다. 왜냐하면 다음 차례에 어떤 눈이 나올지 모르기 때문에 다음 차례의 기댓값이 곧 예상가능한 점수와 동치가 되기 때문이다. 마지막으로 각각의 확률은 모두 $\frac{1}{6}$이 되는데 이유는 멈추든, 계속 진행하든 현재 상황에서 주사위를 무조건 던져야 하기 때문이다.

import sys, math

def go(idx, num):
    if idx == n:
        return 0
    if dp[idx][num] != -1:
        return dp[idx][num]
    dp[idx][num] = 0
    res = 0
    for i in range(1, 7):
        res += go(idx + 1, i)
    dp[idx][num] = max(res, num)
    dp[idx][num] /= 6
    return dp[idx][num]

n = int(sys.stdin.readline())
dp = [[-1] * 7 for _ in range(n)]
ans = 0
for i in range(1, 7):
    ans += go(0, i)
print(ans)

 

 

 총평 : 기하에 약한 편인데(사실 그냥 다 약하지만) 앞단에서 기하문제가 나와버려 시간을 꽤나 썼던 문제이다. D번의 경우는 전형적인 dp문제여서 오히려 C번보다도 빠르게 풀었다. 그럼에도 E를 손댈만한 시간인 1시간 남짓이 나왔는데, 문제에 대한 이해를 제대로 못해서 시간만 버리고 나왔다. 그나마 문제 구조가 dp라는 점은 캐치했다는 점은 있으나, 업솔빙 후 그리 난이도가 높지 않아 아쉬웠다! 저번 대회에서는 400등대의 높은 퍼포먼스였는데 이번에는 무섭게 원래 퍼포먼스로 회귀해버려서 씁쓸하지는 않다. 어차피 원래 있어야 할 자리였기 때문이다!