zukaABCをコツコツ解いていきます。
本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。
目次
本記事の概要
Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC135-C「City Savers」です。
ポイント
ややこしい問題でした。$i$番目の勇者は$i$番目の街のモンスターを全力で倒しにいけば良いことに気付いても，なかなか実装が一筋縄にはいきません。そこで，今回は多くの変数を用意してあげることで，見通しよおく操作を行うことを目指しました。変数名は日本語でかっこ悪いですが，ご勘弁ください。また，入力のオーダーに対応して変数の型をintではなくlong longなどに適宜変更することを忘れないでください。
おさえるべき内容
操作がややこしいときは複数の変数を分けて考える
実装
#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;
int main(){
int N;
cin >> N;
// long longでないと入りきらない
vector<long long> A(N+1);
vector<long long> B(N+1);
rep(i, N+1){
cin >> A[i];
}
rep(i, N){
cin >> B[i];
}
// ここから本題
// ansは倒したモンスターの数
// yoryokuは勇者が次の街で余分に倒せるモンスターの数（余力）
// gamusyaraは余力で倒せるモンスターの数（がむしゃら）
long long ans=0, yoryoku, toubatu, gamusyara;
// 最初は例外処理
toubatu = min(A[0], B[0]);
ans += toubatu;
yoryoku = B[0] - toubatu;
// 最初と最後を除いたN-1回同じ処理をする
rep(i, N-1){
// まずは余力でモンスターを倒す
gamusyara = min(A[i+1], yoryoku);
ans += gamusyara;
// 倒した分のモンスターを減らす
A[i+1] -= gamusyara;
// 次に勇者が普通にモンスターを倒す
toubatu = min(A[i+1], B[i+1]);
ans += toubatu;
// 毎回余力を更新していく
yoryoku = B[i+1] - toubatu;
}
// 最後も例外処理
// 最後の街はがむしゃらでしか倒せない
gamusyara = min(A[N], yoryoku);
ans += gamusyara;
cout << ans << endl;
}
コメント