問題一覧 > 通常問題

No.3329 Only the Rightest Choice is Right!!!

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 1.571秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 40
作問者 : elphe / テスター : ゆにたりー卿 hirayuu_yc Andrew8128 👑 loop0919 DeltaStruct bolero のらら kazuppa Rice_tawara459 よには yimiya(いみや)
お気に入りにしたユーザー ProblemId : 12175 / 自分の提出
問題文最終更新日: 2025-10-29 22:47:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Extra (順位表) の他の問題:

Problem Statement

Iwai Seijin owns $N$ acrylic stands, which he uses by inserting them into his headband.
Each acrylic stand has a fixed position at which it is inserted into the headband, and the stands are numbered $1, 2, \cdots, N$ in order from the leftmost insertion position.
The acrylic stand numbered $i$ has a blessing of $v_i$ and a weight of $w_i$.
By inserting multiple acrylic stands into his headband, Iwai Seijin can stack their blessings. However, his head has a load capacity of $W$, so he cannot insert acrylic stands whose total weight exceeds $W$.

In order to be granted a high performance value and an Amazon gift card in the next ABC, Iwai Seijin intends to choose $1$ or more acrylic stands and insert them into his headband so that the total blessing is maximized while the total weight does not exceed $W$.
Making full use of the groundbreaking algorithm "dynamic programming" that he himself developed, Iwai Seijin tried to find the maximum total blessing with total weight not exceeding $W$, but he noticed that there can be multiple ways of inserting acrylic stands that achieve it.
In such a case, Iwai Seijin prefers a way of insertion that is "more right-leaning".

A way of inserting acrylic stands is represented by the sequence of positive integers obtained by arranging the numbers of the inserted acrylic stands in ascending order, and ways of insertion are distinguished by this sequence.
Here, one way of insertion is defined to be more right-leaning than another if the sequence of positive integers representing the former is lexicographically larger than the sequence of positive integers representing the latter.

For Iwai Seijin, output the "most right-leaning" way of insertion among those that maximize the total blessing of the acrylic stands while the total weight does not exceed $W$. It can be proved that exactly $1$ such way of insertion exists.

What does it mean for a finite sequence of positive integers to be lexicographically larger? A sequence of positive integers $(p_1, p_2, \cdots, p_k)$ of length $k$ is lexicographically larger than a sequence of positive integers $(q_1, q_2, \cdots, q_\ell)$ of length $\ell$ if and only if at least one of the following holds.
  • There exists some integer $i$ satisfying $1 \leq i \leq \mathrm{min}(k,\ell)$ such that both of the following hold.
    • $p_j = q_j$ for all integers $j$ satisfying $1 \leq j < i$
    • $p_i > q_i$
  • $p_i = q_i$ for all integers $i$ satisfying $1 \leq i \leq \mathrm{min}(k,\ell)$, and $k > \ell$

Constraints

  • $1 \leq N \leq 3000$
  • $1 \leq W \leq 3000$
  • $1 \leq v_i \leq 10^5$
  • $1 \leq w_i \leq W$
  • All input values are integers.

Input

The input is given from standard input in the following format.
$N$ $W$
$v_1$ $v_2$ $\cdots$ $v_N$
$w_1$ $w_2$ $\cdots$ $w_N$

Output

Output $2$ lines.
On the $1$ st line, output the number of acrylic stands to insert.
On the $2$ nd line, output the numbers of the acrylic stands to insert in ascending order, separated by spaces.

Sample

Sample 1
Input
4 5
1 4 2 3
1 4 2 3
Output
2
3 4

The maximum achievable total blessing is $5$.
There are $2$ ways of inserting acrylic stands that achieve this, $( 1, 2 ), ( 3, 4 )$, and the most right-leaning choice among them is $( 3, 4 )$.

Sample 2
Input
6 3000
1 1 1 1 1 1
3000 3000 3000 3000 3000 3000
Output
1
6

In this case, Iwai Seijin for some reason owns $6$ acrylic stands, each with a blessing of $1$ and a weight of $3$ kilograms.
His head can hold at most $1$ of them, so only the rightmost acrylic stand, numbered $6$, is inserted.

Sample 3
Input
10 3000
2992 3000 1 1 1 1 1 1 1 1
2992 3000 1 1 1 1 1 1 1 1
Output
1
2

The maximum achievable blessing is $3000$.
There are $2$ ways of inserting acrylic stands that achieve this, $( 1, 3, 4, 5, 6, 7, 8, 9, 10 )$ and $( 2 )$, and the most right-leaning way of insertion among them is $( 2 )$.
In appearance the former looks far more right-leaning, but Iwai Seijin apparently dislikes including an acrylic stand that is extremely far to the left.

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