#1017595 (C++23) No.2926 Botaoshi

提出ソース
結果

問題	No.2926 Botaoshi
ユーザー	Iroha_3856
提出日時	2024-10-12 15:10:23
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	23 ms / 2,000 ms
コード長	24,968 bytes
コンパイル時間	8,327 ms
コンパイル使用メモリ	354,420 KB
実行使用メモリ	14,336 KB
最終ジャッジ日時	2024-10-12 15:10:35
合計ジャッジ時間	10,093 ms
ジャッジサーバーID （参考情報）	judge4 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	22 ms 14,336 KB
testcase_13	AC	22 ms 14,152 KB
testcase_14	AC	22 ms 14,080 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	17 ms 10,880 KB
testcase_17	AC	21 ms 12,928 KB
testcase_18	AC	6 ms 5,248 KB
testcase_19	AC	15 ms 9,728 KB
testcase_20	AC	8 ms 6,016 KB
testcase_21	AC	12 ms 8,192 KB
testcase_22	AC	14 ms 9,344 KB
testcase_23	AC	4 ms 5,248 KB
testcase_24	AC	15 ms 10,368 KB
testcase_25	AC	5 ms 5,248 KB
testcase_26	AC	18 ms 11,776 KB
testcase_27	AC	12 ms 8,576 KB
testcase_28	AC	4 ms 5,248 KB
testcase_29	AC	4 ms 5,248 KB
testcase_30	AC	7 ms 6,016 KB
testcase_31	AC	6 ms 5,248 KB
testcase_32	AC	10 ms 6,912 KB
testcase_33	AC	18 ms 11,008 KB
testcase_34	AC	16 ms 9,856 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	22 ms 14,336 KB
testcase_37	AC	22 ms 14,208 KB
testcase_38	AC	22 ms 14,336 KB
testcase_39	AC	22 ms 14,336 KB
testcase_40	AC	22 ms 14,332 KB
testcase_41	AC	23 ms 14,308 KB
testcase_42	AC	23 ms 14,336 KB
testcase_43	AC	23 ms 14,336 KB
testcase_44	AC	23 ms 14,080 KB
testcase_45	AC	22 ms 13,824 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//==========Iroha_3856's Library==========
//命名規則
//自作関数：ownFunction
//自作クラス：OwnClass

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

//AtCoder-Library
#if __has_include(<atcoder/all>)
#include<atcoder/all>
using namespace atcoder;
using mint = atcoder::modint998244353;
#endif

//PBDS-tree
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//tree.find_by_order(k) = tree[k] (0-indexed)
//tree.order_of_key(k) = tree.lower_bound(k) - tree.begin()
//Note: Can only be used for non-multiple sets.
#endif

#define vec vector
#define ll long long
#define ull unsigned long long
#define vi vec<int>
#define vll vec<ll>
#define vb vec<bool>
#define vvi vec<vi>
#define vvll vec<vll>
#define vvb vec<vb>
#define vvvi vec<vvi>
#define vvvll vec<vvll>
#define vvvb vec<vvb>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pq priority_queue
template<class T> using spq = priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define pb push_back

#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i=(int)(l); i<(int)(r); i++)
#define REP(i, l, r) for (int i=(int)(l); i<=(int)(r); i++)
#define siz(x) (int)x.size()

template<class T>bool chmax(T &a, T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, T b) { if (b<a) { a=b; return 1; } return 0; }

//slice(A, l, r) = A[l, r)
template<class T>
vector<T> slice(const vector<T>& A, int l, int r) {
    assert(0 <= l && l <= r && r <= (int)A.size());
    vector<T> ret;
    for (int i = l; i<r; i++) ret.push_back(A[i]);
    return ret;
}

//slice(S, l, r) = S[l, r)
string slice(const string& S, int l, int r) {
    assert(0 <= l && l <= r && r <= (int)S.size());
    string ret;
    for (int i = l; i<r; i++) ret += S[i];
    return ret;
}

template<class T> 
T allSum(vector<T> A) {
    return reduce(A.begin(), A.end());
}
template<class T>
T allMax(vector<T> A) {
    return *max_element(A.begin(), A.end());
}
template<class T>
T allMin(vector<T> A) {
    return *min_element(A.begin(), A.end());
}
template<class T>
int allArgMax(vector<T> A) {
    return max_element(A.begin(), A.end())-A.begin();
}
template<class T>
int allArgMin(vector<T> A) {
    return min_element(A.begin(), A.end())-A.begin();
}

ll ceil(ll x, ll y) {
    assert(y != 0);
    if ((x >= 0) == (y >= 0)) {
        return (abs(x) + abs(y)-1)/abs(y);
    }
    else {
        return -(abs(x)/abs(y));
    }
}

ll floor(ll x, ll y) {
    assert(y != 0);
    if ((x >= 0) == (y >= 0)) {
        return abs(x)/abs(y);
    }
    else {
        return -((abs(x) + abs(y)-1)/abs(y));
    }
}

template<class T, class U> 
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}

template <class T>
istream &operator>>(istream &is, vector<T> &v) {
    for(auto &x : v) {
        is >> x;
    }
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i != (int)v.size() - 1)
            os << v[i] << " ";
        else
            os << v[i];
    }
    return os;
}

template<class T>
void print(T A, bool f = true) {
    cerr << A;
    if (f) cerr << endl;
}

template<class T, class U>
void print(pair<T, U> A, bool f = true) {
    cerr << "{" << A.first << ", " << A.second << "}";
    if (f) cerr << endl;
}

template<class T> 
void print(vector<T> A, bool f = true) {
    cerr << "{";
    for (int i = 0; i<(int)A.size(); i++) {
        print(A[i], false);
        if (i+1 != (int)A.size()) cerr << ", ";
    }
    cerr << "}";
    if (f) cerr << endl;
}

#define debug(x) cerr << #x << " = "; print(x)

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} iosetup;

struct Edge {
    int to;
    ll cost;
    Edge(int to, ll cost) : to(to), cost(cost) {}
};

const int mod = 998244353;
const int MOD = 1000000007;
const int inf = 1000010000;
const ll INF = 4e18;

//グラフ入力
//無向重みなしグラフ
vector<vector<int>> graph(int& N, int& M) {
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    return G;
}
//無向重み付きグラフ
vector<vector<Edge>> weightedGraph(int& N, int& M) {
    cin >> N >> M;
    vector<vector<Edge>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        u--; v--;
        G[u].push_back(Edge{v, w});
        G[v].push_back(Edge{u, w}); 
    }
    return G;
}
//有向重みなしグラフ
vector<vector<int>> directedGraph(int& N, int& M) {
    cin >> N >> M;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        G[u].push_back(v);
    }
    return G;
}
//有向重み付きグラフ
vector<vector<Edge>> weightedDirectedGraph(int& N, int& M) {
    cin >> N >> M;
    vector<vector<Edge>> G(N);
    for (int i = 0; i < M; i++) {
        int u, v; ll w; cin >> u >> v >> w;
        u--; v--;
        G[u].push_back(Edge{v, w});
    }
    return G;
}

//1次元累積和
//全て0-indexedで処理
template<class T>
struct ComulativeSum {
    int siz;
    vector<T> S;
    bool done;
    ComulativeSum() : ComulativeSum(0) {}
    ComulativeSum(int N) : ComulativeSum(vector<T>(N, 0)) {}
    //累積和の構築はしない
    ComulativeSum(vector<T> A) {
        done = false;
        siz = (int)A.size();
        S.resize(siz+1);
        S[0] = 0;
        for (int i = 0; i < siz; i++) {
            S[i+1] = A[i];
        }
    }
    //累積
    void run() {
        assert(!done);
        for (int i = 1; i <= siz; i++) {
            S[i] += S[i-1];
        }
        done = true;
    }
    //加算（累積前のみ）
    T add(int idx, T a) {
        assert(!done);
        S[idx+1] += a;
        return S[idx+1];
    }
    //代入（累積前のみ）
    T set(int idx, T a) {
        assert(!done);
        S[idx+1] = a;
        return S[idx+1];
    }
    //取得（累積前、累積後両方とも可能だが、どちらを想定するかをexpected_doneで渡す）
    T get(int idx, bool expected_done) {
        assert(expected_done == done);
        return S[idx+1];
    }
    //区間和取得（累積後のみ）
    //半開区間で与える
    T sum(int l, int r) {
        assert(done);
        return S[r]-S[l];
    }
};

template<class T>
struct ComulativeSum2D {
    bool done;
    int H, W;
    vector<vector<T>> S;
    ComulativeSum2D() : ComulativeSum2D(0, 0) {}
    ComulativeSum2D(int h, int w) : ComulativeSum2D(vector<vector<T>>(h, vector<T>(w))) {}
    ComulativeSum2D(vector<vector<T>> A) {
        done = false;
        H = (int)A.size();
        W = (int)A[0].size();
        S.resize(H+1, vector<T>(W+1, 0));
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) S[i+1][j+1] = A[i][j];
        }
    }
    //累積
    void run() {
        assert(!done);
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                S[i][j] += S[i][j-1];
            }
        }
        for (int j = 1; j <= W; j++) {
            for (int i = 1; i <= H; i++) S[i][j] += S[i-1][j];
        }
    }
    //加算（累積前のみ）
    T add(int r, int c, T x) {
        assert(!done);
        S[r+1][c+1] += x;
    }
    //代入（累積前のみ）
    T set(int r, int c, T x) {
        assert(!done);
        S[r+1][c+1] = x;
    }
    //取得（累積前、累積後両方とも可能だが、どちらを想定するかをexpected_doneで渡す）
    T get(int r, int c, bool expect_done) {
        assert(expect_done == done);
        return S[r+1][c+1];
    }
    //区間和取得（累積後のみ）
    //行、列とも半開区間で与える
    T sum(int left_row, int right_row, int left_column, int right_column) {
        return S[right_row][right_column] 
               - S[right_row][left_column] 
               - S[left_row][right_column] 
               + S[left_row][left_column];
    }
};

//よくつかうセグ木用の型宣言
//一点代入区間総和
namespace __RangeSumSegTree {
    template<class T> T op(T a, T b) {return a + b;}
    template<class T> T e() {return 0;}
};
template<class T>
using RangeSumSegTree = atcoder::segtree<T, __RangeSumSegTree::op<T>, __RangeSumSegTree::e<T>>;

//一点代入区間最小値
namespace __RangeMinSegTree {
    template<class T> T op(T a, T b) {return min(a, b);}
    template<class T, T __e> T e() {return __e;} 
};
template<class T, T __e>
using RangeMinSegTree = atcoder::segtree<T, __RangeMinSegTree::op<T>, __RangeMinSegTree::e<T, __e>>;

//一点代入区間最大値
namespace __RangeMaxSegTree {
    template<class T> T op(T a, T b) {return max(a, b);}
    template<class T, T __e> T e() {return __e;} 
};
template<class T, T __e>
using RangeMaxSegTree = atcoder::segtree<T, __RangeMaxSegTree::op<T>, __RangeMaxSegTree::e<T, __e>>;

//Union-Find
struct UnionFind {
    vector<int> par, siz;
    int connected_components;
    UnionFind() {
        init(0);
    }
    //n頂点0辺のグラフを作る
    UnionFind(int n) {
        init(n);
    }
    void init (int n) {
        par.resize(n, -1);
        siz.resize(n, 1);
        connected_components = n;
    }
    //頂点xの連結成分の代表をreturnする
    int root(int x) {
        if (par[x]==-1) return x;
        return par[x] = root(par[x]);
    }
    //頂点xと頂点yが同じ連結成分に属しているか判定する
    bool same(int x, int y) {
        return root(x)==root(y);
    }
    //頂点xと頂点yを結ぶ辺を作る
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x==y) return false;
        //siz[x] > siz[y]を前提とする
        if (siz[x] < siz[y]) swap(x, y);
        par[y] = x;
        siz[x]+=siz[y];
        connected_components--;
        return true;
    }
    //頂点xの連結成分の頂点数をreturnする
    int size(int x) {
        return siz[root(x)];
    }
    int connectedComponents() {
        return connected_components;
    }
    //これまでの頂点数をnとすると、頂点nを追加する（0-indexed）
    //O(1)
    void add_vertex() {
        par.push_back(-1);
        siz.push_back(1);
    }
    //これまでの頂点数をnとすると、vector<int> tosであらわされる辺を持った頂点nを追加する (0-indexed)
    //O(tos.size())
    void add_vertex(vector<int> tos) {
        add_vertex();
        int s = (int)par.size();
        for (int to : tos) {
            merge(s-1, to);
        }
    }
};

//重み付きUnion-Find
template<class T> struct WeightedUnionFind {
    vector<int> par, siz;
    vector<T> diff_weight;
    WeightedUnionFind() : WeightedUnionFind(0) {}
    WeightedUnionFind(int n) {
        init(n);
    }
    void init(int n) {
        par.resize(n, -1);
        siz.resize(n, 1);
        diff_weight.resize(n, 0);
    }
    int root(int x) {
        if (par[x]==-1) return x;
        int r = root(par[x]);
        diff_weight[x] += diff_weight[par[x]];
        return par[x] = r;
    }
    T weight(int x) {
        root(x);
        return diff_weight[x];
    }
    bool same(int x, int y) {
        return root(x)==root(y);
    }
    //weight[y]-weight[x]=wとなるように辺を張る
    bool merge(int x, int y, T w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) {
            if (weight(y)-weight(x)==w) return true;
            return false;
        }
        if (siz[x] < siz[y]) swap(x, y), w = -w;
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }
};

//連結判定
//グラフGにおいて、startから頂点iが行けるかをvector<bool>で返す
vector<bool> connected(const vector<vector<int>>& G, int start) {
    int N = (int)G.size();
    stack<int> S;
    vector<bool> seen(N, false);
    S.push(start);
    seen[start] = true;
    while(!S.empty()) {
        int pos = S.top(); S.pop();
        for (int to : G[pos]) {
            if (!seen[to]) {
                seen[to] = true;
                S.push(to);
            }
        }
    }
    return seen;
}

//BFS
//重みなしグラフにおける最短経路問題
vector<int> bfs(const vector<vector<int>>  &G, int start, int impossible) {
    queue<int> Q;
    vector<int> dist((int)G.size(), impossible);
    Q.push(start);
    dist[start] = 0;
    while(!Q.empty()) {
        int pos = Q.front(); Q.pop();
        for (int to : G[pos]) {
            if (dist[to]!=impossible) continue;
            Q.push(to);
            dist[to] = dist[pos]+1;
        }
    }
    return dist;
}

//dijkstra
//重み付きグラフにおける最短経路問題
vector<long long> dijkstra(const vector<vector<Edge>>& G, int start, long long impossible) {
    int N = (int)G.size();
    vector<long long> dist(N, impossible);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
    dist[start] = 0LL;
    Q.emplace(dist[start], start);
    while(!Q.empty()) {
        pair<long long, int> pos = Q.top();
        Q.pop();
        long long d = pos.first;
        int v = pos.second;
        //trash
        if (dist[v]!=impossible && dist[v]<d) continue;
        for (Edge e : G[v]) {
            if (dist[e.to]==impossible || dist[e.to]>d+e.cost) {
                dist[e.to] = d+e.cost;
                Q.push(make_pair(dist[e.to], e.to));
            }
        }
    }
    return dist;
}

//グリッド上でのBFS
//スタート位置の文字を与える
vector<vector<int>> gridBfs(const vector<string> &s, char start, const string wall, int impossible) {
    const int vr[4] = {0, 1, 0, -1}, vc[4] = {1, 0, -1, 0};
    vector<vector<int>> dist((int)s.size(), vector<int>(s[0].size(), impossible));
    queue<pair<int, int>> Q;
    //search start
    for (int i = 0; i < (int)s.size(); i++) {
        for (int j = 0; j < (int)s[0].size(); j++) {
            if (s[i][j] == start) {
                Q.emplace(i, j);
                dist[i][j] = 0;
            }
        }
    }
    //BFS
    while(!Q.empty()) {
        pair<int, int> pos = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = pos.first+vr[i], nc = pos.second+vc[i];
            if (nr < 0 || nr >= (int)s.size() || nc < 0 || nc >= (int)s[0].size()) continue;
            if (dist[nr][nc] != impossible) continue;
            if (wall.find(s[nr][nc]) != string::npos) continue;
            dist[nr][nc] = dist[pos.first][pos.second] + 1;
            Q.emplace(nr, nc);
        }
    }
    return dist;
}

//グリッド上でのBFS
//スタート位置の行、列を与える
vector<vector<int>> gridBfs(const vector<string> &s, int startrow, int startcolumn, const string wall, int impossible) {
    const int vr[4] = {0, 1, 0, -1}, vc[4] = {1, 0, -1, 0};
    vector<vector<int>> dist((int)s.size(), vector<int>(s[0].size(), impossible));
    queue<pair<int, int>> Q;
    Q.emplace(startrow, startcolumn);
    dist[startrow][startcolumn] = 0;
    //BFS
    while(!Q.empty()) {
        pair<int, int> pos = Q.front(); Q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = pos.first+vr[i], nc = pos.second+vc[i];
            if (nr < 0 || nr >= (int)s.size() || nc < 0 || nc >= (int)s[0].size()) continue;
            if (dist[nr][nc] != impossible) continue;
            if (wall.find(s[nr][nc]) != string::npos) continue;
            dist[nr][nc] = dist[pos.first][pos.second] + 1;
            Q.emplace(nr, nc);
        }
    }
    return dist;
}

//MST
//{辺長, u, v} の vector<tuple<ll, int, int>> を渡す
long long mst(vector<tuple<long long, int, int>> E, int N, bool m) {
    int M = (int)E.size();
    if (!m) sort(E.begin(), E.end());
    else sort(E.begin(), E.end(), greater<tuple<long long, int, int>>());
    dsu d(N);
    long long ret = 0;
    for (int i=0; i<M; i++) {
        if (!d.same(get<1>(E[i]), get<2>(E[i]))) {
            ret+=(long long) get<0>(E[i]);
            d.merge(get<1>(E[i]), get<2>(E[i]));
        }
    }
    return ret;
}

//DAG判定
bool isDAG(const vector<vector<int>>& G) {
    int V = (int)G.size();
    vector<int> deg(V, 0);
    rep(i, 0, V) {
        for (int to : G[i]) deg[to]++;
    }
    queue<int> Q;
    rep(i, 0, V) if (deg[i] == 0) Q.push(i);
    vector<bool> ans(V, false);
    while(!Q.empty()) {
        int v = Q.front(); Q.pop();
        ans[v] = true;
        for (int to : G[v]) {
            deg[to]--;
            if (deg[to] == 0) Q.push(to);
        }
    }
    bool k = true;
    rep(i, 0, V) if (!ans[i]) k = false;
    return k;
}

//トポロジカルソート
//入次数が0の頂点が最初に来る
bool topologicalSort(const vector<vector<int>>& G, vector<int>& res) {
    assert(res.empty());
    int V = (int)G.size();
    vector<int> deg(V);
    rep(i, 0, V) {
        for (int to : G[i]) deg[to]++;
    }
    queue<int> Q;
    rep(i, 0, V) {
        if (deg[i] == 0) Q.push(i);
    }
    while(!Q.empty()) {
        int v = Q.front(); Q.pop();
        res.push_back(v);
        for (int to : G[v]) {
            deg[to]--;
            if (deg[to] == 0) Q.push(to);
        }
    }
    if ((int)res.size() != V) {
        res.clear();
        return false;
    }
    return true;
}

//素数判定
bool isPrime(long long N) {
    for (long long d = 2; d * d <= N; d++) {
        if (N%d == 0) return false;
    }
    return true;
}

//エラトステネスの篩による [1, N] の素数判定
vector<bool> primeSieve(int N) {
    vector<bool> isPrime(N+1);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) {
            for (int j = 2*i; j <= N; j += i) isPrime[j] = false;
        }
    }
    return isPrime;
}

//最小素因数 (Least Prime Factor)
long long lpf(long long N) {
    for (long long d = 2; d * d <= N; d++) {
        if (N%d == 0) {
            return d;
        }
    }
    return N;
}

//エラトステネスの篩による [1, N] の最小素因数
vector<int> lpfSieve(int N) {
    vector<int> lpf(N+1);
    iota(lpf.begin(), lpf.end(), 0);
    lpf[0] = lpf[1] = -1;
    for (int i = 2; i <= N; i++) {
        if (lpf[i] == i) {
            for (int j = 2*i; j <= N; j += i) {
                lpf[j] = min(lpf[j], i);
            }
        }
    }
    return lpf;
}

//N の 素因数分解
//{p, e} of N を返す
vector<pair<long long, int>> primeFactorization(long long N) {
    vector<pair<long long, int>> ret;
    for (long long d = 2; d * d <= N; d++) {
        if (N%d) continue;
        int cnt = 0;
        while(N%d == 0) {
            cnt++;
            N /= d;
        }
        ret.push_back({d, cnt});
    }
    return ret;
} 

//[1, N] の素因数分解
//[1, N] の lpf 配列を与えて、{{p, e} of 0, {p, e} of 1, ... , {p, e} of N} を返す
//0, 1は空
vector<vector<pair<int, int>>> primeFactorization(vector<int> lpf) {
    int N = (int)lpf.size()-1;
    vector<vector<pair<int, int>>> ret(N+1);
    for (int i = 2; i <= N; i++) {
        if (lpf[i] == i) ret[i] = {{i, 1}};
        else {
            ret[i] = ret[i/lpf[i]];
            if (ret[i].back().first == lpf[i]) {
                ret[i].back().second++;
            }
            else ret[i].push_back({lpf[i], 1});
        }
    }
    return ret;
}

struct combination {
    vector<mint> fac, infac;
    combination(int n) {
        fac.resize(n+1);
        infac.resize(n+1);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
        infac[n] = fac[n].inv();
        for (int i = n; i >= 1; i--) infac[i-1] = infac[i] * i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        return fac[n] * infac[k] * infac[n-k];
    }
};

struct Hash {
    vector<long long> mod = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
#ifdef const_rand
    long long K = const_rand;
#else
    long long K = 100 + rand()%100;
#endif 
    vector<vector<long long>> Pow;
    //H[i] = Hash[0, i)
    vector<vector<long long>> H;
    int B = 5;
    vector<int> S;
    int N;
    void init(string s) {
        N = (int)s.size();
        S.resize(N);
        for (int i = 0; i<N; i++) {
            if (islower(s[i])) S[i] = s[i]-'a' + 1;
            if (isupper(s[i])) S[i] = s[i]-'A' + 27;
        }
        Pow.resize(B, vector<long long>(N+1));
        for (int i = 0; i<B; i++) {
            Pow[i][0] = 1;
            for(int j = 1; j<N+1; j++) {
                Pow[i][j] = Pow[i][j-1] * K;
                Pow[i][j] %= mod[i];
            }
        }
        H.resize(B);
        for (int i = 0; i<B; i++) {
            H[i].resize(N+1);
            H[i][0] = 0;
            for (int j = 1; j<N+1; j++) {
                H[i][j] = (H[i][j-1] * K + S[j-1])%mod[i];
            }
        }
    }
    Hash() {
        init("");
    }
    Hash(string s) {
        init(s);
    }
    Hash(string s, vector<long long> m) {
        mod = m;
        B = (int)m.size();
        init(s);
    }
    //val(l, r) = Hash[l, r)
    vector<long long> val(int l, int r) {
        vector<long long> res(B);
        for (int i = 0; i<B; i++) {
            res[i] = H[i][r] - (Pow[i][r-l] * H[i][l]%mod[i]);
            if (res[i] < 0) res[i] += mod[i];
        }
        return res;
    }
    //same(l1, r1, l2, r2) = issame(S[l1, r1), S[l2, r2))
    bool same(int l1, int r1, int l2, int r2) {
        if (val(l1, r1) == val(l2, r2)) return true;
        return false;
    }
};

/*
created by drken
https://qiita.com/drken/items/b97ff231e43bce50199a

返り値: a と b の最大公約数
ax + by = gcd(a, b) を満たす (x, y) が格納される

＜補足＞
(a, b) = (0, 2), (-1, -3)など、a<=0, b<=0の場合でも動きます。
ただし、返ってくるgcdが負になることがあることに注意
gcdが0になるのは(a, b) = (0, 0)の場合のみです
(a, b) = (0, 2)などの場合はちゃんと2となって返ってきます
*/
long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

vector<pair<char, int>> runLength(const string& S) {
    int N = (int)S.size();
    vector<pair<char, int>> ret;
    for (int l = 0; l<N;) {
        int r = l+1;
        for (; r<N && S[l]==S[r] && S[r]=='='; r++) ;
        ret.emplace_back(S[l], r-l);
        l = r;
    }
    return ret;
}

string runLengthDecode(const vector<pair<char, int>>& code) {
    string ret = "";
    for (pair<char, int> c : code) {
        ret+=string(c.first, c.second);
    }
    return ret;
}

int digitSum(long long T) {
    string t = to_string(T);
    int ret = 0;
    for (char k : t) ret+=k-'0';
    return ret;
}

template<class T>
vector<int> compress(const vector<T>& A) {
    vector<T> B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    vector<int> res((int)A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        res[i] = lower_bound(B.begin(), B.end(), A[i])-B.begin();
    }
    return res;
}

//vector<T>であらわされるn進数を10進数に変換する
template<class T>
T changeBaseToTen(const vector<T>& A, T n) {
    T ret = 0;
    T mul = 1;
    for (int i = (int)A.size()-1; i >= 0; i--) {
        ret += mul * A[i];
        mul *= n;
    }
    return ret;
}

//10進数でxのものをn進数に変換する
template<class T>
vector<T> changeBaseFromTen(T x, T n) {
    vector<T> ret;
    while(x != 0) {
        ret.push_back(x%n);
        x /= n;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

//n進法の桁のvectorであるSをm進法に変換する
template<class T>
vector<T> changeBase(const vector<T>& S, T n, T m) {
    T ten = changeBaseToTen(S, n);
    return changeBaseTromTen(ten, m);
} 

int main() {
    int N; string S; cin >> N >> S;
    vector<vector<mint>> dp(N+1, vector<mint>(3));
    dp[0][0] = 1;
    //0 : U
    //1 : L
    //2 : R
    string T = "ULR";
    rep(i, 0, N) {
        rep(j, 0, 3) {
            rep(k, 0, 3) {
                if (j == 2 and k == 1) continue;
                if (S[i] != '.' and T[k] != S[i]) continue;
                dp[i+1][k] += dp[i][j];
            }
        }
    }
    mint ans = dp[N][0] + dp[N][1] + dp[N][2];
    cout << ans.val() << endl;
}
yukicoder

結果

テストケース

ソースコード
