#1083819 (C++17) No.861 ケーキカット

• 問題: No.861 ケーキカット
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:03:25
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 9,052 bytes
• コンパイル時間: 2,775 ms
• コンパイル使用メモリ: 97,044 KB
• 実行使用メモリ: 19,144 KB
• 最終ジャッジ日時: 2025-05-14 13:05:06
• 合計ジャッジ時間: 5,715 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

ファイルパターン	結果
sample	-- * 3
other	TLE * 1 -- * 20

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <queue>
#include <limits>
#include <vector> // Ensure vector is included
#include <cstdlib> // For std::abs

// Detect GCC/Clang to use compiler builtins for optimization
// Builtins like __builtin_ctz and __builtin_popcount can speed up mask operations.
#if defined(__GNUC__) || defined(__clang__)
#define USE_BUILTINS
#endif

using namespace std;

// Use long long for deliciousness values and sums to avoid overflow, as values can be large.
typedef long long ll;

const int GRID_SIZE = 5; // The cake is 5x5
const int N = GRID_SIZE * GRID_SIZE; // Total number of cells (25)

// vals: 1D array storing deliciousness values. Cell (i, j) maps to index k = i * GRID_SIZE + j.
ll vals[N]; 
// adj: Adjacency list for the grid graph. adj[k] stores indices of neighbors of cell k.
vector<vector<int>> adj(N); 
// total_sum: Stores the sum of deliciousness values of all cells in the cake.
ll total_sum = 0; 

// Function to check connectivity of a subset of cells represented by a bitmask.
// Uses Breadth-First Search (BFS).
// Input:
//   mask: An integer where the k-th bit is set if cell k is in the subset.
//   current_sum_ptr: Pointer to a long long where the sum of deliciousness values of the connected component will be stored.
// Returns:
//   true if the subset is connected, false otherwise.
//   If true, *current_sum_ptr contains the sum of deliciousness values for the cells in the mask.
bool isConnectedOptimized(int mask, ll* current_sum_ptr) {
    // An empty set (mask 0) is not a valid portion for A or B according to the problem statement.
    if (mask == 0) return false; 

    // Find the index of the first cell included in the subset (mask).
    // This cell will be the starting point for BFS.
    // Using __builtin_ctz (count trailing zeros) is efficient if available.
    #ifdef USE_BUILTINS
    int start_node = __builtin_ctz(mask); 
    #else
    // Fallback: linear scan to find the first set bit if builtins are not available.
    int start_node = -1;
    for(int i = 0; i < N; ++i) {
        if ((mask >> i) & 1) { // Check if the i-th bit is set
            start_node = i;
            break;
        }
    }
    // This check should ideally never fail if mask > 0.
    if (start_node == -1) return false; 
    #endif

    // BFS setup
    int visited_mask = 0; // Bitmask to keep track of visited cells during BFS for this component.
    queue<int> q; // Queue for BFS nodes to visit.
    
    q.push(start_node); // Start BFS from the first node found.
    visited_mask |= (1 << start_node); // Mark start_node as visited.
    int count = 0; // Counter for the number of cells visited by BFS.
    ll current_sum = 0; // Accumulator for the sum of deliciousness values in the connected component found by BFS.

    // BFS traversal
    while (!q.empty()) {
        int u = q.front(); // Get the next cell index from the queue.
        q.pop();
        
        count++; // Increment the count of visited cells.
        current_sum += vals[u]; // Add the deliciousness of the current cell to the sum.

        // Explore neighbors of the current cell u using the precomputed adjacency list.
        for (int v : adj[u]) {
            // Check three conditions for neighbor v:
            // 1. Is neighbor v part of the subset defined by the input mask? Check if v-th bit is set in 'mask'.
            // 2. Has neighbor v not been visited yet in this BFS run? Check if v-th bit is not set in 'visited_mask'.
            if (((mask >> v) & 1) && !((visited_mask >> v) & 1)) {
                visited_mask |= (1 << v); // Mark neighbor v as visited.
                q.push(v); // Add neighbor v to the queue for exploration.
            }
        }
    }

    // After BFS, check if the number of visited cells ('count') matches the 
    // total number of cells expected in the subset (population count of 'mask').
    // Using __builtin_popcount is efficient if available.
    int popcount;
    #ifdef USE_BUILTINS
    popcount = __builtin_popcount(mask);
    #else
    // Fallback: manual popcount implementation if builtins are not available.
    popcount = 0;
    int temp_mask = mask;
    while (temp_mask > 0) {
        // Clear the least significant set bit. Counting these operations gives popcount.
        temp_mask &= (temp_mask - 1); 
        popcount++;
    }
    #endif

    // If BFS visited exactly the number of cells present in the mask, the subset is connected.
    if (count == popcount) {
        *current_sum_ptr = current_sum; // Store the calculated sum of deliciousness.
        return true; // Return true indicating the subset is connected.
    } else {
        // If the counts don't match, it means BFS didn't reach all cells in the mask,
        // so the subset is not connected.
        return false;
    }
}


int main() {
    // Optimize standard I/O operations for speed.
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Precompute the adjacency list for the grid graph.
    // Each cell (i, j) is mapped to a linear index k = i * GRID_SIZE + j.
    for (int i = 0; i < GRID_SIZE; ++i) {
        for (int j = 0; j < GRID_SIZE; ++j) {
            int k = i * GRID_SIZE + j; 
            // Add edge to cell above if not in the first row (i > 0).
            if (i > 0) adj[k].push_back(k - GRID_SIZE); 
            // Add edge to cell below if not in the last row (i < GRID_SIZE - 1).
            if (i < GRID_SIZE - 1) adj[k].push_back(k + GRID_SIZE); 
            // Add edge to cell left if not in the first column (j > 0).
            if (j > 0) adj[k].push_back(k - 1); 
            // Add edge to cell right if not in the last column (j < GRID_SIZE - 1).
            if (j < GRID_SIZE - 1) adj[k].push_back(k + 1); 
        }
    }

    // Read the deliciousness values (C_ij) for each cell from input.
    // Store them in the 1D array `vals` using the linear index k.
    // Calculate the total sum of deliciousness values for the entire cake.
    for (int i = 0; i < GRID_SIZE; ++i) {
        for (int j = 0; j < GRID_SIZE; ++j) {
             ll val_ij;
             cin >> val_ij; // Read C_ij value.
             int k = i * GRID_SIZE + j; // Calculate the linear index k.
             vals[k] = val_ij; // Store the value in the 1D array.
             total_sum += val_ij; // Accumulate the total sum.
        }
    }

    // Initialize the minimum difference found so far. 
    // Using -1 as a sentinel value to indicate that no valid partition has been found yet.
    // Alternatively, use LLONG_MAX from <limits>.
    ll min_diff = -1; 

    // Iterate through all possible non-empty proper subsets of cells represented by bitmasks.
    // We only need to iterate through masks from 1 up to (but not including) 2^(N-1).
    // This strategy ensures that each partition {S, V\S} is considered exactly once.
    // For a mask 'm' representing subset S, its complement 'complement_m' represents V\S.
    // If we check 'm', we don't need to check 'complement_m' later.
    // Iterating up to 2^(N-1)-1 covers all subsets S where |S| <= N/2 (plus some with |S| > N/2 if N is even).
    // Every partition pair {S, V\S} will have one member considered.
    int limit = 1 << (N - 1); // The upper bound for the loop is 2^(N-1). Iteration runs for m = 1, ..., 2^(N-1)-1.
    int full_mask = (1 << N) - 1; // A mask with all N bits set, representing the full set of cells.

    for (int m = 1; m < limit; ++m) {
        ll current_sum_A; // Variable to store the sum for subset A (represented by mask m).
        // Check if subset A is connected. If yes, get its sum in current_sum_A.
        if (isConnectedOptimized(m, &current_sum_A)) {
            // If A is connected, calculate the mask for its complement subset B.
            int complement_m = full_mask ^ m; 
            ll dummy_sum_B; // Temporary variable to pass to isConnected for B's connectivity check. Its value is not needed here.

            // Check if the complement subset B is also connected.
            if (isConnectedOptimized(complement_m, &dummy_sum_B)) {
                // If both A and B are connected, this forms a valid partition of the cake.
                
                // Calculate the sum for subset B using the total sum and A's sum: S_B = S_total - S_A.
                ll current_sum_B = total_sum - current_sum_A; 
                
                // Calculate the absolute difference between the sums of A and B. Use std::abs for long long.
                ll diff = std::abs(current_sum_A - current_sum_B);

                // Update the minimum difference found so far if the current partition yields a smaller difference.
                // Handle the initial case where min_diff is the sentinel value -1.
                if (min_diff == -1 || diff < min_diff) {
                    min_diff = diff;
                }
            }
        }
    }

    // Output the overall minimum difference found across all valid partitions.
    cout << min_diff << endl;

    return 0;
}