AtCoder ABC 172 反省 - プログラミング関連の記録

atcoder.jp

結果

A, B, D 問題は AC した。C 問題は解けず。E, F 問題は見たけど解けそうにないと思ってすぐにあきらめた（前回よりほんの少し成長？）。

感想

コンテスト後に Twitter を眺めていたところ、C 問題は「しゃくとり法」というやつで解けることが分かった。Twitter は便利だな。

C 問題復習

問題概要

A, B 2つの机の上にそれぞれ $N, M$ 冊の本が乗っている。それぞれの本は読むのに $A_1,\cdots,A_N, B_1,\cdots,B_M$ 分かかる。

本が乗っている机を選び、一番上の本を読む。読み終わった本を机から取り除く。

という行為を繰り返すとき、 $K$ 分以内に読める本の最大の冊数を求めよ。

解き方

「しゃくとり法」というやつを使うらしい。しゃくとり法一般について詳しいことはわからないが、この問題の場合に限ってしゃくとり法による解法をまとめてみようと思う。
この問題は机 A から本を $i$ 冊、机 B から本を $j$ 冊読むとして、所要時間が $K$ 分を超えない範囲で $i+j$ の最大値を求める問題ということができる。机 A から本を $i$ 冊読むのにかかる時間 $a_i$ は

$a_i=A_1+A_2+\cdots+A_i$

である。机 B についても同様である。
しゃくとり法は $a_i$ について $i$ を $0$ ～ $N$ まで昇順で全探索し、 $b_j$ についてはそれぞれの $i$ に関して $j$ を $M$ から降順に探索することで $i+j$ をどんどん更新していく。 $i+j$ は $K$ 以下なので、 $a_i>K$ となった場合はその時点で探索を打ち切ることができる。また、それぞれの $i$ とペアを組む $j$ は $i$ に関して単調減少なので、例えば $i=n$ とペアを組む $j$ の値が $m$ であったなら、 $i=n+1$ に対しては $j=m$ から探索を始めればよい。
しゃくとり法の計算量等について詳しいことはこれから調べようと思う。

ACしたコード

#include<bits/stdc++.h>
using namespace std;

int main(){
  int64_t n,m;
  int64_t k;
  cin >>n>>m>>k;
  vector<int64_t>a(n);
  vector<int64_t>b(m);
  vector<int64_t>as(n+1,0);
  vector<int64_t>bs(m+1,0);
  for(int64_t i=0;i<n;i++){
    cin>>a.at(i);
    as.at(i+1)=as.at(i)+a.at(i);
  }
  for(int64_t i=0;i<m;i++){
    cin>>b.at(i);
    bs.at(i+1)=bs.at(i)+b.at(i);
  }
  int64_t tmp=m;
  int64_t ans=0;
  for(int64_t i=0;i<n+1;i++){
    if(as.at(i)>k)break;
    for(int64_t j=tmp;j>=0;j--){
      if(as.at(i)+bs.at(j)<=k){
        ans=max(ans,i+j);
        tmp=j;
        break;
      }
    }
  }
  cout <<ans<<endl;
}

雑記

最近プログラミングに関しては Progate の HTML & CSS の講座に時間を割いていて競プロの練習ができていない。その割に今回のコンテストでは良い結果が出てしまったので慢心しないようにしたい。