zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。
これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC172-C「Tsundoku」です。
ポイント
非常に良い問題でした。$N$と$M$が$10^5$オーダなので，全探索を行うと$O(NM)=O(10^{10})$となり間に合いません。そこで，$N$について全探索を行いながら，$M$の探索方法を工夫します。大きく分けて方針は2つあります。
- 尺取り法
- 二分探索
まず，両手法とも対象とするデータが昇順になっている前提があります。そこで，今回の場合は累積和を考えることで昇順のデータを利用することができます。尺取り法や二分探索と累積和の相性は抜群なのでおさえておきましょう。
zuka思考過程としては
「全探索間に合わん」
「ほんなら工夫するしかないか」
「尺取り法か二分探索が有名やね」
「両手法とも昇順データが前提やった」
「累積和使えば昇順データ作れる」
「累積和×尺取り法(or 二分探索)でいこか」
って感じです。
尺取り法は，片方を昇順で探索し，もう片方を降順で探索することで探索時間を削減する方法です。今回の例で言えば，累積和をとった配列に対して机Aから何冊読めるかを表す$i$を昇順，机Bから何冊読めるかを表す$j$を降順で調べます。ポイントは降順で調べる$j$で，$j$のスタートポイントを前回の探索時の最終地点とすることができます。なぜなら，$i$は昇順で調べられているため，$i$が増えると$j$は必ず減るからです。
二分探索に関しては，以下の記事をご覧ください。
累積和を用いた昇順データの作成
全探索を尺取り法・二分探索で工夫する
実装（尺取り法）
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N, M;
ll K;
ll A[200010];
ll B[200010];
int main(){
cin >> N >> M >> K;
// 0インデックスには何も読まない0という初期値をそのまま入れておく
rep(i, N) cin >> A[i+1];
rep(i, M) cin >> B[i+1];
// 累積和の計算
rep(i, N) A[i+1] += A[i];
rep(i, M) B[i+1] += B[i];
int ans = 0;
// cnt_bは尺取り法の降順の方
int cnt_b = M;
// cnt_aは尺取り法の昇順の方
rep(cnt_a, N+1){
// もしAだけで条件を満たさない場合はスキップ
if (A[cnt_a] > K) continue;
// 条件を満たすまでbを減らしていく(次のループは更新されたcnt_bから始まるので計算量削減)
while (A[cnt_a] + B[cnt_b] > K){
cnt_b--;
}
ans = max(ans, cnt_a + cnt_b);
}
cout << ans << endl;
}実装（二分探索）
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;
int N, M;
ll K;
ll A[200010];
ll B[200010];
// 今回の問題の条件を判定する関数
bool is_ok(int cnt_a, int mid){
return A[cnt_a] + B[mid] <= K;
}
// 二分探索を行う関数
int binary_search(int cnt_a) {
int left = 0; // 配列の左端(leftは条件を満たす最大のインデックス)
int right = M+1; // 配列の右端(rightは条件を満たさない最小のインデックス)
// 両端の差が1になるまで続ける
while (right - left > 1){
int mid = left + (right - left) / 2; // 区間の真ん中
if (is_ok(cnt_a, mid)) left = mid; // もし調べている対象が「is_okの条件」に当てはまればleftをmidまで移動
else right = mid; // 当てはまらなければrightをmidまで移動
}
return left;
}
int main(){
cin >> N >> M >> K;
// 0インデックスには何も読まない0という初期値をそのまま入れておく
rep(i, N) cin >> A[i+1];
rep(i, M) cin >> B[i+1];
rep(i, N) A[i+1] += A[i];
rep(i, M) B[i+1] += B[i];
int ans = 0;
// cnt_bは二分探索を行う対象
int cnt_b;
// cnt_aに関しては全探索
rep(cnt_a, N+1){
// もしAだけで条件を満たさない場合はスキップ
if (A[cnt_a] > K) continue;
// cnt_bは二分探索によって求める
cnt_b = binary_search(cnt_a);
ans = max(ans, cnt_a + cnt_b);
}
cout << ans << endl;
}
コメント