CSAcademy Round #72: Beautiful Matrix

問題概要

原文 → CS Academy

の行列 から、 の行列 を作る。 (作り方は原文参照)

を作る前に、 について行どうし、または列どうしのスワップを合計 回まで行える (何もしなくても良い) とき、 の最大値を求めよ。

解説

ある要素が、 の要素のうちいくつに関係しているか、要するに何回足されるかを調べてみます。

すると、端は に、それ以外は になることが分かります。

つまり、総和を変更するには「端とそれ以外のスワップ」にだけ着目すれば良いことになります。 (端の最大) と (中の最小) をスワップすると最適になり、これを全て試すのは で行えます。

実装方針がアだと面倒になるので注意してください。端であってもそうでなくても、増減の絶対値は になる (伝わって) ので、それを利用すると楽です。

ソースコード

int N, M;
vector< vector<int> > board;

int solve_row() {
    int outside_val = -INF, inside_val = INF;
    rep(i,0,N) {
        int val = 0;
        rep(j,0,M) {
            if(j == 0 || j == M-1) val += board[i][j];
            else val += 2 * board[i][j];
        }
        if(i == 0 || i == N-1) {
            chmax(outside_val, val);
        }
        else {
            chmin(inside_val, val);
        }
    }
    return outside_val - inside_val;
}

int solve_col() {
    int outside_val = -INF, inside_val = INF;
    rep(j,0,M) {
        int val = 0;
        rep(i,0,N) {
            if(i == 0 || i == N-1) val += board[i][j];
            else val += 2 * board[i][j];
        }
        if(j == 0 || j == M-1) {
            chmax(outside_val, val);
        }
        else {
            chmin(inside_val, val);
        }
    }
    return outside_val - inside_val;
}

signed main() {
    cin >> N >> M;
    board.resize(N, vector<int>(M));
    int orig_sum = 0;
    rep(i,0,N) rep(j,0,M) {
        cin >> board[i][j];
    }

    rep(i,0,N-1) rep(j,0,M-1) {
        rep(k,0,4) {
            int nx = i + dx[k], ny = j + dy[k];
            orig_sum += board[nx][ny];
        }
    }

    int diff = 0;
    chmax(diff, solve_row());
    chmax(diff, solve_col());
    cout << orig_sum + diff << endl;
    return 0;
}