Created
March 25, 2015 09:07
-
-
Save gintenlabo/4c89470076db91380aba to your computer and use it in GitHub Desktop.
plague inc. で どの症状から取るべきか
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <string> | |
#include <unordered_set> | |
#include <vector> | |
#include <memory> | |
#include <limits> | |
struct symptom; | |
using symptom_t = std::shared_ptr<symptom const>; | |
using symptom_list = std::vector<symptom_t>; | |
struct symptom { | |
std::string name; | |
double cost; | |
double infectivity; | |
std::unordered_set<symptom_t> next_symptoms; | |
}; | |
auto estimateMostEfficientRoutes( | |
double sum, | |
double current_infectivity, | |
symptom_list const& r0, | |
std::unordered_set<symptom_t> const& symptoms) | |
-> std::vector<std::pair<double, symptom_list>> { | |
if (symptoms.empty()) { | |
return {{sum, r0}}; | |
} | |
std::vector<std::pair<double, symptom_list>> results; | |
double max_sum = std::numeric_limits<double>::lowest(); | |
for (auto& s : symptoms) { | |
symptom_list r1 = r0; | |
r1.push_back(s); | |
std::unordered_set<symptom_t> remaining_symptoms = symptoms; | |
for (auto& s_ : s->next_symptoms) { | |
remaining_symptoms.insert(s_); | |
} | |
for (auto& s_ : r1) { | |
remaining_symptoms.erase(s_); | |
} | |
std::vector<std::pair<double, symptom_list>> rs = | |
estimateMostEfficientRoutes( | |
sum + s->cost * current_infectivity, | |
current_infectivity + s->infectivity, | |
r1, remaining_symptoms); | |
for (auto& r : rs) { | |
if (max_sum < r.first) { | |
results.clear(); | |
max_sum = r.first; | |
results.push_back(std::move(r)); | |
} else if (max_sum == r.first) { | |
results.push_back(std::move(r)); | |
} | |
} | |
} | |
return results; | |
} | |
std::unordered_set<symptom_t> create_symptoms() { | |
auto pulmonary_edema = std::make_shared<symptom>(); | |
pulmonary_edema->name = "肺水腫"; | |
pulmonary_edema->cost = 7; | |
pulmonary_edema->infectivity = 5; | |
auto nausea = std::make_shared<symptom>(); | |
nausea->name = "吐き気"; | |
nausea->cost = 2; | |
nausea->infectivity = 1; | |
{ | |
auto vomiting = std::make_shared<symptom>(); | |
vomiting->name = "嘔吐"; | |
vomiting->cost = 3; | |
vomiting->infectivity = 3; | |
nausea->next_symptoms.insert(vomiting); | |
vomiting->next_symptoms.insert(pulmonary_edema); | |
auto diarrhoea = std::make_shared<symptom>(); | |
diarrhoea->name = "下痢"; | |
diarrhoea->cost = 6; | |
diarrhoea->infectivity = 6; | |
vomiting->next_symptoms.insert(diarrhoea); | |
pulmonary_edema->next_symptoms.insert(diarrhoea); | |
} | |
auto coughing = std::make_shared<symptom>(); | |
coughing->name = "咳"; | |
coughing->cost = 4; | |
coughing->infectivity = 3; | |
{ | |
auto sneezing = std::make_shared<symptom>(); | |
sneezing->name = "くしゃみ"; | |
sneezing->cost = 5; | |
sneezing->infectivity = 5; | |
coughing->next_symptoms.insert(sneezing); | |
auto pneumonia = std::make_shared<symptom>(); | |
pneumonia->name = "肺炎"; | |
pneumonia->cost = 3; | |
pneumonia->infectivity = 3; | |
coughing->next_symptoms.insert(pneumonia); | |
pneumonia->next_symptoms.insert(pulmonary_edema); | |
} | |
auto rash = std::make_shared<symptom>(); | |
rash->name = "発疹"; | |
rash->cost = 3; | |
rash->infectivity = 2; | |
{ | |
auto sweating = std::make_shared<symptom>(); | |
sweating->name = "発汗"; | |
sweating->cost = 3; | |
sweating->infectivity = 2; | |
rash->next_symptoms.insert(sweating); | |
auto skin_lesions = std::make_shared<symptom>(); | |
skin_lesions->name = "皮膚障害"; | |
skin_lesions->cost = 8; | |
skin_lesions->infectivity = 11; | |
sweating->next_symptoms.insert(skin_lesions); | |
} | |
auto cysts = std::make_shared<symptom>(); | |
cysts->name = "嚢胞"; | |
cysts->cost = 2; | |
cysts->infectivity = 2; | |
{ | |
auto abscesses = std::make_shared<symptom>(); | |
abscesses->name = "膿瘍"; | |
abscesses->cost = 2; | |
abscesses->infectivity = 4; | |
cysts->next_symptoms.insert(abscesses); | |
} | |
auto anaemia = std::make_shared<symptom>(); | |
anaemia->name = "貧血"; | |
anaemia->cost = 2; | |
anaemia->infectivity = 1; | |
{ | |
auto haemophilia = std::make_shared<symptom>(); | |
haemophilia->name = "血友病"; | |
haemophilia->cost = 3; | |
haemophilia->infectivity = 4; | |
anaemia->next_symptoms.insert(haemophilia); | |
} | |
return {nausea, coughing, rash, cysts, anaemia}; | |
} | |
#include <iostream> | |
int main() { | |
auto results = estimateMostEfficientRoutes(0, 4, {}, create_symptoms()); | |
for (auto& result : results) { | |
std::cout << result.first << " "; | |
for (auto& s : result.second) { | |
std::cout << s->name << " "; | |
} | |
std::cout << std::endl; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
結論: 嚢胞->膿瘍->発疹->発汗->皮膚障害->貧血->血友病->咳->くしゃみ->肺炎->吐き気->嘔吐->下痢->肺水腫 の順に取れ