AtCoder Regular Contest 089 D: Checker

問題概要

日本語なので原文参照 → D - Checker

解説

公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。

考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。これらの領域の位置は、領域 の右下を定めるとすべて定まります。黒の累積和・白の累積和をとって足して・・・と書いても出来ますが、今回は累積和の配列を つだけ使って実装してみましょう。

黒が置いてあるところはインクリメントし、白が置いてあるところはデクリメントすることを考えます。黒で塗りたい領域を決定したとき、黒は して白は しているため、決定した領域内に本当に黒が置いてあれば、条件を満たしているのでそのぶん加点されますし、白が置いてあれば、条件を満たしていないのでそのぶんペナルティとして減点される、というイメージになります。

このようにすると、白の要素の個数を覚えておくことで、 (累積和) + (白の要素の個数) とすれば、領域を決定した時に得られる値が分かります。

先ほど決定した領域の白黒を反転した状態における値の計算も簡単にできます。 (黒の個数) - (白の個数) と定義すると、盤面全体の累積和は と一致しています。白黒を反転しているため、 (累積和) とすることで、領域を反転させた際に得られる値が分かります。

ソースコード

#include <cstdio>
using namespace std;

int max(int a, int b) { return a < b ? b : a; }
int board[2010][2010];
int main() {
    int N, K; scanf("%d%d", &N, &K);

    int sum = 0, white = 0;
    for(int i=0; i<N; i++) {
        int x, y; char c; scanf(" %d%d %c", &x, &y, &c);
        x %= 2*K, y %= 2*K;
        if(c == 'B') board[x+1][y+1]++, sum++;
        if(c == 'W') board[x+1][y+1]--, sum--, white++;
    }

    for(int i=1; i<=2*K; i++) {
        for(int j=1; j<=2*K; j++) {
            board[i][j] += board[i][j-1];
        }
    }

    for(int j=1; j<=2*K; j++) {
        for(int i=1; i<=2*K; i++) {
            board[i][j] += board[i-1][j];
        }
    }

    int ma = -(1 << 25);
    for(int i=0; i<=K; i++) {
        for(int j=0; j<=K; j++) {
            int a = board[i][j];
            int b = board[i+K][j+K] - board[i+K][j] - board[i][j+K] + board[i][j];
            int c = board[2*K][j] - board[i+K][j];
            int d = board[i][2*K] - board[i][j+K];
            int e = board[2*K][2*K] - board[2*K][j+K] - board[i+K][2*K] + board[i+K][j+K];
            int tmp = a + b + c + d + e;
            ma = max(ma, max(tmp, sum - tmp));
        }
    }
    ma += white;
    printf("%d\n", ma);
    return 0;
}

おまけ

二次元累積和を使う問題として、他に ARC のチョコレート があります。こちらに関しても累積和の配列 つで解くことができます。

CSAcademy Round #72: Spring Cleaning

問題概要

原文 → CS Academy

頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。

はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除くことができる。

• 頂点 から出る有向辺によって繋がっている頂点を とおくとき、 ともに駒がある場合、 にある駒を取り除くことができる。

できるだけ多くの駒を取り除くとき、この操作列を出力せよ。

解説

頂点 辺の有向グラフなので、いわゆるなもりグラフで、ループが必ず つあるグラフです。なので、それぞれの頂点に対して「ループに繋がっている頂点」であるか「ループ内の頂点」であるかのどちらかです。

ループ内の頂点から探索を始めると、ループに繋がっている頂点を取れない可能性があるので、ループに繋がっている頂点から優先的に探索をすればよいです。これをするには、入次数が である頂点から先に探索すれば良いです。

なお、ひとつの大きな閉路になっていて入次数が である頂点がひとつもない場合もあることなどに注意してください。

ソースコード

void solve(vector<int>& edge, vector<int>& visited, int cur) {
    visited[cur] = true;
    if(visited[ edge[cur] ]) return;
    solve(edge, visited, edge[cur]);
    printf("%lld %lld\n", cur+1, edge[cur]+1);
}

signed main() {
    int N; cin >> N;
    vector<int> to(N, -1), deg(N, 0), visited(N, 0);
    rep(i,0,N) {
        int p; cin >> p; p--;
        to[i] = p;
        deg[p]++;
    }

    deque<int> deq;
    rep(i,0,N) {
        if(deg[i] == 0) deq.push_front(i);
        else deq.push_back(i);
    }

    rep(i,0,N) {
        solve(to, visited, deq[i]);
    }
}

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