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