結果

問題 No.710 チーム戦
コンテスト
ユーザー hiro5277
提出日時 2026-07-09 22:12:03
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 151 ms / 3,000 ms
コード長 2,621 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 436 ms
コンパイル使用メモリ 95,856 KB
実行使用メモリ 164,864 KB
最終ジャッジ日時 2026-07-09 22:12:11
合計ジャッジ時間 4,872 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

'''
yukicoder No207
方針: ナップザックDP(解説AC)

dp[i] = 雪男がi秒かけて、節約できる雪女の解答時間の最大値
-> 雪女の全問題を解答した場合の解答時間 = ΣBなので、ΣB-dp[i] が実際に雪女の解答時間になる
-> 全てのiについて、max(i,ΣB-dp[i])を見てその最小値が答え  // i:雪男の解答時間、ΣB-dp[i]:雪女の解答時間(最小)

------------------------
方針: ナップザックDP  -> WA

反例: 「途中時点では問題iは雪男が解くと最適だけど、最後まで見た場合問題iは雪女が解くのが最適」のようなケース
や「同じ解答時間に残したケースが間違いのケース」

dp[i][x] = 問題0,1,2,...,iまで解答して、最後に人xが解答したときに解答時間が最も短くなる時の、[雪男の解答時間, 雪女の解答時間]
*x = 雪男or雪女

入力例1:
3         最後に雪男が解答  最後に雪女が解答
45 50 ->     [45,0]          [0,50]
20 80 ->     [20,50] *1      [45,80]*2
  *1: [65,0]or[20,50]だと[20,50]のほうがよい
  *2: [45,80]or[0,130]だと[0,130]のほうがよい
40 15 ->     [60,50]         [20,65]

メモ:
  i問目まで解けた時点での最短で、i+1問目を解く際の最短を考えれる
  最後に雪男(人0)/雪女(人1)が解いたかで状態を圧縮できる（通常は最大2^100通り）

WAだがいったん提出。同じところの扱いとかダメそう。
DPの仕方を工夫すべき? ABC 204 Dみたいにすべき?
'''
# 入力
N = int(input())
A,B = [],[]
for i in range(N):
  a,b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

# DP
NONE = -float("inf")
max_times = sum(A)
# dp
prev_dp = [NONE]*(max_times+1)
dp = [NONE]*(max_times+1)
prev_dp[0] = 0
for i in range(N):
  # i問目の解答時間
  t_a = A[i]
  t_b = B[i]
  for t in range(max_times+1):
    if(prev_dp[t] == NONE):
      continue
    # i問目を雪男が解く
    dp[t+t_a] = max(prev_dp[t]+t_b, prev_dp[t+t_a])
    # i問目を雪男が解かない
    #dp[t] = prev_dp[t] # 修正前
    dp[t] = max(prev_dp[t], dp[t]) # 修正後:  すでに t0(<t)でprev_dp[t0] -> dp[t0],dp[t] の遷移があった場合、dp[t]には値が入っている可能性ありなので、dp[t]も比較対象にする 
  prev_dp = dp[:]

# 最小値を求める
ans = float("inf")
sum_times = sum(B) # 雪女が全問題解く場合の解答時間
for t in range(max_times+1):
  solve_time = max(t, sum_times-dp[t]) # 雪男の解答時間, 雪女の解答時間(最小)
  ans = min(solve_time, ans)
print(ans)
0