SRM660 Div1 Easy "Coversta"
解法
コチラを参考にしました。m(_ _)m
kmjp.hatenablog.jp
セル(i, j)に置いた時のスコアを出して、それが大きい順にセルをソートしておく。
1個目の基地を任意の位置に置いた時の、2個目の基地のベストな置き場所を考える。
ベストな置き方は、「セルが重複するような置き方の中でスコアが最大なもの」と「セルが重複しないような置き方の中でスコアが最大なもの」の、これら2つの大きいほうである。
セルが重複するパターンは、x.size()をNとするとN * (N - 1)個しかない。スコアの大きい順にセルを見ていったとき、N * (N - 1) + 1見れば、その中に「セルが重複しないような置き方の中でスコアが最大なもの」が必ず含まれているはず。だから、2個目の基地の置き方を探索するときは、N * (N - 1) + 1回行えば十分である。
ソースコード
class Coversta { public: int place(vector<string> A, vector<int> Y, vector<int> X) { int R = A.size(); int C = A[0].size(); int N = X.size(); // スコアだしてリストに詰める vector<pair<int, int> > cells; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { int s = 0; for (int k = 0; k < N; k++) { int y = i + Y[k]; int x = j + X[k]; if (0 <= y && y < R && 0 <= x && x < C) { s += A[y][x] - '0'; } } cells.push_back(make_pair(s, i * C + j)); } } // スコア順にソート sort(cells.begin(), cells.end(), greater<pair<int, int> >()); int best = 0; // a for (int ay = 0; ay < R; ay++) for (int ax = 0; ax < C; ax++) { int scoreA = 0; set<pair<int, int> > s; for (int i = 0; i < N; i++) { int y = ay + Y[i]; int x = ax + X[i]; if (0 <= y && y < R && 0 <= x && x < C) { scoreA += A[y][x] - '0'; s.insert(make_pair(y, x)); } } // b int checkN = N * (N - 1) + 1; for (int bi = 0; bi < checkN && bi < cells.size(); bi++) { int scoreB = 0; int by = cells[bi].second / C; int bx = cells[bi].second % C; for (int i = 0; i < N; i++) { int y = by + Y[i]; int x = bx + X[i]; if (0 <= y && y < R && 0 <= x && x < C && s.find(make_pair(y, x)) == s.end()) { scoreB += A[y][x] - '0'; } } best = max(best, scoreA + scoreB); } } return best; } };