No.2182 KODOKU Stone
タグ : / 解いたユーザー数 16
作問者 :
MasKoaTS
/ テスター :
👑 
potato167
Shirotsume
問題文
$1,2,\dots,N$ の番号が付いた $N$ 個の袋と中に何も入っていない $1$ 個の箱があります。
袋 $i$ $(1 \leq i \leq N)$ には $T_{i}$ 個の石が入っており、このうち $j$ $(1 \leq j \leq T_{i})$
番目の石の質量は $A_{i,j}$ です。
コアさんは、これらの袋と石と箱を用いて、$i=1,2,\dots,N$ の順に次の操作を行います。
石が $1$ 個以上入っている袋を自由に $1$ 個選び、その中の石をすべて箱の中に入れる。
次に、箱の中にある石の個数を $n$ として、これら $n$ 個の石のうち、次の条件を満たすものの中から無作為に $1$ 個選ぶ。
ただし、$x = \min(K_{i}, n)$ とする。$n$ 個の石の質量が降順に $a_{1}, a_{2}, \dots, a_{n}$ $(a_{1} \geq a_{2} \geq \cdots \geq a_{n})$ と表されるとき、自身の質量が $a_{x}$ に等しい。
その後、選んだ石以外の $n-1$ 個の石をすべて箱の中から取り出して食べる。
すべての $i$ に対して操作を終了した後、箱の中に残るただ $1$ 個の石の質量としてあり得るものの最大値を求めてください。
制約
$1 \leq N \leq 10^{5}$
$1 \leq T_{i} \leq 10^{5}$ $(1 \leq i \leq N)$
$T_{1}, T_{2}, \dots, T_{N}$ の総和は $10^{5}$ 以下
$1 \leq A_{i,j} \leq 10^{9}$ $(1 \leq i \leq N \text{ かつ } 1 \leq j \leq T_{i})$
$1 \leq K_{i} \leq 3 \times 10^{5}$ $(1 \leq i \leq N)$
入力はすべて整数
入力
入力は次の形式で与えられます。
$N$
$K_{1}$ $K_{2}$ $\cdots$ $K_{N}$
$T_{1}$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,T_{1}}$
$T_{2}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,T_{2}}$
$\vdots$
$T_{N}$
$A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,T_{N}}$
$1$ 行目には $N$ が与えられる
$2$ 行目には $K_{1}, K_{2}, \dots, K_{N}$ がこの順に半角スペース区切りで与えられる
$2 i + 1$ $(1 \leq i \leq N)$ 行目には $T_{i}$ が与えられる
$2 i + 2$ $(1 \leq i \leq N)$ 行目には $A_{i,1}, A_{i,2}, \dots, A_{i,T_{i}}$ がこの順に半角スペース区切りで与えられる
出力
答えを $1$ 行に出力してください。
サンプル
サンプル1
入力
3 3 1 2 2 1 2 5 7 9 5 3 9 4 10 8 6 4
出力
9
例えば次の操作を考えることにより、最終的に質量 $9$ の石のみが箱の中に残ります。
袋 $1$ を選び、その中にある $2$ 個の石を箱の中に入れる。
$x = \min(3,2) = 2$, $(a_{1}, a_{2}) = (2, 1)$ であり、箱の中にある $2$ 個の石のうち質量が $a_{2} = 1$ であるものの中から
無作為に $1$ 個を選ぶ。そして、選んだ $1$ 個以外の $1$ 個をすべて箱の中から取り出して食べる。
このとき、質量 $1$ の石が箱の中に残る。袋 $2$ を選び、その中にある $5$ 個の石を箱の中に入れる。
$x = \min(1,6) = 1$, $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}) = (9, 9, 7, 5, 3, 1)$ であり、箱の中にある $6$ 個の石のうち質量が
$a_{1} = 9$ であるものの中から無作為に $1$ 個を選ぶ。そして、選んだ $1$ 個以外の $5$ 個をすべて箱の中から取り出して食べる。
このとき、質量 $9$ の石が箱の中に残る。袋 $3$ を選び、その中にある $4$ 個の石を箱の中に入れる。
$x = \min(2,5) = 2$, $(a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) = (10, 9, 8, 6, 4)$ であり、箱の中にある $5$ 個の石のうち質量が
$a_{2} = 9$ であるものの中から無作為に $1$ 個を選ぶ。そして、選んだ $1$ 個以外の $4$ 個をすべて箱の中から取り出して食べる。
このとき、質量 $9$ の石が箱の中に残る。
質量が $9$ より大きい石を箱の中に残すことはできません。
サンプル2
入力
5 2 2 2 1 2 1 1 1 10 1 100 1 1000 1 10000
出力
1000
サンプル3
入力
9 4 2 10 7 3 300000 7 1 5 5 7 1433 233 441445814 14 8 84906649 75121583 12 603415 10147 199004 65221 151278232 7 129002 468 235 250 1144 38994 1070804 10 122230317 19048460 168635 817 24296790 17 6404 49328 194386 61986 5 18 11 408 1 2 1 7 10 339112 57 159599 209673 234036624 277265898 34115930 17787 13825 20151 9 16 2337 557 185983 823 47160 712213 20538 100 3 829 10 9307
出力
603415
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。