問題一覧 > 通常問題

No.2700 Please Hack Greedy Solution!

レベル : / 実行時間制限 : 1ケース 0.500秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 58
作問者 : hirayuu_yc / テスター : hamamu Magentor
3 ProblemId : 10613 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-11 14:03:32

問題文

これは出力のみの課題です。

0-1ナップサック問題で、ほぼすべての場合で厳密解が貪欲解を上回ることはあるでしょうか。

正整数 N,WN,W と、正整数の組の列 ((v1,w1),(v2,w2),…,(vN,wN))((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N)) のうち、以下の条件を満たすものを一つ求めてください。

  • 1≤N≤20001\leq N\leq 2000
  • 1000≤W≤20001000\leq W\leq 2000
  • 1≤vi≤1091\leq v_i\leq 10^9
  • 1≤wi≤W1\leq w_i\leq W
  • p=1,2,…,Wp=1,2,\dots,W のうち、以下の条件を満たさない pp は多くとも 11 つ
    • {1,2,…,N}\{1,2,\dots,N\} の部分集合 SS であって ∑i∈Swi≤p\sum_{i\in S} w_i\leq p を満たすものの中で、∑i∈Svi\sum_{i\in S} v_i の最大値を RR とする。ただし、空でない SS の中で ∑i∈Swi≤p\sum_{i\in S} w_i\leq p を満たすものが存在しない場合、R=0R=0 とする。
    • ((v1,w1),(v2,w2),…,(vN,wN))((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N)) を、viwi\frac{v_i}{w_i} の大きい順（ただし、同じ場合は wiw_i の大きい順）に並び替えたものに置き換え、q=p,G=0q=p,G=0 として i=1,2,…,Ni=1,2,\dots,N の順に以下の操作を行う。
      • もし wi≤qw_i\leq q なら、q←q−wiq\gets q-w_i 、G←G+viG\gets G+v_i に置き換える。
    • このとき、RR が最終的な GG より真に大きい

入力

入力は与えられない。

出力

条件を満たす N,W,((v1,w1),(v2,w2),…,(vN,wN))N,W,((v_1,w_1),(v_2,w_2),\dots,(v_N,w_N)) を以下のように出力してください。

N WN\ W
v1 w1v_1\ w_1
v2 w2v_2\ w_2
⋮\vdots
vN wNv_N\ w_N

サンプル

サンプル1
出力
2 3
3 1
4 2

この出力は出力例を示すものであり、以下の理由で条件を満たさないため WA と判定されます。

  • 1000≤W≤20001000\leq W\leq 2000 を満たさない
  • p=1,2,…,Wp=1,2,\dots,W のうち、条件を満たさない pp は 1,31,3 の 22 つ
    • p=1p=1 のとき、R=G=3R=G=3 なので、条件を満たしません。
      • ∑i∈Swi≤p\sum_{i\in S} w_i\leq p を満たす SS は {},{1}\{\},\{1\} の 22 つで、∑i∈Svi\sum_{i\in S} v_i は SS が {1}\{1\} のときに最大の 33 になります。よって、R=3R=3 です。
      • ((v1,w1),(v2,w2))((v_1,w_1),(v_2,w_2)) をviwi\frac{v_i}{w_i} の大きいに並び替えたものである ((3,1),(4,2))((3,1),(4,2)) に置き換え、q=p,G=0q=p,G=0 とします。
        • w1≤qw_1\leq q なので、qq を q−w1=0q-w_1=0、GG を G+v1=3G+v_1=3 に置き換えます。
        • w2≤qw_2\leq q でないので、何もしません。
        • よって、最終的な GG は 33 です。
    • p=2p=2 のとき、R=4,G=3R=4,G=3 なので、条件を満たします。
      • ∑i∈Swi≤p\sum_{i\in S} w_i\leq p を満たす SS は {},{1},{2}\{\},\{1\},\{2\} の 33 つで、∑i∈Svi\sum_{i\in S} v_i は SS が {2}\{2\} のときに最大の 44 になります。よって、R=4R=4 です。
      • ((v1,w1),(v2,w2))((v_1,w_1),(v_2,w_2)) をviwi\frac{v_i}{w_i} の大きいに並び替えたものである ((3,1),(4,2))((3,1),(4,2)) に置き換え、q=p,G=0q=p,G=0 とします。
        • w1≤qw_1\leq q なので、qq を q−w1=1q-w_1=1、GG を G+v1=3G+v_1=3 に置き換えます。
        • w2≤qw_2\leq q でないので、何もしません。
        • よって、最終的な GG は 33 です。
    • p=3p=3 のとき、R=G=7R=G=7 なので、条件を満たしません。
      • ∑i∈Swi≤p\sum_{i\in S} w_i\leq p を満たす SS は {},{1},{2},{1,2}\{\},\{1\},\{2\},\{1,2\} の 44 つで、∑i∈Svi\sum_{i\in S} v_i は SS が {1,2}\{1,2\} のときに最大の 77 になります。よって、R=7R=7 です。
      • ((v1,w1),(v2,w2))((v_1,w_1),(v_2,w_2)) をviwi\frac{v_i}{w_i} の大きいに並び替えたものである ((3,1),(4,2))((3,1),(4,2)) に置き換え、q=p,G=0q=p,G=0 とします。
        • w1≤qw_1\leq q なので、qq を q−w1=2q-w_1=2、GG を G+v1=3G+v_1=3 に置き換えます。
        • w2≤qw_2\leq q なので、qq を q−w2=0q-w_2=0、GG を G+v2=7G+v_2=7 に置き換えます。
        • よって、最終的な GG は 77 です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。