#1196111 (C++17) No.3779 L or R

• 問題: No.3779 L or R
• ユーザー: ococonomy1
• 提出日時: 2026-10-30 22:44:51
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 17 ms / 2,000 ms
• コード長: 7,896 bytes
• コンパイル時間: 1,572 ms
• コンパイル使用メモリ: 224,352 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-10-30 22:44:57
• 合計ジャッジ時間: 5,566 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 40

ソースコード

//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pli = pair<ll,int>;
#define MOD 998244353
//#define MOD 1000000007
#define el '\n'
#define El '\n'
#define YESNO(x) ((x) ? "Yes" : "No")
#define YES YESNO(true)
#define NO YESNO(false)
#define EXIT_ANS(x) {cout << (x) << '\n'; return;}
template <typename T> void inline SORT(T &v){sort(v.begin(),v.end()); return;}
template <typename T> void inline REV(T &v){reverse(v.begin(),v.end()); return;}
template <typename T> void inline VEC_UNIQ(T &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); return;}
template <typename T> auto inline MAX(T &v){return *max_element(v.begin(),v.end());}
template <typename T> auto inline MIN(T &v){return *min_element(v.begin(),v.end());}
template <typename T> auto inline SUM(vector<T> &v){T ans = 0; for(int i = 0; i < (int)v.size(); i++)ans += v[i]; return ans;}
template <typename T> void inline DEC(T &v){for(int i = 0; i < (int)v.size(); i++)v[i]--; return;}
template <typename T> void inline INC(T &v){for(int i = 0; i < (int)v.size(); i++)v[i]++; return;}
void inline TEST(void){cerr << "TEST" << endl; return;}
template <typename T,typename S> bool inline chmin(T &x,S y){
    if(x > (T)y){
        x = (T)y;
        return true;
    }
    return false;
}
template <typename T,typename S> bool inline chmax(T &x,S y){
    if(x < (T)y){
        x = (T)y;
        return true;
    }
    return false;
}
template <typename T = long long> vector<T> inline get_vec(int n){
    vector<T> ans(n);
    for(int i = 0; i < n; i++)cin >> ans[i];
    return ans;
}
template <typename T> void inline print_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cout << vec[i];
        if(kaigyou || i == n - 1)cout << '\n';
        else cout << ' ';
    }
    if(!n)cout << '\n';
    return;
}
template <typename T> void inline debug_vec(vector<T> &vec,bool kaigyou = false){
    int n = (int)vec.size();
    for(int i = 0; i < n; i++){
        cerr << vec[i];
        if(kaigyou || i == n - 1)cerr << '\n';
        else cerr << ' ';
    }
    if(!n)cerr << '\n';
    return;
}
vector<vector<int>> inline get_graph(int n,int m = -1,bool direct = false,bool decrement = true){
    if(m == -1)m = n - 1;
    vector<vector<int>> g(n);
    while(m--){
        int u,v;
        cin >> u >> v;
        if(decrement)u--,v--;
        g[u].push_back(v);
        if(!direct)g[v].push_back(u);
    }
    return g;
}
template <typename T> vector<vector<pair<T,int>>> inline get_weighted_graph(int n,int m = -1,bool direct = false,bool decrement = true){
    if(m == -1)m = n - 1;
    vector<vector<pair<T,int>>> g(n);
    while(m--){
        int u,v;
        cin >> u >> v;
        if(decrement)u--,v--;
        ll w; cin >> w;
        g[u].push_back(pair(w,v));
        if(!direct)g[v].push_back(pair(w,u));
    }
    return g;
}

//フェネック木(BIT とも呼ばれるアレ) operator+, operator+=,operator- さえ定義できていればオンラインに区間和を取得できる。
//オーダーはセグ木と一緒だが、定数倍が圧倒的に良い。ほぼ定数。
template <typename T> class ococo_fenwicktree{
private:
    int n;
    vector<T> a;
public:

    //初め、全て0で埋まっている
    ococo_fenwicktree(int N){
        n = N + 1;
        a.resize(n);
        for(int i = 1; i < n; i++){
            a[i] = 0;
            int temp = i + 1;
            while(!(temp % 2)){
                temp /= 2;
            }
        }
    }

    void add_num(int i,T x){
        int idx = i + 1;
        while(idx < n){
            a[idx] += x;
            idx += (idx & -idx);
        }
    }

    //[0,r] の区間和を取得する。
    T get_sum(int r){
        if(r < 0)return 0;
        T ans = 0;
        int idx = r + 1;
        while(idx > 0){
            ans += a[idx];
            idx -= idx & -idx;
        }
        return ans;
    }

    T get_sum(int l,int r){
        if(r < l)return 0;
        T ans = get_sum(r);
        ans -= get_sum(l - 1);
        return ans;
    }

    void update_num(int i,T x){
        T val = get_sum(i) - get_sum(i - 1);
        T dif = x - val;
        add_num(i,dif);
        return;
    }
};

bool judge(string s,string t){
    int n = (int)s.size();
    ococo_fenwicktree<int> l(n),r(n);
    for(int i = 0; i < n; i++){
        if(t[i] == 'L')l.add_num(i,1);
        else r.add_num(i,1);
    }
    for(int i = 0; i < n; i++){
        int temp = 1;
        if(i >= 1)temp += r.get_sum(i - 1);
        if(i != n - 1)temp += l.get_sum(i + 1,n - 1);
        //cerr << i << ' ' << temp << el;
        if(s[i] == 'o' && temp % 2 == 1)return false;
        if(s[i] == 'x' && temp % 2 == 0)return false;
    }
    return true;
}

#define MULTI_TEST_CASE false
void solve(void){
    //問題を見たらまず「この問題設定から言えること」をいっぱい言う
    //よりシンプルな問題に言い換えられたら、言い換えた先の問題を自然言語ではっきりと書く
    //複数の解法のアイデアを思いついた時は全部メモしておく
    //g++ -D_GLIBCXX_DEBUG -Wall -O2 a.cpp -o o
    int n;
    string s;
    cin >> n >> s;
    //n が奇数の時、 奇数回操作されるライト の個数の偶奇が一定？
    //n == 1 だと o がダメで x がいけるが、
    //n == 3 だと xxx がダメで ooo がいける（他に関しても、個数の偶奇が同じ方に倣う）
    //全部を o にしたい
    int ocnt = 0,xcnt = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'o')ocnt++;
        if(s[i] == 'x')xcnt++;
    }

    //n が偶数の時について、LR 列も点灯の変換も 2^N 通りあるから、答えとなる操作列はちょうど一通りしかない。
    //xxxx は RLRL,xxxxxx は LRLRLR となるように、mod4 に何かある？


    //[1,n-1] の L の個数は s[0] の状態で決まる
    //[0,0] の R の個数+ [2,n-1]の L の個数は s[1] で決まる
    //[0,1]   R         [3,n-1]   L          s[2]
    //s[0] == s[1] なら、s[0],s[1] の関係性は LR or RL
    //s[0] != s[1] なら、LL or RR
    //候補は高々2通りしかない
    string ans1 = "L",ans2 = "R";

    for(int i = 1; i < n; i++){
        if(s[i] != s[i - 1]){
            ans1 += ans1.back();
            ans2 += ans2.back();
        }
        if(s[i] == s[i - 1]){
            ans1 += (ans1.back() == 'L' ? 'R' : 'L');
            ans2 += (ans2.back() == 'L' ? 'R' : 'L');
        }
    }
    // cerr << ans1 << el;
    // cerr << ans2 << el;
    if(judge(s,ans1)){
        cout << YES << el;
        EXIT_ANS(ans1);
    }
    if(judge(s,ans2)){
        cout << YES<< El;
        EXIT_ANS(ans2);
    }
    cout << NO << el;


    return;
}

void calc(void){
    for(int n = 1; n <= 6; n++){
        for(int S = 0; S < (1 << n); S++){
            vector<int> val(n,0);
            string func;
            for(int i = 0; i < n; i++){
                if(S & (1 << i)){
                    func += 'L';
                    for(int j = i; j >= 0; j--){
                       val[j] ^= 1;
                    }
                }
                else{
                    func += 'R';
                    for(int j = i; j < n; j++){
                        val[j] ^= 1;
                    }
                }
            }
            cout << func << el;
            for(int j = 0; j < n; j++)cout << (val[j] ? 'x' : 'o');
            cout << el;
            cout << el;
        }
    }
    return;
}

signed main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //calc(); return 0;
    int t = 1;
    if(MULTI_TEST_CASE)cin >> t;
    while(t--){
        solve();
    }
    return 0;
}