結果
| 問題 |
No.1211 円環はお断り
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,926 bytes |
| コンパイル時間 | 845 ms |
| コンパイル使用メモリ | 83,264 KB |
| 実行使用メモリ | 22,884 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:49 |
| 合計ジャッジ時間 | 9,342 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 37 WA * 4 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
// Define long long for potentially large sums
typedef long long ll;
// Maximum power for binary lifting. Since K <= N <= 10^5,
// ceil(log2(10^5)) is approximately 16.6. Using 20 provides a safe margin.
const int MAX_P = 20;
int N; // Number of beads
int K_int; // Number of segments/people (using int as K <= N <= 10^5)
vector<ll> A; // Bead values, using 1-based indexing A[1...N]
vector<ll> B; // Duplicated array B[1...2N-1] to handle circularity
vector<int> next_idx; // Stores the start index of the next segment for each possible start index i
vector<vector<int>> jump; // Binary lifting table: jump[p][i] stores start index after 2^p segments starting from i
// Check function: Returns true if it's possible to partition the circular arrangement
// into K contiguous segments such that the sum of values in each segment is at least X.
bool check(ll X) {
// Base case: If X is non-positive, it's always achievable since bead values A_i >= 1 and K >= 1.
if (X <= 0) return true;
// Compute next_idx using the two-pointer method.
// next_idx[i] stores the starting index of the segment immediately following
// the shortest possible segment starting at index i with sum >= X.
// Use 2*N as a sentinel value to indicate failure (cannot form a segment with sum >= X).
next_idx.assign(2 * N + 1, 2 * N); // Initialize with sentinel value
ll current_sum = 0; // Current sum of the segment window [i..j]
int j = 0; // Right pointer of the sliding window [i..j]
// Iterate through all possible start indices i from 1 to 2N-1
// B has elements B[1]...B[2N-1].
for (int i = 1; i < 2 * N; ++i) {
// When the window slides right (i increases), remove the element B[i-1] that is leaving the window.
if (i > 1) {
current_sum -= B[i - 1];
}
// Note: For i=1, the window starts empty. `current_sum` remains 0. `j` starts at 0.
// Ensure the right pointer j is at least i-1. If j fell behind i-1,
// it implies the window starting at i-1 might have been very short, possibly empty if B[i-1] >= X.
// Reset j to i-1 and current_sum to 0 if necessary. This covers the empty window [i..i-1].
if (j < i - 1) {
j = i - 1;
current_sum = 0;
}
// Extend the right pointer j until the segment sum [i..j] is at least X,
// or we reach the end of the available beads in B (index 2N-1).
// The condition `j + 1 < 2 * N` ensures we don't access B[2N]. Max index for B is 2N-1.
while (j + 1 < 2 * N && current_sum < X) {
j++; // Advance right pointer
current_sum += B[j]; // Add the new element B[j] to the sum
}
// After extending j, check if the sum requirement is met.
if (current_sum >= X) {
// If sum >= X, the segment [i..j] is valid. The next segment must start at index j+1.
next_idx[i] = j + 1;
}
// Otherwise (current_sum < X), it's impossible to form a segment starting at i with sum >= X.
// next_idx[i] remains the sentinel value 2*N indicating failure.
}
// Precompute the binary lifting table 'jump'.
// jump[p][i] will store the starting index of the segment after 2^p segments, starting from index i.
jump.assign(MAX_P, vector<int>(2 * N + 1, 2 * N)); // Initialize with sentinel value
// Base case: jump[0][i] is the start index after 1 segment (2^0 steps).
for (int i = 1; i <= 2 * N; ++i) { // Include index 2N for sentinel handling consistency
jump[0][i] = next_idx[i];
}
// The value jump[0][2N] = next_idx[2N] will be 2N because next_idx was initialized to 2N.
// Build the rest of the jump table levels using dynamic programming.
for (int p = 1; p < MAX_P; ++p) {
for (int i = 1; i <= 2 * N; ++i) { // Iterate up to include sentinel index 2N
int prev_jump_idx = jump[p - 1][i]; // Where did we land after 2^(p-1) steps?
// The next 2^(p-1) steps start from prev_jump_idx. Find where they land.
// jump[p-1][prev_jump_idx] gives the final position after another 2^(p-1) steps.
// If prev_jump_idx is already the sentinel state (2N), the state remains sentinel.
// jump[p-1][2N] is correctly handled as 2N.
jump[p][i] = jump[p - 1][prev_jump_idx];
}
}
// Check each possible starting bead index s from 1 to N on the original circle.
for (int s = 1; s <= N; ++s) {
int current_pos = s; // Start at bead s
int k_temp = K_int; // Need to take K steps (form K segments)
// Use binary lifting to find the starting position after K segments efficiently.
// Iterate through powers of 2 from largest potentially in K down to 0.
for (int p = MAX_P - 1; p >= 0; --p) {
// Check if current_pos is already in failure state before attempting jump
if (current_pos >= 2 * N) break;
// If the p-th bit of K is set, it means K includes a 2^p term.
// Take a jump of 2^p segments.
if ((k_temp >> p) & 1) {
current_pos = jump[p][current_pos];
}
}
// If current_pos reached the sentinel state, forming K segments failed for this start s.
if (current_pos >= 2 * N) {
continue; // Try the next starting position s+1
}
// If successful, current_pos is the start index of the (K+1)-th segment (denoted as s_{K+1}).
// The K-th segment ends at index end_pos_K = current_pos - 1.
int end_pos_K = current_pos - 1;
// The K segments formed greedily cover beads from index s to end_pos_K in the duplicated array B.
// The total number of beads covered is length = end_pos_K - s + 1.
// If this length is at most N, it means the K segments use at most N beads from the duplicated array.
// This corresponds to a valid partition of N distinct beads in the original circle.
// (As explained in thought process, if length < N, we can extend the last segment to cover all N beads.)
if (end_pos_K - s + 1 <= N) {
return true; // Found a feasible partition configuration. X is possible.
}
}
// If no starting position s yielded a valid partition configuration after checking all s=1..N,
// then it's impossible to achieve minimum sum X.
return false;
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K_int; // Read number of beads N and number of people/segments K
A.resize(N + 1); // Use 1-based indexing for bead values A
ll total_sum = 0; // Calculate the total sum of bead values
for (int i = 1; i <= N; ++i) {
cin >> A[i];
total_sum += A[i];
}
// Build the duplicated array B of length 2N-1 (indices 1 to 2N-1).
// This allows treating the circular arrangement linearly.
B.resize(2 * N); // Size 2N to use 1-based indexing up to 2N-1 easily
for (int i = 1; i <= N; ++i) {
B[i] = A[i];
}
for (int i = 1; i < N; ++i) { // Copy A[1..N-1] to B[N+1..2N-1]
B[N + i] = A[i];
}
// Binary search for the maximum possible minimum segment sum M.
// The possible range for M is [min(A_i), total_sum]. Since A_i >= 1, min is at least 1.
// Use range [0, total_sum + 1) for the binary search. `ans` stores the best M found so far.
ll low = 0, high = total_sum + 1, ans = 0;
while (low < high) {
// Calculate midpoint carefully to avoid overflow with large `high`.
ll mid = low + (high - low) / 2;
// Handle mid = 0 case separately. M=0 is always possible as long as K >= 1.
if (mid == 0) {
ans = max(ans, mid); // `ans` remains 0 or updates if it was negative (impossible here)
low = mid + 1; // Move search range to positive values
continue;
}
// Check if it's possible to achieve minimum sum `mid`.
if (check(mid)) {
// If 'mid' is achievable, it's a potential answer. Store it.
// Try to achieve an even larger minimum sum. Search in [mid+1, high).
ans = mid;
low = mid + 1;
} else {
// If 'mid' is not achievable, the target minimum sum is too high.
// Need to aim for a smaller minimum sum. Search in [low, mid).
high = mid;
}
}
// After the binary search loop terminates (low == high),
// `ans` holds the largest value `mid` for which `check(mid)` returned true.
// This is the maximum possible minimum segment sum M.
cout << ans << endl;
return 0;
}