1. yurahuna

    Posted

    yurahuna
Changes in title
+【解答編】数列の左からの和がK以上となる最小の添字は?
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,114 @@
+問題編は[こちら](http://qiita.com/yurahuna/items/b640257f2c5b2c925a52)。
+この記事では↑の問題の解法を2通り、コードとともに紹介します。
+
+# 解法1: 累積和×二分探索
+もし N,Q が小さければ、クエリごとに毎回数列の上でループを回し、和が初めてK以上となったところで添え字を出力すればよいでしょう。これだと計算量はO(NQ)になります。しかし今回はN,Qの上限が10^5と大きいので、このアルゴリズムでは間に合いません。そこで、**累積和**と**二分探索**を用います。
+
+まず、数列aの1番目からi番目までの和(累積和)をすべて計算しておきます。
+するとa_i>=0という制約から、aの累積和は単調増加になります。
+単調性があるので二分探索ができます。
+そこでクエリごとに、ループを回すのではなく二分探索で答えを探すと、計算量はO(N + QlogN)となります。(前処理にO(N), クエリ1つにO(logN))
+
+ただしこの解法は、**a_iが非負とは限らない場合には適用できない**ことに注意してください。
+
+```cpp:nibutan.cpp
+#include <bits/stdc++.h>
+using namespace std;
+#define int long long // <-----!!!!!!!!!!!!!!!!!!!
+
+#define rep(i,n) for (int i=0;i<(n);i++)
+#define rep2(i,a,b) for (int i=(a);i<(b);i++)
+#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
+#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
+#define all(a) (a).begin(),(a).end()
+
+typedef long long ll;
+typedef pair<int, int> Pii;
+typedef tuple<int, int, int> TUPLE;
+typedef vector<int> V;
+typedef vector<V> VV;
+typedef vector<VV> VVV;
+typedef vector<vector<int>> Graph;
+// const int inf = 1e9;
+const int INF = 1e18;
+const int mod = 1e9 + 7;
+
+signed main() {
+ std::ios::sync_with_stdio(false);
+ std::cin.tie(0);
+
+ int N, Q;
+ while (cin >> N >> Q, N) {
+ vector<int> a(N + 2);
+ rep2(i, 1, N + 1) {
+ cin >> a[i];
+ a[i] += a[i - 1];
+ }
+ a[0] = -INF;
+ a.back() = INF;
+ rep(i, Q) {
+ int K;
+ cin >> K;
+ int ans = lower_bound(all(a), K) - a.begin();
+ cout << (ans == N + 1 ? -1 : ans)<< endl;
+ }
+ }
+}
+```
+
+# 解法2: クエリ先読み
+実は**クエリ先読み**をすると、**a_iが負になりうる場合にも同等の計算量で対応できます**。
+手順は以下の通りです。
+
+1. 解法1と同様に累積和をもっておく
+2. クエリをひとまずすべて読み込む。$q[id] = (K_{id}, id)$ のペアを $K_{id}$ の昇順にソートする
+3. 数列の累積和について、左からループを回す。累積和の添字を $i$, ソートされたクエリの添字を $j$ とし、答えは $ans[q[j].id] = (クエリidに対する答え)$ に記録するものとする。各 $i$ に対し、$j < Q$ かつ $a_i >= q[j].K$ 以上である限り $ans[q[j].id] = i, j++$ を繰り返す
+4. $ans$ を出力する
+
+クエリをソートすることで、Kの小さい方から順に印をつけていくことができるというわけです。
+計算量はO(N + QlogQ)となります。(前処理にO(N), クエリのソートにO(QlogQ), ↑のステップ3にO(N + Q))
+この解法は累積和の単調性を仮定していないので、a_iが非負という制約がなくても有効です。
+
+```cpp:sakiyomi.cpp
+signed main() {
+ std::ios::sync_with_stdio(false);
+ std::cin.tie(0);
+
+ int N, Q;
+ while (cin >> N >> Q, N) {
+ vector<int> a(N);
+ rep(i, N) {
+ cin >> a[i];
+ if (i != 0) a[i] += a[i - 1];
+ }
+
+ vector<Pii> queries;
+ rep(id, Q) {
+ int K;
+ cin >> K;
+ queries.emplace_back(K, id);
+ }
+ sort(all(queries));
+
+ vector<int> ans(Q, -2);
+ int j = 0;
+ rep(i, N) {
+ while (j < Q && a[i] >= queries[j].first) {
+ ans[queries[j].second] = i;
+ j++;
+ }
+ }
+
+ rep(i, Q) {
+ cout << ans[i] + 1 << endl;
+ }
+ }
+}
+```
+
+# チャレンジ問題
+さらに理解を深めるための問題です。↑の問題が解けた方は気が向いたらやってみましょう。
+
+> N頂点M辺の無向グラフGがある。頂点には0, 1, ..., N-1と番号がつけられており、各辺にはコストが与えられている。Q個のクエリq_iに対し、頂点0からの最短距離がK_i以上かつそのうちで最小であるような頂点の番号を答えよ。
+
+ご不明な点・ご指摘等あればぜひお気軽にコメントか @yurahuna まで。