最短の区間 R(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
数列 A の要素数 N と値 M , 数列 A の要素 A_1, A_2, ..., A_N が与えられます。
要素の和が M 以上となるような A の部分列の最短の長さを求めてください。
そのような部分列が存在しない場合は -1 を出力してください。
なお、数列の部分列とは、数列の連続した 1 つ以上の要素を取り出して作ることができる数列のことです。
- 入力される値
-
N M
A_1 A_2 ... A_N
・ 1 行目には、数列 A の要素数 N と、条件に使う整数 M が与えられます。
・ 2 行目には、数列 A の各要素 A_1, A_2 ... A_N が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行の出力
・ 条件を満たす最短の区間の長さ(要素数) l を 1 行で出力してください。l
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N, M ≦ 10 ^ 5
・ 0 ≦ A_i ≦ 100
- 入力例1
-
1 10
9
- 出力例1
-
-1
- 入力例2
-
10 27
16 9 2 6 18 3 1 3 6 8
- 出力例2
-
3
