結果
| 問題 |
No.1736 Princess vs. Dragoness
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 12:59:03 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,423 bytes |
| コンパイル時間 | 165 ms |
| コンパイル使用メモリ | 82,276 KB |
| 実行使用メモリ | 82,700 KB |
| 最終ジャッジ日時 | 2025-05-14 13:00:43 |
| 合計ジャッジ時間 | 9,551 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 22 WA * 7 TLE * 4 |
ソースコード
import sys
# Function to read input and solve the problem
def solve():
# Read input values: N monsters, A casts of spell A, B casts of spell B,
# X damage per spell A, Y total damage per spell B.
N, A, B, X, Y = map(int, sys.stdin.readline().split())
# Read initial health points of N monsters.
H_orig = list(map(int, sys.stdin.readline().split()))
# Ensure X and Y are treated as integers (Python handles large integers automatically).
X = int(X)
Y = int(Y)
# Helper function for ceiling division: ceil(a / b)
def ceil_div(a, b):
# Handle division by zero, though X is guaranteed >= 1.
if b == 0: return float('inf')
# If health is non-positive, no spells needed.
if a <= 0: return 0
# Standard ceiling division formula for positive integers a, b.
return (a + b - 1) // b
# Function to simulate the effect of k casts of Spell B. O(N) time complexity.
# It calculates the health points of monsters after k casts of Spell B are applied
# starting from the health state provided in current_H.
def fast_simulate_b(k, current_H):
# Create a copy of the health list to avoid modifying the input list.
H_after_B = list(current_H)
# Calculate the total damage potential from k casts of Spell B.
# This can be a large number, Python's arbitrary precision integers handle this.
total_damage_potential = k * Y
# Keep track of the remaining damage potential.
current_total_damage_potential = total_damage_potential
# Iterate through monsters in order from 1 to N.
for i in range(N):
# If monster i already has non-positive health, skip it.
if H_after_B[i] <= 0:
continue
# Determine the damage dealt to monster i. It's the minimum of its current health
# and the remaining damage potential of the spell B aggregate effect.
damage_to_deal = min(H_after_B[i], current_total_damage_potential)
# Apply the damage to monster i.
H_after_B[i] -= damage_to_deal
# Reduce the remaining damage potential.
current_total_damage_potential -= damage_to_deal
# If the total damage potential is exhausted, stop the simulation for this set of B casts.
if current_total_damage_potential == 0:
break
# Return the final health state of monsters after k Spell B casts.
return H_after_B
# Check function to determine if it's possible to win with exactly k casts of Spell B
# and at most A casts of Spell A. This uses a greedy strategy.
# The strategy is to iteratively use a Spell A cast *before* the Spell B phase
# on the monster that provides the maximum immediate benefit (reduction in total Spell A casts needed),
# as long as the benefit is positive.
def check(k):
# 'processed_H' keeps track of the monster healths after applying 'A_before' casts of Spell A.
# Initially, it's the original healths.
processed_H = list(H_orig)
A_before = 0 # Counter for Spell A casts used before the Spell B phase.
# Calculate the initial state: healths after k Spell B casts applied to 'processed_H',
# and the number of Spell A casts needed *after* this Spell B phase ('A_after').
H_after_B = fast_simulate_b(k, processed_H)
A_after = 0
for h_val in H_after_B:
A_after += ceil_div(h_val, X)
# Greedy loop: attempts to improve the situation by applying Spell A casts *before* Spell B.
# The loop runs at most A times, as each beneficial step uses one Spell A cast from the budget.
for _iter_count in range(A + 1): # Iterate at most A+1 times (covers using 0 to A 'before' spells)
# If the total number of Spell A casts required (before + after) is within budget A, we found a way. Success.
if A_before + A_after <= A:
return True
# Optimization: If we have already used A 'before' spells, we cannot use more.
# The check A_before + A_after <= A above handles the final state. Can break early.
if A_before >= A:
break
best_p = -1 # Index of the best monster to target with Spell A.
max_benefit = 0 # Maximum benefit found. Must be strictly positive to apply the spell.
# Cache the current total A spells needed for benefit calculation.
current_total_A_needed = A_before + A_after
best_p_A_after = -1 # Store the resulting A_after count if the best move is taken.
# Iterate through all monsters to find the one giving the maximum benefit if targeted by Spell A *before* B phase.
for p in range(N):
# Only consider targeting monsters that are currently alive.
if processed_H[p] <= 0 : continue
# Create a temporary health state: apply one Spell A cast on monster p.
temp_H = list(processed_H)
# Health cannot drop below 0 conceptually. Use max(0, ...) just in case.
temp_H[p] = max(0, temp_H[p] - X)
# Simulate k Spell B casts on this temporary health state.
temp_H_after_B = fast_simulate_b(k, temp_H)
# Calculate the number of Spell A casts needed *after* B for this temporary state.
temp_A_after = 0
for h_val in temp_H_after_B:
temp_A_after += ceil_div(h_val, X)
# Calculate the benefit. Benefit = Current Total A needed - New Total A needed
# New total A needed = (A_before + 1) + temp_A_after (1 is for the spell A used before B)
# Benefit = (A_before + A_after) - (A_before + 1 + temp_A_after) = A_after - temp_A_after - 1
benefit = A_after - temp_A_after - 1
# If this monster p provides a better positive benefit, update best choice.
if benefit > max_benefit:
max_benefit = benefit
best_p = p
# Store the resulting A_after count for this potential move.
best_p_A_after = temp_A_after
# If no monster provides a positive benefit (max_benefit <= 0), the greedy strategy cannot improve further. Stop.
if best_p == -1:
break
# Apply the best move permanently: Use one Spell A on monster 'best_p'.
processed_H[best_p] = max(0, processed_H[best_p] - X)
A_before += 1 # Increment the count of 'before' spells used.
# Update A_after based on the pre-calculated effect of the chosen move.
A_after = best_p_A_after
# After the greedy loop terminates, check the final condition one last time.
# This covers cases where the loop ended because no benefit was found or A limit was reached.
return A_before + A_after <= A
# Binary search for the minimum number of Spell B casts (k) required.
# We search in the range [0, B].
min_k = B + 1 # Initialize min_k to a value indicating failure (outside the valid range).
low = 0
high = B
ans_found = False # Flag to track if we have found any k that allows winning.
# Standard binary search loop.
while low <= high:
mid = (low + high) // 2 # Calculate the midpoint k value to check.
if check(mid): # If using 'mid' Spell B casts works...
min_k = mid # Record 'mid' as a potential minimum k.
ans_found = True # Mark that we found at least one working k.
high = mid - 1 # Try to find an even smaller k in the lower half.
else: # If 'mid' Spell B casts are not sufficient...
low = mid + 1 # We need more Spell B casts, so search in the upper half.
# After binary search, if ans_found is True, it means we found a valid k <= B.
if ans_found:
print("Yes")
else: # Otherwise, it's impossible to win with at most B casts of Spell B.
print("No")
# Execute the main function to solve the problem.
solve()