WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
    }
};