結果
| 問題 |
No.1538 引きこもりさんは引き算が得意。
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,999 bytes |
| コンパイル時間 | 949 ms |
| コンパイル使用メモリ | 105,916 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:38 |
| 合計ジャッジ時間 | 2,833 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 WA * 8 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric> // Required for std::gcd (available since C++17)
#include <cmath> // Required for std::abs
#include <unordered_map>
#include <vector> // Make sure vector header is included
// Function to compute the greatest common divisor (GCD) of two numbers.
// Handles negative inputs by taking absolute values first.
// Relies on std::gcd available since C++17.
// If using an older standard, a custom implementation like Euclidean algorithm would be needed.
/*
long long custom_gcd(long long a, long long b) {
a = std::abs(a);
b = std::abs(b);
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
*/
// Function to compute GCD of all elements in a vector A.
// Handles potential 0 values correctly. The GCD of a set containing 0 and some non-zero numbers
// is the GCD of the non-zero numbers. GCD involving only 0 is 0.
long long calculate_vec_gcd(const std::vector<long long>& A) {
if (A.empty()) {
return 0; // Define GCD of empty set as 0
}
long long res = 0;
for (long long x : A) {
// std::gcd(a, 0) returns std::abs(a). This property helps compute GCD correctly.
// It effectively initializes `res` with the absolute value of the first non-zero element
// and then computes GCD iteratively.
res = std::gcd(res, std::abs(x));
}
// If all elements in A are 0, the result will be 0.
// Otherwise, it's the GCD of the absolute values of the non-zero elements.
return res;
}
// Global variables accessible by DFS functions
std::vector<long long> A; // Stores the input array A
int N; // Number of elements in A
long long K; // The target value K
int N1; // Size of the first half of A (N / 2)
// map_L stores sums generated from the first half of A (indices 0 to N1-1).
// Key: a possible sum value.
// Value: a boolean flag. `true` if this sum can ONLY be formed using all zero coefficients
// (this is only possible if the sum itself is 0). `false` if this sum can be formed using
// at least one non-zero coefficient (+1 or -1).
std::unordered_map<long long, bool> map_L;
bool found = false; // Global flag set to true once a valid representation of K is found
// Depth First Search function to generate sums for the first half of array A.
// index: current element index being considered (from 0 up to N1-1).
// current_sum: the sum accumulated so far along the current path.
// all_zeros: boolean flag, true if all coefficients used so far on this path are 0.
void generate_sums_L(int index, long long current_sum, bool all_zeros) {
// Base case: If we have considered all elements in the first half
if (index == N1) {
// Check if this sum is already in the map
auto it = map_L.find(current_sum);
if (it == map_L.end()) {
// If this sum value is encountered for the first time, insert it with its all_zeros flag.
map_L[current_sum] = all_zeros;
} else {
// If this sum value already exists, update its flag.
// The flag remains true only if BOTH the existing ways AND this new way use all_zeros.
// If *any* path generating this sum used non-zero coefficients, the flag becomes false.
it->second = it->second && all_zeros;
}
return; // End this path of recursion
}
// Recursive calls for the next index (index + 1):
// Option 1: Use coefficient 0 for A[index]. The 'all_zeros' state doesn't change.
generate_sums_L(index + 1, current_sum, all_zeros);
// Option 2: Use coefficient +1 for A[index]. This path now uses a non-zero coefficient.
generate_sums_L(index + 1, current_sum + A[index], false);
// Option 3: Use coefficient -1 for A[index]. This path also uses a non-zero coefficient.
generate_sums_L(index + 1, current_sum - A[index], false);
}
// Depth First Search function to generate sums for the second half of array A and check for matches.
// index: current element index being considered (from N1 up to N-1).
// current_sum: the sum accumulated so far for the second half along the current path.
// all_zeros_R: boolean flag, true if all coefficients used so far in the second half on this path are 0.
void generate_sums_R(int index, long long current_sum, bool all_zeros_R) {
// Optimization: If a solution has already been found, stop exploring further paths.
if (found) return;
// Base case: If we have considered all elements in the second half (reached index N)
if (index == N) {
// Calculate the required sum from the first half to achieve the target K
long long target_sum = K - current_sum;
// Check if this required sum (target_sum) exists in the map generated from the first half
auto it = map_L.find(target_sum);
if (it != map_L.end()) {
// If target_sum exists in map_L, get its associated all_zeros flag.
bool all_zeros_L = it->second;
// A representation K = S1 + S2 is valid if it uses at least one non-zero coefficient overall.
// This condition is met if NOT (both S1 came from all_zeros=true AND S2 came from all_zeros_R=true).
// Equivalent to: at least one of them came from a path with non-zero coefficients.
if (!all_zeros_L || !all_zeros_R) {
found = true; // Mark that a valid solution is found
}
}
return; // End this path of recursion
}
// Recursive calls for the next index (index + 1) in the second half:
// Option 1: Use coefficient 0 for A[index]. The 'all_zeros_R' state remains the same.
generate_sums_R(index + 1, current_sum, all_zeros_R);
if (found) return; // Optimization check after recursive call returns
// Option 2: Use coefficient +1 for A[index]. Sets 'all_zeros_R' to false for this path.
generate_sums_R(index + 1, current_sum + A[index], false);
if (found) return; // Optimization check
// Option 3: Use coefficient -1 for A[index]. Sets 'all_zeros_R' to false for this path.
generate_sums_R(index + 1, current_sum - A[index], false);
// No need to check 'found' after the last recursive call in the function body, it's checked at the top.
}
int main() {
// Use faster I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read problem input N and K
std::cin >> N >> K;
A.resize(N);
bool all_input_elements_are_zero = true; // Flag to track if all A[i] are 0
// Read the N integers into vector A
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
if (A[i] != 0) {
all_input_elements_are_zero = false; // Set flag to false if any non-zero element found
}
}
// Handle the edge case where all input numbers A[i] are 0.
if (all_input_elements_are_zero) {
// If all A_i are 0, any linear combination $\sum c_i A_i$ results in 0.
// The only value possible is 0.
if (K == 0) {
// We can achieve K=0. E.g., take A_1 with coefficient +1. The sum is 1*0=0. The subset {1} is non-empty.
std::cout << "Yes" << std::endl;
} else {
// If K is non-zero, it's impossible to achieve it from only zeros.
std::cout << "No" << std::endl;
}
return 0; // Exit program after handling this edge case
}
// Calculate the GCD of the absolute values of all elements in A.
long long common_divisor = calculate_vec_gcd(A);
// Apply the necessary condition based on GCD.
// Any achievable number must be divisible by the GCD of the initial numbers.
// This check is only meaningful if common_divisor is not 0 (i.e., not all A_i are 0).
if (common_divisor != 0) {
// If K is not divisible by the common_divisor, it's impossible to form K.
if (K % common_divisor != 0) {
std::cout << "No" << std::endl;
return 0; // Exit program
}
}
// Note: If common_divisor is 0, it means all A_i are 0, which was already handled.
// Proceed with the Meet-in-the-Middle approach.
N1 = N / 2; // Define the split point: first half has N1 elements (0..N1-1)
// Phase 1: Generate all possible sums for the first half and store results in map_L.
generate_sums_L(0, 0, true); // Start DFS from index 0, initial sum 0, initially all_zeros is true.
// Phase 2: Generate sums for the second half and check against map_L if K can be formed.
// Start DFS for the second half from index N1, initial sum 0, initially all_zeros_R is true.
generate_sums_R(N1, 0, true);
// After exploring possibilities, output the final result based on the 'found' flag.
if (found) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
return 0; // Indicate successful execution
}