東京海上日動プログラミングコンテスト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;
}