ABC170に挑んだ回
今回はD突破ならず!迷走した!
D - Not Divisible
エラトステネスの篩的なことはやってたけど、素直に計算してると時間がかかるそうな。
篩に掛けた済フラグリスト(checked)的なものを用意して、対象の値をひたすら埋めていく方が速いらしい。
数が少ないときは逆に遅いけど、多くなってもそれなりに一定っぽい?
この先早く処理するためには計算しない(フラグを取っておく)みたいな対処も必要そう。
(これに気付けなかったのでエラトステネス自体が間違いかと思って因数分解とか見てた
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
void FuncD() { ll N; cin >> N; vector<ll> vec; for (ll i = 0; i < N; ++i) { ll n; cin >> n; vec.push_back(n); } sort(vec.begin(), vec.end()); ll answerNum = 0; const ll maxcount = 1000010; vector<bool> checked(maxcount); for (ll i = 0; i < vec.size(); ++ i) { auto value = vec[i]; if (checked[value]) continue; if (vec.size() != (i+1) && value == vec[i+1]) { } else { answerNum++; } for (ll j = 1; j < maxcount; ++j) { auto index = j * value; if (j * value < maxcount) { checked[j * value] = true; } else { break; } } } DisplayAnswer(answerNum); } |
E - Smart Infants
↑で詰まってたので軽く見たけど面倒そうだったので撤退した。
敗因としてはmultisetとかいう便利なやつを知らなかったので、それ知ってたら存外解けたかも。rbeginで末尾の値も取れるのね。便利。
あとは「1人も園児がいない園は計算対象外」とかを読み忘れてたり、インデックスのズレが怖いなぁとかやってたり。
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
struct School { multiset<ll> scores; void Display()const { cout << "scores:"; for (auto v : scores) { cout << v << ","; } cout << endl; } ll GetScore()const { return *scores.rbegin(); } }; void FuncE() { ll N, Q; cin >> N >> Q; map<ll, School> schools; vector<ll> children; vector<ll> childrensSchool; multiset<ll> schoolScores; children.push_back(0); childrensSchool.push_back(0); for (ll i = 0; i < N; ++i) { ll a, b; cin >> a >> b; children.push_back(a); childrensSchool.push_back(b); schools[b].scores.insert(a); } for (auto& school : schools) { if (school.second.scores.size() > 0) { schoolScores.insert(school.second.GetScore()); } } for (ll i = 0; i < Q; ++i) { ll c, s; cin >> c >> s; { auto& school = schools[childrensSchool[c]]; schoolScores.erase(schoolScores.find(school.GetScore())); school.scores.erase(school.scores.find(children[c])); if (school.scores.size() > 0) { schoolScores.insert(school.GetScore()); } } childrensSchool[c] = s; { auto& school = schools[childrensSchool[c]]; if (school.scores.size() > 0) { schoolScores.erase(schoolScores.find(school.GetScore())); } schools[childrensSchool[c]].scores.insert(children[c]); schoolScores.insert(school.GetScore()); } DisplayAnswer(*schoolScores.begin()); } } |
コメントを残す