問題概要
原文 → 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; }