結果
| 問題 |
No.733 分身並列コーディング
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:50 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 136 ms / 1,500 ms |
| コード長 | 6,054 bytes |
| コンパイル時間 | 337 ms |
| コンパイル使用メモリ | 82,700 KB |
| 実行使用メモリ | 80,552 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:54 |
| 合計ジャッジ時間 | 6,261 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 46 |
ソースコード
import sys
# Read input faster for competitive programming
input = sys.stdin.readline
def solve():
# Read the time limit T
T = int(input())
# Read the number of problems N
N = int(input())
# Read the time required for each problem t_i
# Store them in a list t
t = [int(input()) for _ in range(N)]
# Use float('inf') as a representation for infinity. This will be used for unreachable states
# or states not yet optimally determined.
INF = float('inf')
# Initialize DP tables. We use two arrays:
# dp_people[mask] stores the minimum number of people required to complete the subset of problems represented by 'mask'.
# dp_time[mask] stores the minimum time used by the *last* person assigned tasks among those minimum people.
# The size of the DP table is 2^N, covering all possible subsets of N problems.
dp_people = [INF] * (1 << N)
dp_time = [INF] * (1 << N)
# Base case: To solve 0 problems (mask 0), we conceptually start with 1 person available,
# who has currently used 0 time. This sets up the start of the DP process.
dp_people[0] = 1
dp_time[0] = 0
# Iterate through all possible subsets of problems, represented by masks from 0 to 2^N - 1.
# The order ensures that when we compute dp for 'mask', the dp values for all smaller masks (subsets) are already computed.
for mask in range(1 << N):
# If the current state 'mask' is unreachable (dp_people[mask] is still INF),
# it means this subset cannot be formed based on previous states, so we skip it.
if dp_people[mask] == INF:
continue
# Get the current optimal state for 'mask'
current_people = dp_people[mask]
current_last_time = dp_time[mask]
# Iterate through each problem index 'i' from 0 to N-1.
for i in range(N):
# Check if problem 'i' is NOT already included in the current subset 'mask'.
# This is done by checking if the i-th bit of 'mask' is 0.
if not (mask & (1 << i)):
# If problem 'i' is not in 'mask', we can potentially add it.
# The new mask representing the subset including problem 'i' is 'next_mask'.
next_mask = mask | (1 << i)
# --- Try Option 1: Assign problem 'i' to the current last person ---
# This is only possible if adding task 'i' does not exceed the time limit T for this person.
if current_last_time + t[i] <= T:
# If valid, calculate the potential new state: same number of people, updated time for the last person.
proposed_people1 = current_people
proposed_time1 = current_last_time + t[i]
# Compare this potential state with the current best state recorded for 'next_mask'.
# Check if the proposed state is better (fewer people, or same people with less time for the last one).
current_best_people = dp_people[next_mask]
current_best_time = dp_time[next_mask]
is_proposed1_better = False
if current_best_people == INF: # If next_mask hasn't been reached optimally yet, any valid state is better.
is_proposed1_better = True
elif proposed_people1 < current_best_people: # Fewer people is always better.
is_proposed1_better = True
elif proposed_people1 == current_best_people and proposed_time1 < current_best_time: # Same people, less time is better.
is_proposed1_better = True
# If the proposed state is indeed better, update the DP table for 'next_mask'.
if is_proposed1_better:
dp_people[next_mask] = proposed_people1
dp_time[next_mask] = proposed_time1
# --- Try Option 2: Assign problem 'i' to a new person ---
# This option is always available (assuming problem constraints t[i] <= T).
# It increases the total number of people by 1.
# The new person starts with task 'i', taking t[i] time. This person becomes the new 'last person'.
proposed_people2 = current_people + 1
proposed_time2 = t[i]
# Compare this potential state with the current best state recorded for 'next_mask'.
# IMPORTANT: Read the current best state for 'next_mask' again, as it might have been updated by Option 1 just above.
current_best_people = dp_people[next_mask]
current_best_time = dp_time[next_mask]
is_proposed2_better = False
if current_best_people == INF: # If next_mask hasn't been reached optimally yet, any valid state is better.
is_proposed2_better = True
elif proposed_people2 < current_best_people: # Fewer people is always better.
is_proposed2_better = True
elif proposed_people2 == current_best_people and proposed_time2 < current_best_time: # Same people, less time is better.
is_proposed2_better = True
# If the proposed state is indeed better, update the DP table for 'next_mask'.
if is_proposed2_better:
dp_people[next_mask] = proposed_people2
dp_time[next_mask] = proposed_time2
# After iterating through all masks, the DP table is filled.
# The final answer is the minimum number of people required to complete all N problems.
# This is stored in the DP state corresponding to the mask where all bits are set (1<<N) - 1.
final_mask = (1 << N) - 1
# Print the minimum number of people required.
print(dp_people[final_mask])
# Call the main function to solve the problem
solve()