A. 牛牛吃米粒

入力: 整数 n, k と符号なし整数 s、および k 個の位置 a_i。各ビット位置が制限されていないか検証し、s のビットが立っている位置が禁止領域と重なる場合は "NO"、それ以外は "YES" を出力。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    unsigned long long s;
    int n, k;
    cin >> n >> k;
    vector<bool> restricted(64, false);
    for (int i = 0; i < k; i++) {
        int pos;
        cin >> pos;
        restricted[pos] = true;
    }
    cin >> s;

    for (int idx = 0; idx < 64 && s; idx++, s >>= 1) {
        if ((s & 1) && restricted[idx]) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

B. 牛牛嚯可乐

目標文字列 "cocacola" への変換に必要な最小隣接スワップ回数をDFSで計算。文字列長は固定(8文字)。

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
const string TARGET = "cocacola";

void findMinSwaps(string str, int pos, int moves, int &minMoves) {
    if (pos == 8) {
        minMoves = min(minMoves, moves);
        return;
    }
    if (str[pos] == TARGET[pos]) {
        findMinSwaps(str, pos + 1, moves, minMoves);
    } else {
        for (int next = pos + 1; next < 8; next++) {
            if (str[next] == TARGET[pos]) {
                swap(str[pos], str[next]);
                findMinSwaps(str, pos + 1, moves + 1, minMoves);
                swap(str[pos], str[next]);
            }
        }
    }
}

int main() {
    string input;
    cin >> input;
    int result = INT_MAX;
    findMinSwaps(input, 0, 0, result);
    cout << result << endl;
    return 0;
}

C. 牛牛吃豆人

3列×n行グリッドで2経路が交差せずに通過可能か判定。障害物位置を考慮し、貪欲下降法で経路検証。

#include <iostream>
#include <vector>
using namespace std;

bool validatePath(vector<vector<bool>> &grid, int startRow, int startCol, int endRow, int endCol) {
    int row = startRow, col = startCol;
    while (row <= endRow) {
        grid[row][col] = true;
        if (row == endRow && col == endCol) return true;
        if (row < endRow && !grid[row + 1][col]) {
            row++;
        } else if (col < endCol && !grid[row][col + 1]) {
            col++;
        } else {
            return false;
        }
    }
    return false;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> grid(n + 1, vector<bool>(4, false));
    while (m--) {
        int row, col;
        cin >> col >> row;
        grid[row][col] = true;
    }
    if (!validatePath(grid, 1, 1, n, 2) || !validatePath(grid, 1, 2, n - 1, 3)) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
    return 0;
}

D. 牛牛种小树

木の次数分布最適化問題。次数和2n-2の制約下で関数fの総和最大化。完全ナップサック問題に帰着。

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> f(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> f[i];
    }
    vector<long long> dp(n, LLONG_MIN);
    dp[0] = 0;
    long long base = f[0] * n;
    for (int i = 1; i < n - 1; i++) {
        f[i] -= f[0];
    }
    for (int i = 1; i < n - 1; i++) {
        for (int j = i; j <= n - 2; j++) {
            if (dp[j - i] != LLONG_MIN) {
                dp[j] = max(dp[j], dp[j - i] + f[i]);
            }
        }
    }
    cout << base + dp[n - 2] << endl;
    return 0;
}

E. 牛牛小数点

解法は公式解説を参照: 牛客解説リンク

F. 牛牛防疫情

グリッド感染拡大防止の最小遮断コスト計算。感染源から安全地帯への最大フローをDinic法で求解。

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <climits>
using namespace std;
const int INF = INT_MAX;

struct Edge {
    int dest, cap, rev;
};

vector<vector<Edge>> graph;
vector<int> level;

void addEdge(int src, int dst, int cap) {
    graph[src].push_back({dst, cap, (int)graph[dst].size()});
    graph[dst].push_back({src, 0, (int)graph[src].size() - 1});
}

bool bfs(int s, int t) {
    fill(level.begin(), level.end(), -1);
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto &e : graph[u]) {
            if (e.cap > 0 && level[e.dest] < 0) {
                level[e.dest] = level[u] + 1;
                q.push(e.dest);
            }
        }
    }
    return level[t] >= 0;
}

int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    for (auto &e : graph[u]) {
        if (e.cap > 0 && level[e.dest] == level[u] + 1) {
            int f = dfs(e.dest, t, min(flow, e.cap));
            if (f > 0) {
                e.cap -= f;
                graph[e.dest][e.rev].cap += f;
                return f;
            }
        }
    }
    return 0;
}

int maxFlow(int s, int t) {
    int total = 0;
    while (bfs(s, t)) {
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            total += f;
        }
    }
    return total;
}

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    int gridSize = n * n;
    graph.resize(gridSize + 2);
    level.resize(gridSize + 2);
    int source = gridSize, sink = gridSize + 1;
    vector<bool> infection(gridSize, false);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        infection[y * n + x] = true;
    }
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            int idx = y * n + x;
            if (infection[idx]) {
                addEdge(source, idx, INF);
                if (y < n - 1) addEdge(idx, idx + n, 1);
                if (x < n - 1) addEdge(idx, idx + 1, 1);
            } else {
                addEdge(idx, sink, c);
            }
        }
    }
    cout << maxFlow(source, sink) << endl;
    return 0;
}