RGB рядок#12320

RGB рядок (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Аналіз:	Андрій Холод (Connect)

Розв’язок

Розглянемо відрізок довжиною $6$ . Давайте поставимо в першу позицію елемент $R$ , в другу поставимо $G$ , в третю $B$ . Тоді розглянемо елементи які вже входять в трійку яка закінчується в позиції $4$ , в позиції $2$ — $G$ , в позиції $3$ — $B$ . Отже єдиний елемент яким ми зможемо поставити в позицію $4$ — $R$ . Тим самим принципом розташуємо елементи в позиціях $5$ та $6$ . Також умова красоти буде зберігатись і в трійках які починаються в $5$ та $6$ позиціях.

Тоді таким же принципом можемо довести що рішення не існує для всіх $n$ які не діляться націло на $3$ .

Тоді рішенням задачі буде спробувати підставити всі можливі розташування елементів $R$ , $G$ , та $B$ без повторів та вибрати найвигідніший варіант.

Асимптотика рішення $O (n)$ .

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define pb push_back

const ll clasik = 2e5+17;
const ll INF = 1e17;
ll w[clasik] , pref[clasik] , poslid[clasik];

void solve() {

    ll n;

    cin>>n;

    string line;

    cin>>line;

    if (n%3 != 0) {
        cout<<-1<<endl;
        return;
    }

    ll res = INF;

    //R G B


    ll curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='R');
        curr += (line[i+1]!='G');
        curr += (line[i+2]!='B');
    }

    res = min(res , curr);

    // R B G

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='R');
        curr += (line[i+1]!='B');
        curr += (line[i+2]!='G');
    }

    res = min(res , curr);

    // B R G

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='B');
        curr += (line[i+1]!='R');
        curr += (line[i+2]!='G');
    }

    res = min(res , curr);

    // B G R

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='B');
        curr += (line[i+1]!='G');
        curr += (line[i+2]!='R');
    }

    res = min(res , curr);

    // G R B

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='G');
        curr += (line[i+1]!='R');
        curr += (line[i+2]!='B');
    }

    res = min(res , curr);

    // G B R

    curr = 0;

    for (int i = 0 ; i < n ; i+=3) {
        curr += (line[i]!='G');
        curr += (line[i+1]!='B');
        curr += (line[i+2]!='R');
    }

    res = min(res , curr);

    cout<<res<<endl;

}  

signed main() {
    speed;
    int test;
    test = 1;
    //cin>>test;
    while (test--) solve();
    return 0;
}

C++