Approach
Sorting and greedy selection
For ABC337 D — Cheating Gomoku Narabe, 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
- 80 lines of C++ from the credited upstream file abc337_d.cpp.
- The implementation visibly relies on sequence storage.
- 4 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 <list>4#include <vector>5 6using namespace std;7using ui = unsigned int;8 9int main() {10 ui h, w, k;11 cin >> h >> w >> k;12 13 vector<vector<char>> g(h, vector<char>(w));14 15 vector<ui> okpc;16 17 for (ui i = 0; i < h; i++) {18 list<char> ok;19 ui pc = 0;20 for (ui j = 0; j < w; j++) {21 cin >> g[i][j];22 if (g[i][j] == 'x') {23 if (ok.size() == k) {24 okpc.push_back(pc);25 }26 ok.clear();27 pc = 0;28 } else {29 if (ok.size() == k) {30 okpc.push_back(pc);31 pc -= ui(ok.front() == '.');32 ok.pop_front();33 }34 ok.push_back(g[i][j]);35 pc += ui(g[i][j] == '.');36 }37 }38 39 if (ok.size() == k) {40 okpc.push_back(pc);41 }42 }43 44 for (ui j = 0; j < w; j++) {45 list<char> ok;46 ui pc = 0;47 for (ui i = 0; i < h; i++) {48 if (g[i][j] == 'x') {49 if (ok.size() == k) {50 okpc.push_back(pc);51 }52 ok.clear();53 pc = 0;54 } else {55 if (ok.size() == k) {56 okpc.push_back(pc);57 pc -= ui(ok.front() == '.');58 ok.pop_front();59 }60 ok.push_back(g[i][j]);61 pc += ui(g[i][j] == '.');62 }63 }64 65 if (ok.size() == k) {66 okpc.push_back(pc);67 }68 }69 70 if (okpc.size() == 0) {71 cout << -1 << endl;72 return 0;73 }74 75 sort(okpc.begin(), okpc.end());76 77 cout << okpc[0] << endl;78 79 return 0;80}