hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

CSAcademy Round #72: Beautiful Matrix

問題概要

原文 → CS Academy

 H \times W の行列  A から、  (H-1) \times (W-1) の行列  B を作る。 (作り方は原文参照)

 B を作る前に、 A について行どうし、または列どうしのスワップを合計  1 回まで行える (何もしなくても良い) とき、  \sum_{i, j} B_{ij} の最大値を求めよ。

解説

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

すると、端は  1, 2, 2, \dots , 2, 1 に、それ以外は  2, 4, 4, \dots, 4, 2 になることが分かります。

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

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

ソースコード

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