結果
| 問題 |
No.2221 Set X
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:57:44 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,514 bytes |
| コンパイル時間 | 1,100 ms |
| コンパイル使用メモリ | 89,624 KB |
| 実行使用メモリ | 14,168 KB |
| 最終ジャッジ日時 | 2025-05-14 12:59:26 |
| 合計ジャッジ時間 | 5,163 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 TLE * 1 -- * 26 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <set>
#include <algorithm>
#include <map> // Not used, but could be useful for debugging or frequency counts
// Function to calculate f(X) for a given X.
// f(X) = (X+1) * |{ floor(A_1/X), ..., floor(A_N/X) }|
// Uses std::vector, std::sort, and std::unique to find the number of distinct values.
// This approach is often faster than using std::set for large N.
long long calculate_f(long long X, int N, const std::vector<long long>& A) {
// The problem specifies X must be a positive integer.
// If X is somehow <= 0, return a value indicating error or an impossible state.
// Based on candidate generation logic, X should always be >= 1.
if (X <= 0) return -1;
// Create a vector to store the floor values floor(A_i / X).
std::vector<long long> values;
// Reserve space to potentially avoid reallocations.
values.reserve(N);
for (int i = 0; i < N; ++i) {
// Calculate floor(A[i] / X) using integer division.
values.push_back(A[i] / X);
}
// Sort the vector to bring identical elements together.
std::sort(values.begin(), values.end());
// Use std::unique to move unique elements to the front and get an iterator to the end of the unique range.
auto last = std::unique(values.begin(), values.end());
// Calculate the number of distinct elements using the distance.
long long distinct_count = std::distance(values.begin(), last);
// Calculate f(X) = (X + 1) * distinct_count.
// Check for potential overflow: Max value could be around (10^9 + 1) * 10^5 ~ 10^14.
// This fits within a 64-bit signed long long.
return (X + 1) * distinct_count;
}
int main() {
// Use fast I/O operations.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of elements in sequence A
std::cin >> N;
std::vector<long long> A(N); // Sequence A
long long max_A = 0; // Track the maximum value in A (A_N)
bool has_positive = false; // Flag to check if any element A_i > 0
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
// Update maximum value seen so far.
if (A[i] > max_A) {
max_A = A[i];
}
// Check if there is at least one positive element.
if (A[i] > 0) {
has_positive = true;
}
}
// Use a set to store candidate X values. std::set automatically handles duplicates and keeps elements sorted.
std::set<long long> candidates;
// Always consider X=1 as a candidate. f(1) = 2 * N.
candidates.insert(1);
// Consider X = max(A_i) + 1. For X > max(A_i), floor(A_i/X) = 0 for all i.
// So |S_X| = 1 (containing just 0). f(X) = X + 1.
// The minimum value in this range X > max(A_i) is at X = max_A + 1, giving f(max_A + 1) = max_A + 2.
// Add this X as a candidate only if there are positive elements in A.
// If all A_i are 0, then N=1 and A=(0). max_A = 0. In this case, X=1 is the only necessary candidate.
if (has_positive) {
candidates.insert(max_A + 1);
}
// Candidate Generation Logic:
// The value of the set S_X = { floor(A_i/X) } can change only when X passes a point A_i/k for some i and integer k >= 1.
// The function f(X) might achieve its minimum value at integers X near these critical points.
// We consider candidate X values: floor(A_i/k) and floor(A_i/k) + 1.
// This loop structure efficiently generates all distinct values of floor(A_i/k) for a fixed A_i in O(sqrt(A_i)) time.
// Total time for candidate generation across all A_i is roughly O(sum sqrt(A_i)).
for(int i=0; i<N; ++i) {
long long Ai = A[i];
// Skip A_i = 0, as floor(0/k) = 0 for all k>=1. The effect of A_i=0 is captured by considering X=1 and potentially X=max_A+1.
if (Ai == 0) continue;
// Loop through relevant k values efficiently.
// k iterates starting from 1. It represents the denominator in A_i/k.
for (long long k = 1; k <= Ai; /* k is updated inside */ ) {
// Calculate X_cand = floor(Ai/k). This is a potential candidate X.
long long X_cand = Ai / k;
// If floor(Ai/k) becomes 0, it means k > Ai. All subsequent floor(Ai/k') for k' > k will also be 0. Stop the loop.
if (X_cand == 0) break;
// Add candidate X = floor(Ai/k). Since Ai >= 1 and k <= Ai, X_cand >= 1. X_cand is always positive.
candidates.insert(X_cand);
// Add candidate X = floor(Ai/k) + 1. This is always >= 2.
candidates.insert(X_cand + 1);
// Determine the next value of k to check.
// We want to find the smallest k' > k such that floor(Ai/k') < floor(Ai/k).
// The current value floor(Ai/k) is X_cand.
// The largest k'' such that floor(Ai/k'') = X_cand is k_max = floor(Ai / X_cand).
// The smallest k' that gives a different (smaller) value is k_max + 1.
// So, the next k we should check is k_max + 1.
long long k_next_val = Ai / X_cand + 1;
// Basic sanity check: Since k <= k_max = Ai / X_cand, k_next_val = k_max + 1 should always be > k.
// Set k to k_next_val for the next iteration.
k = k_next_val;
}
}
// Variables to store the minimum f(X) found and the smallest X achieving it.
long long min_f = -1;
long long best_X = -1;
// Iterate through all generated candidate X values.
for (long long X : candidates) {
// Calculate f(X) for the current candidate X.
long long current_f = calculate_f(X, N, A);
// Check if this is the first candidate evaluated or if current_f is smaller than the minimum found so far.
if (best_X == -1 || current_f < min_f) {
min_f = current_f; // Update minimum f value.
best_X = X; // Update the best X.
} else if (current_f == min_f) {
// If current_f is equal to the minimum f value, update best_X only if the current X is smaller.
// The problem asks for the minimum X among those that achieve the minimum f value.
best_X = std::min(best_X, X);
}
}
// Output the minimum X and the minimum f(X) value.
std::cout << best_X << std::endl;
std::cout << min_f << std::endl;
return 0;
}