Approach
Sorting and greedy selection
For ABC420 B — Most Minority, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 75 lines of C++ from the credited upstream file abc420_b.cpp.
- The implementation visibly relies on sequence storage.
- 7 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1#include <algorithm>2#include <iostream>3#include <vector>4 5using namespace std;6using ui = unsigned int;7 8void add_score(vector<ui>& target_idx, vector<pair<ui, ui>>& score) {9 for (auto const idx : target_idx) score[idx].second++;10}11 12int main() {13 ui n, m;14 cin >> n >> m;15 16 vector<string> s(n);17 for (auto& ss : s) cin >> ss;18 19 vector<pair<ui, ui>> score(n);20 vector<ui> all_idx(n);21 for (ui i = 0; i < n; i++) {22 score[i].first = i;23 score[i].second = 0;24 all_idx[i] = i;25 }26 27 ui x = 0, y = 0;28 vector<ui> x_idx = {}, y_idx = {};29 for (ui i = 0; i < m; i++) {30 31 x = 0, y = 0;32 x_idx = {}, y_idx = {};33 for (ui j = 0; j < n; j++) {34 35 if (s[j][i] == '0') {36 x++;37 x_idx.push_back(j);38 } else {39 y++;40 y_idx.push_back(j);41 }42 }43 44 if (x == 0 || y == 0) {45 46 } else if (x < y) {47 48 add_score(x_idx, score);49 } else if (x > y) {50 51 add_score(y_idx, score);52 }53 }54 55 sort(score.begin(), score.end(),56 [](const pair<ui, ui>& a, const pair<ui, ui>& b) {57 return a.second > b.second;58 });59 60 ui max = score[0].second;61 vector<ui> mi = {score[0].first + 1};62 for (ui i = 1; i < n; i++) {63 if (max != score[i].second) break;64 65 mi.push_back(score[i].first + 1);66 }67 68 sort(mi.begin(), mi.end());69 70 cout << mi[0];71 for (ui i = 1; i < mi.size(); i++) cout << " " << mi[i];72 cout << endl;73 74 return 0;75}