貪欲法というアルゴリズム があります。英語だとGreedy Algorithmです。簡単に言うと、ある問題を部分的な問題に分解した上で、個々の問題に対して最適なケースを適用して、それを解とするアルゴリズム です。考え方が割とシンプルなので、ハマれば強力ですがそもそも貪欲法で求める解が得られるんだっけと言うところが判断しづらいです。
i番目の勇者が、i番目の街のモンスターを全力で倒す。倒して、余力があれば次の街のモンスターを倒す。と最適なケースを定めれば解ける問題です。以下のコードで解が求まりました。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; vector<long> enemies; vector<long> heroes; for (int i=0; i<N+1; i++) { long A;cin>>A; enemies.push_back(A); } for (int i=0; i<N; i++) { long B;cin>>B; heroes.push_back(B); } long defeatTotalCount = 0; for (int i=0; i<N; i++) { long defeatCount = min(enemies[i], heroes[i]); long defeatCountOfNextCity = (heroes[i] > enemies[i]) ? min(heroes[i] - enemies[i], enemies[i+1]) : 0; defeatTotalCount += defeatCount + defeatCountOfNextCity; enemies[i+1] -= defeatCountOfNextCity; } cout << defeatTotalCount << endl; } |
問題読み間違えて、盛大にハマったのは内緒…