1. yurahuna
Changes in body
Source | HTML | Preview
@@ -1,114 +1,104 @@
問題編は[こちら](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;
-
+const ll INF = 1e18;
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);
+ vector<ll> 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;
+ ll 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);
+ vector<ll> a(N);
rep(i, N) {
cin >> a[i];
if (i != 0) a[i] += a[i - 1];
}
- vector<Pii> queries;
+ vector<pair<ll, int>> queries;
rep(id, Q) {
- int K;
+ ll 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以上かつそのうちで最小であるような頂点の番号を答えよ。
+> N頂点M辺の無向グラフGがある。頂点には0, 1, ..., N-1と番号がつけられており、各辺にはコストが与えられている。頂点0から頂点jまでの最短距離をd_j(ただしd_0 = 0)とする。このとき、次のQ個のクエリq_iに答えよ。
+>
+> 1. $d_j \geq q_i$ かつ $|d_j - q_i|$ が最小となる $j$ (複数ある場合はそのうちで最小の $j$ )
+> 2. $d_j \geq q_i$ を満たす最小の $j$
ご不明な点・ご指摘等あればぜひお気軽にコメントか @yurahuna まで。