No.3329 Only the Rightest Choice is Right!!!
タグ : / 解いたユーザー数 36
作問者 :
elphe
/ テスター :
高橋ゆに
hirayuu_yc
Andrew8128
👑 
loop0919
DeltaStruct
bolero
のらら
kazuppa
こめだわら
よには
yimiya（いみや）
問題文
岩井星人さんは $N$ 個のアクリルスタンドを所有しており、ハチマキに差し込んで使います。
各アクリルスタンドについて、ハチマキに差し込む位置が決まっており、差し込む位置が左であるものから順に $1, 2, \cdots, N$ の番号がついています。
番号 $i$ のアクリルスタンドのご利益は $v_i$ で、重量は $w_i$ です。
岩井星人さんはハチマキにアクリルスタンドを複数差し込むことでご利益を重ね掛けすることができますが、岩井星人さんの頭部の耐荷重は $W$ なので重量の合計が $W$ を超えてアクリルスタンドを差し込むことはできません。
岩井星人さんは次回のABCで高パフォーマンス値とAmazonギフト券を恵んでもらうために、重量の合計が $W$ を超えない範囲でご利益の合計が最大になるようにアクリルスタンドを $1$ 体以上選んでハチマキに差し込もうとしています。
岩井星人さんは自身の開発した画期的なアルゴリズム「動的計画法」を駆使して、重量の合計が $W$ を超えない範囲でのご利益の合計の最大値を求めようとしましたが、それを達成するアクリルスタンドの差し方は複数存在しうることに気づきました。
そのようなとき、岩井星人さんは「より右に偏っている」差し方を好みます。
アクリルスタンドの差し方は、差し込むアクリルスタンドの番号を昇順に並べた正整数列によって表現され、またこれによって区別されます。
ここで、ある差し方が他の差し方より右に偏っているとは、前者の差し方を表現した正整数列が後者の差し方を表現した正整数列よりも辞書順で大きいことと定義します。
岩井星人さんのために、重量の合計が $W$ を超えない範囲でアクリルスタンドのご利益の合計を最大にする差し方のうち、「最も右に偏っている」差し方を出力してください。なお、そのような差し方がただ $1$ つ存在することが証明できます。
有限長の正整数列が辞書順で大きいとは？
長さ $k$ の正整数列 $(p_1, p_2, \cdots, p_k)$ が、長さ $\ell$ の正整数列 $(q_1, q_2, \cdots, q_\ell)$ よりも辞書順で大きいとは、下記のいずれかを満たすことと同値です。- $1 \leq i \leq \mathrm{min}(k,\ell)$ を満たすある整数 $i$ が存在し、以下の両方がともに成り立つ。
- $1 \leq j < i$ を満たすすべての整数 $j$ について $p_j = q_j$
- $p_i > q_i$
- $1 \leq i \leq \mathrm{min}(k,\ell)$ を満たすすべての整数 $i$ について $p_i = q_i$ であり、かつ $k > \ell$
制約
- $1 \leq N \leq 3000$
- $1 \leq W \leq 3000$
- $1 \leq v_i \leq 10^5$
- $1 \leq w_i \leq W$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。$N$ $W$ $v_1$ $v_2$ $\cdots$ $v_N$ $w_1$ $w_2$ $\cdots$ $w_N$
出力
$2$ 行出力せよ。
$1$ 行目には、差し込むアクリルスタンドの個数を出力せよ。
$2$ 行目には、差し込むアクリルスタンドの番号を昇順に空白区切りで出力せよ。
サンプル
サンプル1
入力
4 5 1 4 2 3 1 4 2 3
出力
2 3 4
達成可能なご利益の合計の最大値は $5$ です。
これを達成するアクリルスタンドの差し方は $( 1, 2 ), ( 3, 4 )$ の $2$ 通りありますが、このうち最も右に偏った選び方は $( 3, 4 )$ です。
サンプル2
入力
6 3000 1 1 1 1 1 1 3000 3000 3000 3000 3000 3000
出力
1 6
このケースでは、岩井星人さんは何故かご利益 $1$, 重量 $3$ キロのアクリルスタンドを $6$ 体所持しています。
岩井星人さんの頭では精々 $1$ 体が限界なので、最も右の番号 $6$ のアクリルスタンドのみが差し込まれます。
サンプル3
入力
10 3000 2992 3000 1 1 1 1 1 1 1 1 2992 3000 1 1 1 1 1 1 1 1
出力
1 2
達成可能なご利益の最大値は $3000$ です。
これを達成するアクリルスタンドの差し方は $( 1, 3, 4, 5, 6, 7, 8, 9, 10 )$ と $( 2 )$ の $2$ 通りがありますが、このうち最も右に偏った差し方は $( 2 )$ です。
見た目では前者のほうがかなり右に偏っていますが、岩井星人さんは極端に左に偏っているアクリルスタンドが含まれることが嫌いなようです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。