#1083987 (C++17) No.506 限られたジャパリまん

• 問題: No.506 限られたジャパリまん
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:13:20
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 7,057 bytes
• コンパイル時間: 853 ms
• コンパイル使用メモリ: 88,972 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:14:18
• 合計ジャッジ時間: 7,317 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
other	AC * 12 WA * 13

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <numeric> // Not strictly needed, but good practice for potentially using standard algorithms
#include <algorithm> // For std::max, though manual comparison is used here
#include <vector>

// Use __builtin_popcount if available (typically on GCC/Clang)
#if defined(__GNUC__) || defined(__clang__)
#define USE_BUILTIN_POPCOUNT
#endif

using namespace std;

// Define long long for convenience, especially for path counts that can exceed 32-bit int limits
typedef long long ll;

ll H, W; // Grid dimensions (East-West H meters, North-South W meters)
int K; // Number of friends
int P; // Number of Japari buns available

// Structure to store friend information
struct FriendInfo {
    int x, y; // Coordinates of the friend
    string name; // Name of the friend
};

vector<FriendInfo> friends; // Vector to store information about all K friends
ll MOD = 1000000007; // Modulo value for path counting

// Function to count set bits (population count) in an integer
// This determines how many friends are chosen in a subset represented by a bitmask
int countSetBits(int n) {
#ifdef USE_BUILTIN_POPCOUNT
    // Use the compiler's built-in function for efficiency if available
    return __builtin_popcount(n);
#else
    // Fallback manual implementation using Brian Kernighan's algorithm
    // Works for non-negative integers
    int count = 0;
    unsigned int val = static_cast<unsigned int>(n); // Use unsigned int for safety with bitwise ops
    while (val > 0) {
        val &= (val - 1); // Clears the least significant set bit
        count++;
    }
    return count;
#endif
}

// Dynamic Programming function to calculate the number of shortest paths
// from (0,0) to (H,W) for a given subset of friends allowed to pass (represented by mask).
// Friends whose corresponding bit in 'mask' is 1 are passable. Others are obstacles.
ll calculate_paths(int mask) {
    // Create a grid to mark obstacle locations. True if obstacle, false otherwise.
    vector<vector<bool>> is_obstacle(H + 1, vector<bool>(W + 1, false));
    for (int i = 0; i < K; ++i) {
        // If the i-th bit in the mask is 0, this friend is NOT given a bun and acts as an obstacle.
        if (!((mask >> i) & 1)) {
             // Mark the friend's location as an obstacle
             // The problem guarantees friend coordinates are within grid bounds [0,H] x [0,W]
             is_obstacle[friends[i].x][friends[i].y] = true;
        }
    }

    // DP table: dp[x][y] will store the number of shortest paths from (0,0) to (x,y)
    vector<vector<ll>> dp(H + 1, vector<ll>(W + 1, 0));

    // Base case: The starting point (0,0).
    // The problem states (0,0) is never an obstacle location.
    if (is_obstacle[0][0]) return 0; // Safety check: if start is blocked, 0 paths.
    dp[0][0] = 1; // There is one way to be at the start: just be there.

    // Fill the DP table iteratively
    for (int x = 0; x <= H; ++x) {
        for (int y = 0; y <= W; ++y) {
            
            // If the current cell (x,y) is an obstacle, no paths can go through it.
            if (is_obstacle[x][y]) {
                dp[x][y] = 0; // Ensure dp value is 0 for obstacles
                continue; // Skip calculation for this cell, paths cannot terminate or pass through here.
            }

            // For non-obstacle cells, calculate paths reaching it.
            // Paths can only come from the West (x-1, y) or South (x, y-1).
            
            // Add paths coming from West (moving East to reach (x,y))
            if (x > 0) {
                 // We add dp[x-1][y] because any path to (x-1,y) can be extended East to (x,y).
                 // No need to check if (x-1, y) is obstacle, as if it were, dp[x-1][y] would be 0.
                 dp[x][y] = (dp[x][y] + dp[x-1][y]) % MOD; 
            }

            // Add paths coming from South (moving North to reach (x,y))
            if (y > 0) {
                 // Similarly, add dp[x][y-1]
                 dp[x][y] = (dp[x][y] + dp[x][y-1]) % MOD;
            }
            // Note: The base case dp[0][0]=1 is correctly handled. dp[1][0] will get value from dp[0][0],
            // dp[0][1] will get value from dp[0][0]. dp[1][1] will get value from dp[0][1] and dp[1][0].
        }
    }

    // The final answer for this mask is the number of paths to the destination (H, W).
    return dp[H][W];
}


int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input values: grid dimensions H, W, number of friends K, number of buns P
    cin >> H >> W >> K >> P;

    // Read friend data: coordinates (x,y) and name for each friend
    friends.resize(K);
    for (int i = 0; i < K; ++i) {
        cin >> friends[i].x >> friends[i].y >> friends[i].name;
    }

    ll max_paths = -1; // Initialize max_paths to -1 to track the maximum paths found so far.
                       // -1 helps distinguish between 0 paths and initial state.
    int best_mask = -1; // Initialize best_mask to -1, stores the mask yielding max_paths.

    // Iterate through all possible subsets of friends using bitmasks from 0 to 2^K - 1
    for (int mask = 0; mask < (1 << K); ++mask) {
        // A subset is valid if the number of friends chosen (number of set bits) is at most P.
        if (countSetBits(mask) <= P) {
            // Calculate the number of shortest paths for the current subset choice.
            ll current_paths = calculate_paths(mask);
            
            // If the number of paths for this subset is greater than the current maximum found:
            if (current_paths > max_paths) {
                max_paths = current_paths; // Update the maximum path count.
                best_mask = mask;         // Update the mask that achieved this maximum.
            }
        }
    }
    
    // --- Output Results ---

    // If max_paths is still -1 (should technically not happen for H, W >= 1 as (0,0) is reachable)
    // or if max_paths is 0, it means the destination (H,W) is unreachable for all valid subsets.
    // In this case, output 0 as required.
    if (max_paths <= 0) { 
        cout << 0 << endl; 
    } else {
        // Otherwise, output the maximum number of paths found.
        cout << max_paths << endl;
        
        // Then, output the names of the friends corresponding to the set bits in the best_mask.
        // Iterate through friends based on their original input order (index i).
        for (int i = 0; i < K; ++i) {
           // Check if the i-th bit is set in the best_mask.
           if ((best_mask >> i) & 1) {
               // If set, this friend was given a bun in the optimal solution. Print their name.
               cout << friends[i].name << endl;
           }
        }
    }
    
    // The problem statement asks for a final newline. Standard output with `endl` handles newlines after each print.
    // No extra blank line is typically needed unless explicitly specified.

    return 0; // Indicate successful execution
}