C The Nether: DAG에서 최장 경로 탐색

이 문제는 그래프의 구조를 쿼리하는 방식으로 해결하는 인터랙티브 문제입니다. 주어진 방향성 비순환 그래프(DAG)에서 가능한 최대 길이의 경로를 찾아야 하며, 쿼리 제한은 2n번입니다.

핵심 전략은 각 정점에서 시작하는 최장 경로 길이를 미리 계산한 후, 그 중 가장 큰 값을 가진 정점을 시작점으로 삼고, 이후 점차 이어지는 정점을 하나씩 추론하는 것입니다.

먼저 모든 정점 i에 대해 전체 정점 집합을 사용하여 ? i n 1 2 ... n 쿼리를 수행해, 각 정점에서 시작하는 최장 경로 길이 p[i]를 얻습니다. 이때 p[i]가 최대인 정점 b를 선택하면, 이는 최적 경로의 시작점이 됩니다.

다음 단계에서는 다음 정점 v₂부터 찾습니다. 조건은 p[j] == p[b] - 1이고, b와 j 사이에 간선이 존재해야 합니다. 이를 위해 ? b 2 b j 쿼리를 통해 간선 여부를 확인합니다. 유사한 방식으로 이후 정점들을 순차적으로 결정합니다.

총 쿼리 수는 초기 n번과 이후 각 정점별 최대 1번씩의 쿼리로, 최대 2n-1번이므로 제약 조건을 충족합니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;

int n, dist[MAXN], path[MAXN];

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

    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        memset(path, 0, sizeof(path));

        // 각 정점에서 시작하는 최장 경로 길이 측정
        for (int i = 1; i <= n; ++i) {
            cout << "? " << i << " " << n;
            for (int j = 1; j <= n; ++j) {
                cout << " " << j;
            }
            cout << endl;
            cin >> dist[i];
            if (dist[i] >= dist[path[1]]) path[1] = i;
        }

        int current = path[1];
        int len = dist[current];

        // 경로 구성: 현재 정점 기준으로 다음 정점 탐색
        for (int step = 1; step < len; ++step) {
            bool found = false;
            for (int next = 1; next <= n; ++next) {
                if (dist[next] != dist[current] - 1) continue;
                cout << "? " << current << " 2 " << current << " " << next << endl;
                int result;
                cin >> result;
                if (result == 2) {  // 간선 존재
                    current = next;
                    path[step + 1] = next;
                    found = true;
                    break;
                }
            }
            if (!found) break;
        }

        // 결과 출력
        cout << "! " << len;
        for (int i = 1; i <= len; ++i) {
            cout << " " << path[i];
        }
        cout << endl;
    }

    return 0;
}

D Chicken Jockey: 생물 덱의 최소 공격 횟수

생물이 쌓여 있는 덱에서, 한 번의 공격으로 특정 생물에 1만큼 피해를 입힐 수 있습니다. 생물이 사망하면 위의 생물들이 떨어지며, 아래에 있던 생물 수만큼의 피해를 받게 됩니다. 이 과정이 연쇄적으로 발생할 수 있으며, 전체 생물을 제거하기 위한 최소 공격 횟수를 구해야 합니다.

동적 프로그래밍을 사용합니다. f[i]를 첫 번째부터 i번째 생물까지 제거하는 최소 공격 횟수로 정의합니다.

전이 관계는 다음과 같습니다:

• 첫 번째 방법: 앞의 i-1개를 먼저 제거하고, i번째 생물에게 1점 피해를 줘서 제거 → f[i-1] + a[i] - 1
• 두 번째 방법: i-1번째 생물을 먼저 제거 → i번째 생물에게 i-1점 피해를 입히고, 이후 a[i] - (i-1)만큼 더 공격 필요 → f[i-2] + a[i-1] + max(0, a[i] - i + 1)

두 경우 중 최소값을 선택하며, 음수 피해는 무시합니다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 200005;

ll a[MAXN], dp[MAXN];

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        dp[1] = a[1];
        for (int i = 2; i <= n; ++i) {
            ll option1 = dp[i-1] + a[i] - 1;
            ll option2 = dp[i-2] + a[i-1] + max(0LL, a[i] - i + 1);
            dp[i] = min(option1, option2);
        }

        cout << dp[n] << '\n';
    }

    return 0;
}

E I Yearned For The Mines

제한 시간 내에 여러 지뢰를 효과적으로 제거해야 하는 문제입니다. 각 지뢰는 위치와 폭발 반경을 가지며, 공격 시 그 영역 내의 지뢰가 동시에 제거됩니다. 이때 최대한 많은 지뢰를 한 번의 공격으로 제거할 수 있도록 전략을 세워야 합니다.

기본 아이디어는 지뢰의 좌표를 기준으로 가능한 공격 위치를 탐색하고, 각 공격이 얼마나 많은 지뢰를 제거하는지 계산하는 것입니다. 그리디 또는 스위핑 기법을 활용해, 가장 효율적인 공격 위치를 선택합니다.

또한, 지뢰 간 거리가 작을수록 한 번의 공격으로 처리 가능성이 높아지므로, 중심 지점 근처에서 공격을 수행하는 것이 유리합니다.

F Flint and Steel

불꽃을 일으키기 위한 재료 조합 문제입니다. 다양한 재료 조합이 가능하며, 각 조합마다 불꽃 발생 확률이 다릅니다. 목표는 최대 확률로 불꽃을 발생시키는 조합을 찾는 것입니다.

문제는 확률 값의 조합을 고려한 백트래킹이나 동적 프로그래밍으로 접근할 수 있습니다. 하지만 제약 조건이 크므로, 우선순위 큐나 힙 기반 탐색을 사용해 가장 높은 확률을 가진 조합을 먼저 탐색하는 방식이 효과적입니다.