結果
| 問題 |
No.9 モンスターのレベル上げ
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:53 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 281 ms / 5,000 ms |
| コード長 | 7,947 bytes |
| コンパイル時間 | 1,068 ms |
| コンパイル使用メモリ | 86,320 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:02:13 |
| 合計ジャッジ時間 | 4,567 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 20 |
ソースコード
#include <iostream> // For input/output operations
#include <vector> // For using dynamic arrays (vectors)
#include <queue> // For using priority queue
#include <numeric> // Potentially useful for some operations, though not used here
#include <algorithm> // For std::max and std::min functions
// Use a type alias for long long to handle potentially large monster levels.
using ll = long long;
// Define a structure to hold the state of a monster.
// This structure will be used in the priority queue to manage monster selection.
struct MonsterState {
ll level; // Current level of the monster
int fight_count; // Number of times this monster has fought so far in the simulation
int id; // Original 0-based index of the monster, used as a final tie-breaker
int has_fought_flag; // A helper flag: 0 if fight_count is 0, 1 otherwise. Used to prioritize monsters that haven't fought.
// Custom comparison logic for the priority queue.
// This defines the operator> which is used by std::priority_queue when configured with std::greater<MonsterState>.
// It determines the order of elements, effectively making the priority queue a min-heap based on these rules.
// The element for which this operator returns 'false' more often compared to others is considered 'smaller' and has higher priority.
bool operator>(const MonsterState& other) const {
// Rule 1: Prioritize minimum level.
if (level != other.level) {
return level > other.level; // Lower level is smaller (preferred). Return true if this level is greater.
}
// Rule 2 (Tiebreak 1): Prioritize monsters that haven't fought yet.
// The has_fought_flag is 0 for monsters that haven't fought, 1 otherwise.
// 0 is considered smaller (preferred) than 1.
if (has_fought_flag != other.has_fought_flag) {
// If this flag is 1 and other is 0, this is larger -> return true.
// If this flag is 0 and other is 1, this is smaller -> return false.
return has_fought_flag > other.has_fought_flag;
}
// Rule 3 (Tiebreak 2): Prioritize minimum fight count.
// This rule applies when levels are equal AND either:
// a) Both monsters haven't fought (has_fought_flag=0, fight_count=0 for both).
// b) Both monsters have fought (has_fought_flag=1 for both).
// In case a), fight counts are equal (both 0), so this check passes.
// In case b), we compare their actual fight counts.
if (fight_count != other.fight_count) {
return fight_count > other.fight_count; // Lower fight count is smaller (preferred). Return true if this count is greater.
}
// Rule 4 (Tiebreak 3): Prioritize minimum original index (ID).
// This ensures a deterministic choice when all previous criteria result in a tie.
return id > other.id; // Lower ID is smaller (preferred). Return true if this ID is greater.
}
};
int main() {
// Optimize standard C++ input/output stream operations for faster execution.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of monsters in the team and also the number of enemy monsters.
std::cin >> N;
// Read the initial levels of the N team monsters. Store in a vector of long longs.
std::vector<ll> A(N);
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// Read the levels of the N enemy monsters. Store in a vector of ints.
// Enemy levels are up to 10000, so int is sufficient.
std::vector<int> B(N);
for (int i = 0; i < N; ++i) {
std::cin >> B[i];
}
// Variable to store the minimum value found for the maximum fight count across all simulations.
// Initialize it to N + 1, a value guaranteed to be larger than any possible maximum fight count (which is at most N).
int min_max_fights = N + 1;
// Iterate through all N possible starting positions for fighting the enemy monsters.
// start_idx represents the index of the first enemy monster to fight.
for (int start_idx = 0; start_idx < N; ++start_idx) {
// Set up a min-priority queue for the current simulation.
// It stores MonsterState objects and uses std::greater<MonsterState> along with the overloaded operator>
// to maintain min-heap property according to our custom comparison logic.
std::priority_queue<MonsterState, std::vector<MonsterState>, std::greater<MonsterState>> pq;
// Create copies of the initial states for this simulation run.
// This is important because each simulation starts from the same initial conditions.
std::vector<ll> current_levels = A; // Copy initial levels.
std::vector<int> fight_counts(N, 0); // Initialize fight counts to 0 for all monsters.
// Populate the priority queue with the initial state of each team monster.
for(int i = 0; i < N; ++i) {
// Initial state: level is A[i], fight_count is 0, id is i, has_fought_flag is 0.
pq.push({current_levels[i], 0, i, 0});
}
// Simulate the sequence of N battles against the enemy monsters.
for (int k = 0; k < N; ++k) {
// Calculate the index of the enemy monster for the k-th battle (0-indexed).
// The sequence starts at start_idx and proceeds clockwise (wraps around using modulo N).
int enemy_idx = (start_idx + k) % N;
int enemy_level = B[enemy_idx];
// Select the monster to fight: The highest priority monster is at the top of the min-priority queue.
MonsterState chosen_monster_state = pq.top();
pq.pop(); // Remove the selected monster from the queue temporarily.
int monster_id = chosen_monster_state.id; // Get the index (ID) of the chosen monster.
// Update the state of the chosen monster after the battle.
// Level increases by floor(enemy_level / 2). Integer division automatically performs floor.
// Cast enemy_level to ll before adding to potentially large current_level to be safe, although addition result would fit ll anyway.
current_levels[monster_id] += (ll)enemy_level / 2;
fight_counts[monster_id]++; // Increment the fight count for this monster.
// Determine the new has_fought_flag. It becomes 1 once the fight_count is greater than 0.
int new_has_fought_flag = (fight_counts[monster_id] == 0) ? 0 : 1;
// Insert the monster back into the priority queue with its updated state.
// The priority queue will automatically place it in the correct position based on its new state.
pq.push({current_levels[monster_id],
fight_counts[monster_id],
monster_id,
new_has_fought_flag});
}
// After completing all N battles for the current starting position:
// Find the maximum fight count among all team monsters during this simulation run.
int current_max_fights = 0;
// Iterate through the final fight counts of all monsters.
for (int count : fight_counts) {
current_max_fights = std::max(current_max_fights, count); // Update max if current count is higher.
}
// Update the overall minimum maximum fight count found across all starting positions tested so far.
min_max_fights = std::min(min_max_fights, current_max_fights); // Update min if current max is lower.
}
// Output the final result: the minimum possible value for the maximum number of fights any single monster had.
// The problem requires the output to be followed by a newline character.
std::cout << min_max_fights << "\n";
return 0; // Indicate successful execution.
}