難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) 未投票 (0票)

投票の分布

まだ投票はありません。

  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.50票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Melting Kotatsu Cats

作成者 jammy

テスター tau0529

難易度(作成者設定) Lv.3

難易度(投票) 未投票 (0票)

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

条件に対するViV_i, DiD_iの寄与を考え条件を満たす最大のねこの数を求めます。
II :こたつに入った猫の集合, SS: ViV_iの総和(全猫の大きさの総和) 条件を式にすると以下の不等式になります。

∑i∈I(Vi+Di)≤∑j∉IVj \sum_{i \in I} (V_i + D_i) \le \sum_{j \notin I} V_j

以下の式を代入

∑j∉IVj=S−∑i∈IVi \sum_{j \notin I} V_j = S - \sum_{i \in I} V_i

∑i∈I(Vi+Di)≤S−∑i∈IVi \sum_{i \in I} (V_i + D_i) \le S - \sum_{i \in I} V_i

∑i∈I(Vi+Di)+∑i∈IVi≤S \sum_{i \in I} (V_i + D_i) + \sum_{i \in I} V_i \le S

∑i∈I(2Vi+Di)≤S \sum_{i \in I} (2V_i + D_i) \le S

コストを ci=2Vi+Dic_i = 2V_i + D_i とおくと、条件は

∑i∈Ici≤S \sum_{i \in I} c_i \le S

となります。
この条件のもとで ∣I∣|I| を最大にします。 xx 匹を選ぶとき、コストの合計が一番小さくなるのは、cic_i が小さい順に xx 匹選んだときです。なので cic_i を昇順に並べ、合計が SS を超えない範囲で前から何匹取れるかが答えになります。

ソートがあるので、計算量は O(Nlog⁡N)O(N \log N)で実装できます。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。