Help us understand the problem. What is going on with this article?

【問題編】数列の左からの和がK以上となる最小の添字は?

More than 3 years have passed since last update.

はじめに

この記事は、競技プログラミング形式の問題を通じて、典型的なアルゴリズムに対する理解を深めるという目的で書かれたものです。
簡単なテストケースも用意してあるので、実際にコードを書いて正しく動くか確認してもらうことができます。
記事は「問題編」「解答編」に分かれています。
今回の問題編では問題を出題します。

今回の難易度はyukicoder☆2程度だと思います。
解法がすぐに思いついてしまったという人は他の解法も考えてみてください。
筆者は少なくとも2通りの解法を想定しています。

問題文

N個の非負整数からなる数列a_1, a_2, ..., a_Nがあります。
今からQ個のクエリが飛んできます。
i番目のクエリは「数列の左からの和がK_i以上となる最小の添字は?」という質問です。
すなわち「a_1 + a_2 + ... + a_p >= K_i となる最小のpを求めよ」というものです。
各クエリに対し、その答えを出力してください。
もし条件を満たすpが存在しない場合、-1を出力してください。

制約

以下の値はすべて整数である。
1 <= N <= 10^5
1 <= Q <= 10^5
0 <= a_i <= 10^9
0 <= K_i <= 10^18

入力

入力は複数のテストケースからなる。
1つのテストケースは以下の形式で与えられる。
N Q
a_1 a_2 ... a_N
K_1
K_2
...
K_Q
入力の終わりは2つの0(スペース区切り)によって表される。

出力

各テストケースごとに解答を出力する。
各テストケースに対し、出力はQ行からなる。
そのうちi行目にはi番目のクエリに対する答えを出力せよ。

サンプル

---入力---
6 6
2 4 0 5 5 1
10
17
18
0
6
6
1 3
5
4
5
6
0 0

---出力---
4
6
-1
1
2
2
1
1
-1

解答方法

ここからテストケースの入力ファイルと出力ファイルをzipでダウンロードできます(ランダム生成なのでコーナーケース等は考えていませんが、だいたいのチェックに使ってください。)
フォルダの中身は以下の通りです。
* in-small.txt
* out-small.txt
* in-large.txt
* out-large.txt
入力ファイルは"in-"です。smallは N, Q <= 10, a_i <= 10, K_i <= 100 を満たします(デバッグ用です)。

自分のコードがあっているかどうかは次の手順で判定できます。
1. 入力ファイルを自分の書いたコードにかませ、出力を生成する
2. 自分の出力と"out-"とのdiffを取る
3. 差がなければAC!

目標実行時間はC++で2秒です。

解答編は近日公開します。

yurahuna
競プロやアルゴリズムに興味があります.
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした