Ліхтарі з одним ремонтом (Розбір)

Розв'язок

Нехай cnt_i — кількість ліхтарів, які освітлюють будинок $i$.

Спочатку обчислимо cnt_i для кожного будинку. Позначимо через $ans$ кількість будинків, які спочатку освітлюються рівно одним ліхтарем:

Тут $[P]$ дорівнює $1$, якщо умова $P$ виконується, та $0$ — інакше.

Розглянемо розворот ліхтаря біля будинку $i$. Нехай $l$ — будинок, який цей ліхтар освітлював до розвороту, а $r$ — будинок, який він освітлюватиме після розвороту.

Розворот впливає лише на два будинки: cnt_l зменшується на $1$, а cnt_r збільшується на $1$. Кількість ліхтарів, що освітлюють усі інші будинки, залишається незмінною.

Внесок будинку $l$ у відповідь змінюється з [cnt_l = 1] на [cnt_l = 2], а внесок будинку $r$ — з [cnt_r = 1] на [cnt_r = 0].

Отже, кількість будинків, які освітлюються рівно одним ліхтарем після розвороту, дорівнює

Таким чином, для кожного ліхтаря можемо обчислити результат його розвороту за $O(1)$, не змінюючи масив $cnt$.

Переберемо всі $n$ можливих розворотів і знайдемо максимальний результат. Оскільки дозволено розвернути не більш ніж один ліхтар, також врахуємо початковий стан без жодного розвороту.

Асимптотична складність

Обчислення початкової кількості ліхтарів, які освітлюють кожен будинок, займає $O(n)$ часу. Кожен із $n$ можливих розворотів обробляється за $O(1)$.

Загальна часова складність становить $O(n)$, а просторова — $O(n)$.

Реалізація

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<int> cnt(n);

    for (int i = 0; i < n; i++) {
        int j = (s[i] == 'L' ? (i + n - 1) % n : (i + 1) % n);
        cnt[j]++;
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (cnt[i] == 1);
    }

    int res = ans;

    for (int i = 0; i < n; i++) {
        int l = (i + n - 1) % n;
        int r = (i + 1) % n;

        if (s[i] == 'R') {
            swap(l, r);
        }

        int cur = ans;
        cur -= (cnt[l] == 1);
        cur += (cnt[l] == 2);
        cur -= (cnt[r] == 1);
        cur += (cnt[r] == 0);

        res = max(res, cur);
    }

    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}