SRM 660 div1 easy:Coversta - mayoko’s diary

SRM 660に参加。SRM div1では多分初めてmedも提出したんですがeasyもmedも落ちて0点でした。

問題

解法

いろんな方法があるっぽいですが枝刈り使った方法でやってみます。

2つの点a, bを選んだ時の最高点数の指標として,「aのみを選んだ場合の点数+bのみを選んだ場合の点数」というのが考えられる(本当は2つの頂点を選んだ場合に選ばれる頂点がかぶる可能性があるので実際にはもっと低くなる可能性がある)。これを使って枝刈りする。

基本的には2つの頂点の選び方を全探索する。しかし,それで得られる「最高点数」が予めこれまで調べた中での最高点以下であったらそれを調べる必要はないのでその2つの頂点を選んだ場合の実際の点数は計算しない。

ややスパゲッティですが以下ソースコード

class Coversta {
public:
    int place(vector <string> a, vector <int> x, vector <int> y) {
        vector<pii> memo[111][111];
        int score[111][111];
        vector<int> scores;
        int n = a.size();
        int m = a[0].size();
        int p = x.size();
        vector<vi> mat(n, vi(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                mat[i][j] = a[i][j] - '0';
            }
        }
        int ans = 0;
        for (int i = 0; i < n*m; i++) {
            int x1 = i/m;
            int y1 = i%m;
            int tmp = 0;
            for (int k = 0; k < p; k++) {
                int nx = x1+x[k];
                int ny = y1+y[k];
                if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                    memo[x1][y1].push_back(make_pair(nx, ny));
                    tmp += mat[nx][ny];
                }
            }
            scores.push_back(tmp);
            score[x1][y1] = tmp;
        }
        sort(scores.rbegin(), scores.rend());
        for (int i = 0; i < n*m; i++) {
            for (int j = 0; j < i; j++) {
                int x1 = i/m;
                int y1 = i%m;
                int x2 = j/m;
                int y2 = j%m;
                if (ans >= score[x1][y1] + score[x2][y2]) continue;
                set<pii> S;
                for (auto P : memo[x1][y1]) {
                    S.insert(P);
                }
                for (auto P : memo[x2][y2]) {
                    S.insert(P);
                }
                int tmp = 0;
                for (auto P : S) {
                    tmp += mat[P.first][P.second];
                }
                ans = max(ans, tmp);
            }
        }
        return ans;
    }
};