2024 ICPC Seoul Regional First Round 관전

대회 시간 중 떠올랐던 아이디어 몇 개를 남겨봅니다.
 
 
E번. Matrix Game (한. 행렬 게임)
새로운 행렬 C에 대하여 C의 각 원소는 |C_i,j = |A_i,j - B_i,j|로 구성되어 있다고 하자. C의 각 열에 대하여 그 열에서 얻어질 수 있는 최댓값을 전처리한다. M개의 수에 대하여, 그 수의 열에서 전처리된 값을 더해나간다. 
(예: 예제 입력 2에서 얻어지는 행렬 C는 {{2, 3}, {1, 4}}이고 1열에서 얻어지는 최댓값은 2, 2열에서 얻어지는 최댓값은 4임을 알 수 있다. M개의 수가 각각 1, 1, 2이므로 답은 2+2+4 = 8.)
 
 
 
F번. Mining Rights (한. 채굴권 분할)
두 점 p1, p2로 만들어지는 선분과 교차되는 분할선의 개수가 짝수 개이면 "YES", 홀수 개이면 "NO"를 출력.
분할선도 그렇고, 두 점 p1, p2도 그렇고 좌표 설정이 관건인 것처럼 보인다. (실제 대회장이었으면 나는 못 풀었을 듯..)
 
 
 
H번. Number Allocation (한. 숫자 할당)
가장 생각하기 쉬운 풀이의 시간복잡도는 13! 인데 이 수가 20억에 가깝기 때문에 좀 더 생각해 보아야 한다. 가지치기 방법이 여러가지 있을 수 있겠지만, 내가 생각해낸 풀이의 순서는
   1) 원소 두 개의 합만을 가지는 D, H부터 먼저 쌍을 골라낸다.
   2) 나머지 9개의 원소를 가지치기하면서 완전탐색
 
(시간 내에 도는지 궁금해서 이 문제는 코드를 한 번 짜봤다.)

#include <iostream>
using namespace std;

int ans = 0;
int A, B, C, D, E, F, G, H;
int stage[5][5];
bool chk[15];

void go(int k)
{
    if(k == 9)
    {
        if(stage[0][0] + stage[1][0] + stage[2][0] + stage[3][0] == A)
            if(stage[0][1] + stage[1][1] + stage[2][1] + stage[3][1] == B)
                if(stage[0][2] + stage[1][2] + stage[2][2] + stage[3][2] == C)
                    ans++;
        return;
    }

    for(int i = 1; i <= 13; i++)
        if(!chk[i])
        {
            chk[i] = 1;
            stage[k/3][k%3] = i;
            if((k+1)%3 > 0)
                go(k+1);
            else if(k+1 == 3 && stage[0][0] + stage[0][1] + stage[0][2] + stage[0][3] == E)
                go(k+1);
            else if(k+1 == 6 && stage[1][0] + stage[1][1] + stage[1][2] + stage[1][3] == F)
                go(k+1);
            else if(k+1 == 9 && stage[2][0] + stage[2][1] + stage[2][2] + stage[2][3] == G)
                go(k+1);
            chk[i] = 0;
        }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> A >> B >> C >> D >> E >> F >> G >> H;

    for(int i = 1; i <= 13; i++)
    {
        if(D-i > 13 || D-i <= 0 || D-i == i)
            continue;

        stage[0][3] = i;
        stage[1][3] = D-i;

        for(int j = 1; j <= 13; j++)
        {
            if(j == i || j == D-i)
                continue;
            if(H-j > 13 || H-j <= 0 || H-j == j)
                continue;
            
            stage[3][0] = j;
            stage[3][1] = H-j;

            chk[i] = chk[D-i] = chk[j] = chk[H-j] = 1;
            go(0);
            chk[i] = chk[D-i] = chk[j] = chk[H-j] = 0;
        }
    }

    cout << ans << '\n';
}

 
 
 
G번. New Megacity
크루스칼 알고리즘으로 우선 MST를 만들어 나간다. MST가 만들어진 이후에 남아있는 간선들은 모두 type3의 간선임을 알 수 있다. 현재의 MST에는 포함되지 않은 간선들이 다른 MST를 만들 수 있음(이러한 간선을 '후보 간선'이라 하자.)은 어떻게 알 수 있을까? 어떤 후보 간선이 두 정점 u, v를 잇고 있고 가중치가 w일 때, 현재의 MST에서 u에서 v까지의 경로 중 가중치가 w인 간선이 존재하면 이 후보 간선은 type2가 됨을 알 수 있다. 문제는 어떻게 빨리 1)경로에서 w를 찾아낼 수 있는지, 2)현재의 MST 간선에 type2를 지정할 수 있는지 인데..
떠오르는 방법이 있긴 하지만, 시간 내에 돌지도 모르겠고 풀이의 정당성이 맞는지도 모르겠다..
 
 
 
C번. Covers
직관적으로는 "KMP + 무언가" 같은 풀이이지 않을까 싶은데.. 그 무언가가 dp인지 그리디인지 아니면 또 다른 무언가인지는 잘 모르겠다.