結果

問題 No.3779 L or R
コンテスト
ユーザー kwm_t
提出日時 2026-10-30 21:34:25
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 141 ms / 2,000 ms
+ 499µs
コード長 8,701 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,514 ms
コンパイル使用メモリ 390,460 KB
実行使用メモリ 11,536 KB
最終ジャッジ日時 2026-10-30 21:34:38
合計ジャッジ時間 11,628 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
/**
 * @file lazy_segtree_variants.hpp
 * @brief Lazy Segment Tree の各種バリエーション
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/acl_wrapper/lazy_segtree_variants.hpp
 */
#ifndef KWM_T_ACLWRAPPER_LAZY_SEGTREE_VARIANTS_HPP
#define KWM_T_ACLWRAPPER_LAZY_SEGTREE_VARIANTS_HPP

#include <vector>
#include <algorithm>
#include <utility>
#include <optional>
#include <atcoder/lazysegtree>

 /**
  * @brief LazySegTree の典型パターン集
  *
  * 提供:
  *   - Range Add / Min, Max, Sum
  *   - Range Update / Min, Max, Sum
  *   - Arithmetic Progression Add / Sum
  *   - Min/Max with Count
  *   - Affine Transform (template)
  *
  * 注意:
  *   - INF は long long 前提
  *   - size は init() で必ず 1 を入れること
  * verified:
  *   - https://atcoder.jp/contests/practice2/submissions/74233369
  */

namespace kwm_t::aclwrapper {

// ================= Range Add / Min =================
namespace RangeAddRangeMin {
using S = long long;
using F = long long;
static constexpr long long INF = (long long)4e18;

S op(S a, S b) { return std::min(a, b); }
S e() { return INF; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}
namespace RangeAddRangeMinIndex {
struct S { long long val; int idx; };
using F = long long;
static constexpr long long INF = (long long)4e18;

S op(S a, S b) {
	if (a.val != b.val) return (a.val < b.val ? a : b);
	return (a.idx < b.idx ? a : b);
}
S e() { return { INF, INT_MAX }; }
S mapping(F f, S x) { return { x.val + f, x.idx }; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}

// ================= Range Add / Max =================
namespace RangeAddRangeMax {
using S = long long;
using F = long long;
static constexpr long long INF = (long long)4e18;

S op(S a, S b) { return std::max(a, b); }
S e() { return -INF; }
S mapping(F f, S x) { return f + x; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}

// ================= Range Add / Sum =================
namespace RangeAddRangeSum {
struct S {
	long long value;
	int size;
};
using F = long long;

S op(S a, S b) { return { a.value + b.value, a.size + b.size }; }
S e() { return { 0, 0 }; }
S mapping(F f, S x) { return { x.value + f * x.size, x.size }; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
std::vector<S> init(int n, long long val = 0) { return std::vector<S>(n, { val, 1 }); }
}

// ================= Range Update / Min =================
namespace RangeUpdateRangeMin {
using S = long long;
using F = long long;
static constexpr long long INF = (long long)4e18;
static constexpr long long ID = (long long)4e18;

S op(S a, S b) { return std::min(a, b); }
S e() { return INF; }
S mapping(F f, S x) { return (f == ID ? x : f); }
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}

// ================= Range Update / Max =================
namespace RangeUpdateRangeMax {
using S = long long;
using F = long long;
static constexpr long long INF = (long long)4e18;
static constexpr long long ID = (long long)4e18;

S op(S a, S b) { return std::max(a, b); }
S e() { return -INF; }
S mapping(F f, S x) { return (f == ID ? x : f); }
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}

// ================= Range Update / Sum =================
namespace RangeUpdateRangeSum {
struct S {
	long long value;
	int size;
};
using F = long long;
static constexpr long long ID = (long long)4e18;

S op(S a, S b) { return { a.value + b.value, a.size + b.size }; }
S e() { return { 0, 0 }; }
S mapping(F f, S x) {
	if (f == ID) return x;
	x.value = f * x.size;
	return x;
}
F composition(F f, F g) { return (f == ID ? g : f); }
F id() { return ID; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
std::vector<S> init(int n, long long val = 0) { return std::vector<S>(n, { val, 1 }); }
}

// ================= Arithmetic Progression =================
namespace AddArithmeticProgression {
struct S { long long val_sum, index_sum, len; };
struct F { long long a, b; };

S op(S x, S y) { return { x.val_sum + y.val_sum, x.index_sum + y.index_sum, x.len + y.len }; }
S e() { return { 0, 0, 0 }; }
S mapping(F f, S x) { return { x.val_sum + f.a * x.index_sum + f.b * x.len, x.index_sum, x.len }; }
F composition(F f, F g) { return { f.a + g.a, f.b + g.b }; }
F id() { return { 0, 0 }; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
}

// ================= Max + Count =================
namespace RangeAddRangeMaxCount {
using S = std::pair<long long, int>;
using F = long long;
static constexpr long long INF = (long long)4e18;

S op(S a, S b) {
	if (a.first > b.first) return a;
	if (a.first < b.first) return b;
	return { a.first, a.second + b.second };
}
S e() { return { -INF, 0 }; }
S mapping(F f, S x) { return { x.first + f, x.second }; }
F composition(F f, F g) { return f + g; }
F id() { return 0; };

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
std::vector<S> init(int n, long long val = 0) { return std::vector<S>(n, { val, 1 }); }
}

// ================= Min + Count =================
namespace RangeAddRangeMinCount {
using S = std::pair<long long, int>;
using F = long long;
static constexpr long long INF = (long long)4e18;

S op(S a, S b) {
	if (a.first < b.first) return a;
	if (a.first > b.first) return b;
	return { a.first, a.second + b.second };
}
S e() { return { INF, 0 }; }
S mapping(F f, S x) { return { x.first + f, x.second }; }
F composition(F f, F g) { return f + g; }
F id() { return 0; }

using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
std::vector<S> init(int n, long long val = 0) { return std::vector<S>(n, { val, 1 }); }
}

// ================= Affine (Template) =================
template<class mint>
struct RangeAffineRangeSum {
	struct S { mint sum; int size; };
	struct F { mint b, c; };
	static S op(S l, S r) { return { l.sum + r.sum, l.size + r.size }; }
	static S e() { return { mint(0), 0 }; }
	static S mapping(F f, S x) { return { f.b * x.sum + f.c * x.size, x.size }; }
	static F composition(F f, F g) { return { f.b * g.b, f.b * g.c + f.c }; }
	static F id() { return { mint(1), mint(0) }; }

	using lazy_segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
	static std::vector<S> init(int n) { return std::vector<S>(n, { mint(0), 1 }); }
};

} // namespace kwm_t::aclwrapper

#endif // KWM_T_ACLWRAPPER_LAZY_SEGTREE_VARIANTS_HPP
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n; cin >> n;
	string s; cin >> s;
	rep(_, 2) {
		kwm_t::aclwrapper::RangeAddRangeMax::lazy_segtree seg(n);
		string t;
		if (_ == 0) {
			// L
			t = "L";
			seg.apply(0, 1, 1);
		}
		else {
			// R
			t = "R";
			seg.apply(0, n, 1);
		}
		rep2(i, 1, n) {
			int l = seg.get(i - 1) % 2;
			int r = seg.get(i) % 2;
			int b = l == r;
			int b2 = s[i - 1] == s[i];
			if (b == b2) {
				t += 'L';
				seg.apply(0, i + 1, 1);
			}
			else {
				t += 'R';
				seg.apply(i, n, 1);
			}
		}
		bool chk = true;
		rep(i, n) {
			int x = seg.get(i) % 2;
			if (x && s[i] == 'o')chk = false;
			if (!x && s[i] == 'x')chk = false;
		}
		if (!chk)continue;
		cout << "Yes" << endl;
		cout << t << endl;
		return 0;
	}
	cout << "No" << endl;
	return 0;
}
0