mayoko’s diary

プロコンとかいろいろ。

Facebook Hacker Cup 2016 Qualification Round High Security

解法

X.X...
......
とかなっている場合, X.X の中の . を見えるようにするためには, X.X の . に警備員を置くか, その下に警備員を置くしかないですが, どう考えても下に置くのが得です。このように, 見る必要がある, 横に広がっているような区間が 1 マスの場所では, 警備員をどう置くかが一意に決まります。

また, 区間が 2 マス以上の場所では警備員を一人置くのが良いです。

以上をまとめると,
・横に 1 マスだけ広がっている区間ではその反対側に警備員を置く
・残った区間ではとりあえず 一人置く

というのが良いです。

int N;
string field[2];

int calc(int r) {
    int cur = 0;
    int ret = 0;
    while (cur < N) {
        if (field[r][cur] == 'X') {
            cur++;
            continue;
        }
        int i = cur;
        while (i < N && field[r][i] != 'X') {
            i++;
        }
        int nr = r^1;
        for (int j = cur; j < i; j++) {
            if (field[nr][j] == '.') {
                int cnt = 0;
                if (j-1 >= 0 && field[nr][j-1] != 'X') cnt++;
                if (j+1 < N && field[nr][j+1] != 'X') cnt++;
                if (!cnt) {
                    ret--;
                    break;
                }
            }
        }
        ret++;
        cur = i;
    }
    return ret;
}

void solve(int T) {
    cin >> N;
    for (int i = 0; i < 2; i++) cin >> field[i];
    int ans = 0;
    for (int r = 0; r < 2; r++) ans += calc(r);
    for (int i = 0; i < N; i++) {
        if (field[0][i] == '.' && field[1][i] == '.') {
            if (i-1 >= 0 && field[0][i-1] != 'X') continue;
            if (i-1 >= 0 && field[1][i-1] != 'X') continue;
            if (i+1 < N && field[0][i+1] != 'X') continue;
            if (i+1 < N && field[1][i+1] != 'X') continue;
            ans++;
        }
    }
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}