ABC172に参加してみた - インフラエンジニアの備忘録とか色々

初めに

ABC172もAB完でした。今回はそもそも参加が遅れてしまい
そのせいもありレートが結構下がったのでかなりテンションが下がりました。。。
くよくよせず今回もC問題について書いて行きます！

https://atcoder.jp/contests/abc172

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Tsundoku

この問題は、机A,B上に積まれている本を決められた時間内に最大で何冊読めるか求める問題です。
それぞれの本を読むために掛かる時間は設定されており、本は上から順番に読むことが出来ます。

上にある本を読む時間が小さいものから順々に読んで行けばええんやない？と考えて
その方針で解こうと思い実装しサンプル通ったんでイケそう！と思いましたが、
WA出しまくって解けませんでした。。。

解説を見たところ今回の問題の解き方は2パターンあるそうなので両方実装しました。

解説を見てからの回答①

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

ll N,M,K;
ll ans = -1;

cin >> N >> M >> K;

vector<ll> A(N);
vector<ll> B(M);

for(ll i = 0;i < N;++i) cin >> A[i];
for(ll j = 0;j < M;++j) cin >> B[j];

// 累積和を格納するための配列
vector<ll> sumA(N+1,0);
vector<ll> sumB(M+1,0);

// 累積和を計算し配列に格納
for(ll i = 0;i < N;++i) sumA[i+1] = sumA[i] + A[i];
for(ll i = 0;i < M;++i) sumB[i+1] = sumB[i] + B[i];

for(ll i = 0;i <= N;++i){

// 机Aからi冊読んだ時に残っている時間
ll t = K - sumA[i];

// 机Bから本を読み時間が無くなったらループを抜ける
if(t < 0) break;
  
  // 2分探索用の変数(机Bに積んである本で2分探索)
  ll left = 0;
  ll right = M+1;
  ll mid = 0;

  while(right - left > 1){

    // left と rightの中間地の計算
    mid = (left + right)/2;

    // 中間地よりも大きかった場合は、leftに中間地の値を格納
    if(sumB[mid] <= t) left = mid;
    // 中間地よりも小さかった場合は、rightに中間地の値を格納
    else right = mid;

  }

  // 机Aから選択したi冊と机Bから選択したleft冊の本の合計
  ll res = i + left;

  // 読み事が可能な冊数を最大値で更新
  ans = max(ans,res);

}

cout << ans << endl;

return 0;

}

1つ目は、累積和+2分探索を利用した解法です。

本を読むのに掛かる時間を愚直に2重ループで全探索を行おうとすると
N,Mがそれぞれ最大で2×10⁵のためTLEになってしまいます。
そこで本を読みのに掛かる時間の計算時間を削減するために累積和を用いています。

下記のイメージのようにあらかじめ累積和を計算しておけば、
ループの中でいちいち計算しなくても<直ぐに本を読んだ時間を求める事ができます。

f:id:hgm_blog:20200708004610p:plain — イメージ

※累積和についてはこちらを見るとお勉強になります。

累積和を何も考えずに書けるようにする！ - Qiita

求めた累積和を利用して机Aから0冊読んだ場合に机Bから何冊読めるか、
1冊読んだ場合に机Bから何冊読めるか・・・と順々に計算し、
最大で読める冊数を更新していきますが、机Bから何冊読めるかは、
累積和を求めた配列を2分探索することにより高速に求める事が可能です。

机Bの本をすべて読む際にに掛かる読書時間の累積和は既に計算しており、
配列の値はインデックスが増えるごとに単調増加することは自明なため、
2分探索を行う事が可能です。

プログラム上では探索範囲の先頭(左端)をleft,末尾(右端)をright,中間をmid、
机AからN冊読んで残った時間をtとしており、midの値がtより大きい場合はleft = midで更新、
小さい場合はright = midと更新していき探索範囲を狭めていき、
right - left > 0を満たさなくなった時のleftの値が机Bから読む事ができる本の冊数となります。

f:id:hgm_blog:20200709012317p:plain — イメージ

そして、机A・Bで読むことが可能な冊数を最大値で更新していく
ことでK以内で読める最大の冊数が求められます。

解説を見てからの回答②

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll N,M,K;
ll ans = 0;

cin >> N >> M >> K;

vector<ll> A(N);
vector<ll> B(M);

for(ll i = 0;i < N;++i) cin >> A[i];
for(ll j = 0;j < M;++j) cin >> B[j];

ll left = 0;
ll sum = 0;


for(ll i = 0;i < M;++i) sum +=  B[i];

for(ll right = M;right >= 0;--right){

  //机Aの本を読み切るかsumがKを超えるまで机Aの本を読む。
  while((sum + A[left]) <= K && left < N){

    sum += A[left];
    ++left;

  }

  // Bの本が0冊の場合はsumから本を読む時間を引き事は出来ない
  if(sum <= K && sum != 0) ans = max(ans,left + right);

  // 机Bの本を1冊も読まない場合はsumから本を読む時間を引かない
  if(right != 0) sum -= B[right - 1];

}

cout << ans << endl;

return 0;

}

2つ目は、尺取り法を利用した解法です。

尺取り法は長さのNの数列から条件を満たす区間の最大や最小を求める際に使用できる手法で、
区間の先頭(左端)をleft、末尾(右端)をrightとおきleftとrightを条件に従い移動させることで値を求めていきます。

この問題ではsumにあらかじめ机Bの本をすべて読んだ際の累積和を代入し、
机Bの本の冊数をright、机Aの本の冊数をleftとおきました

そして、机Bの本を読んだ際に掛かる読書時間を1冊分ずつsumから引いていき、
机AからK-sumの時間で読むことが可能な本の読書時間を1冊分ずつsumに足していく操作を
机Bのすべての本の読書時間を引くまで行います。
（机Bの本の読書時間を引く際にrightも引き、机Aの本の読書時間を足す際にleftも足します。)

その間に机A・Bで読むことが可能な冊数を最大値で
更新していくことでK以内で読める最大の冊数が求められます。

(下記イメージ)