yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

東京海上日動プログラミングコンテスト2022(AtCoder Beginner Contest 256)B - Batters

問題の要約
高橋君の代わりに次の問題を解くプログラムを作成せよ。

マス0、マス1、マス2、マス3の4つのマス目がある。はじめマスの上には何もない。
また、整数Pがあり、はじめP=0である。
正の整数からなる数列A=(A1,...,AN)が与えられるので、i=1,...,Nについて順番に次の操作を行う。
 1.マス0に駒を1個置く。
 2.マス上の全ての駒を番号がAi大きいマスに進める。言い換えると、駒がマスxにあればその駒をマスx+Aiに移動する。
  ただし移動先のマスが存在しない(すなわちx+Aiが4以上になる)駒たちに関しては、それらを取り除いてPに除いた個数を加算する。
すべての操作を行った後のPの値を出力せよ。


制約
1<=N<=100
1<=Ai<=4


入力
N
A1 A2 ... AN


考え方
1,マス目が4つだけではなく、無限個あると考える。
2,1個目の駒はA1+...+AN、2個目の駒はA2+...+AN、となりN個目の駒はANとなる。
 よって、Aiをvector<int> Aで管理し、後ろの方から和を取っていけばよい。
3,すべてのAについて4以上かどうかを判定し、4以上ならPを1増やせばよい。

実際のプログラム
#include<iostream>
#include<vector>

using namespace std;

int main(){
  int N;
  cin >> N;
  
  vector<int> A(N);
  for(int i = 0; i < N; ++i){
    cin >> A[i];
  }
  
  for(int i = N-2; i >= 0; --i){
    A[i] += A[i+1];
  }
  
  int P = 0;
  for(int i = 0; i < N; ++i){
    if(A[i] >= 4){
      ++P;
    }
  }
  
  cout << P << endl;
  
  return 0;
}