2025 경인지역 대학 연합 프로그래밍 경시대회 shake! Open Contest 후기

2026년 1월 10일에 진행한 2025 경인지역 대학 연합 프로그래밍 경시대회 shake! Open Contest (이하 shake! 오픈)에 참가했습니다. 4문제를 해결해 전체 참가자 160명 중 21등을 차지했습니다.

A. 릴레이 가위바위보 게임

$1$, $2$, $3$의 등장 횟수는 각각 $N-1$, $N$, $N+1$ 중 하나입니다. 등장 횟수가 $N-1$인 것을 첫째 줄에, $N+1$인 것을 둘째 줄에 출력하면 됩니다. 한 번에 AC를 받았습니다.

B. 히든 이벤트

$P(x)=1-\frac{_{N-M}C_x}{_NC_x}$입니다. $K$가 작으므로 조합의 값을 충분히 계산할 수 있고, 따라서 큰 수 연산을 지원하는 Python 등으로 구현하면 됩니다. 한 번에 AC를 받았습니다.

G. 으악그래프

다음 명제와 그 역을 각각 증명해 봅시다.

• $N\le{}M$이면 이면 주어진 그래프는 으악그래프이다. $\cdots~(p)$

주어지는 그래프는 연결 그래프이므로 $M\ge{}N-1$입니다. $M=N-1$이면 주어진 그래프는 트리가 되는데, 트리에서 임의의 한 간선을 제거하면 그래프가 둘 이상의 연결 요소로 분리됨은 잘 알려져 있습니다. $M=N$이라면 임의의 한 간선을 제거했을 때 그래프가 분리되거나 트리가 되므로 으악그래프입니다. 따라서 $p$는 참입니다.

반대로 $N>M$이라면, 주어진 그래프를 트리로 만들기 위해 둘 이상의 간선을 제거해야 합니다. 즉 그래프를 분리시키지 않고 두 간선을 제거할 수 있으며, 으악그래프가 아닙니다. 따라서 $p$의 역도 참입니다.

결과적으로 $N\le{}M$이면 Yes를, 아니면 No를 출력하면 됩니다. 한 번에 AC를 받았습니다.

J. i18n

탑다운 DP를 사용하여 해결할 수 있습니다. $S_x$를 $S$의 $x$번째 문자부터 끝까지의 부분 문자열, $T_x$를 $T$의 $x$번째 문자부터 끝까지의 부분 문자열로 정의합니다. 다음으로 $DP[i][j]$를 $T_j$가 $S_i$의 약어가 될 수 있는지 여부로 정의합니다. 점화식을 세우는 것이 살짝 귀찮은데, 말로 설명하기도 불편하므로 재귀 코드를 첨부합니다.

char s[2005], t[2005];
int n, m, chk[2005][2005];
bool dp[2005][2005];

bool back(int x, int y) {
    if (x == n && y == m) return true;
    if (x >= n || y >= m) return false;
    if (chk[x][y]) return dp[x][y];
    chk[x][y] = 1;
    bool res = false;

    if (s[x] == t[y]) res = res || back(x + 1, y + 1);
    if ('1' <= t[y] && t[y] <= '9') {
        int k = 0;
        for (int i = y; i < m && '0' <= t[i] && t[i] <= '9'; i++) {
            k = k * 10 + (int) (t[i] - '0');
            if (x + k > n) break;
            res = res || back(x + k, i + 1);
        }
    }
    return dp[x][y] = res;
}

처음에는 메모이제이션을 적용하지 않아 시간 초과가 발생했고, DP 테이블을 도입했더니 AC를 받았습니다. 34분에 AC를 받으면서 인생 처음으로 퍼솔에 성공했습니다. 본 대회 퍼솔도 38분이므로 두 대회를 통틀어 이 문제를 가장 빨리 푼 사람이 되었습니다.

결과

나머지 문제는 너무 어려워 빠르게 도망쳤습니다. 직후에 있던 앳코더에서 좋은 성적을 거두었는데, 아마 이 대회에서 얻은 퍼솔 버프 때문이 아닌가 싶습니다.