#1137671 (C++23) No.3395 Range Flipping Game

提出ソース
結果

問題	No.3395 Range Flipping Game
コンテスト
ユーザー	sclara
提出日時	2025-12-02 00:10:49
言語	C++23 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	220 ms / 2,000 ms
コード長	23,905 bytes
コンパイル時間	3,856 ms
コンパイル使用メモリ	300,744 KB
実行使用メモリ	7,852 KB
最終ジャッジ日時	2025-12-02 00:10:56
合計ジャッジ時間	6,450 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 30
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef std::pair<long long, long long> P;
typedef std::priority_queue<P, std::vector<P>, std::greater<P>> PQ;
typedef std::complex<double> cd;

struct P3 {
    long long first, second, third;
};

struct P4 {
    long long first, second, third, fourth;
};

struct P3P {
    P first, second, third;
};

struct compP3{
    bool operator()(const P3 &p1,const P3 &p2) const {
        if (p1.first != p2.first) return p1.first < p2.first;
        if (p1.second != p2.second) return p1.second < p2.second;
        else return p1.third < p2.third;
    }
};

struct gcompP3{
    bool operator()(const P3 &p1,const P3 &p2) const {
        if (p1.first != p2.first) return p1.first > p2.first;
        if (p1.second != p2.second) return p1.second > p2.second;
        else return p1.third > p2.third;
    }
};

struct comp{
    bool operator()(const P3 &p1,const P3 &p2) const {
        ll a = p1.first + p1.third;
        ll b = p2.first + p2.third;
        return a < b;
    }
};

const double PI = acos(-1.0);

bool ckran(int a, int n) {
    return (a >= 0 && a < n);
}

void yn (bool f) {
    if (f) std::cout << "Yes" << '\n';
    else std::cout << "No" << '\n';
}

void zo (bool f) {
    if (f) std::cout << 1 << '\n';
    else std::cout << 0 << '\n';
}

long long sclog10(long long n) {
    long long ans = 0;
    while (n != 0) {
        n /= 10;
        ans++;
    }
    return ans;
}

long long longpow(long long x, long long n) {
    long long ans = 1;
    for (long long i = 0; i < n; ++i) {
        ans *= x;
    }
    return ans;
}

long long pplus(P a) {
    return a.first + a.second;
}

long long pminus(P a) {
    return a.first - a.second;
}

long long ptime(P a) {
    return a.first * a.second;
}

long long pdiv(P a) {
    return a.first / a.second;
}

std::pair<long long, long long> unzip(long long x, long long m) {
    std::pair<long long, long long> res;
    res.first = x / m;
    res.second = x % m;
    return res;
}

template<typename T, typename U>
bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template<typename T, typename U>
bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template<typename T>
void outspace(std::vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        std::cout << a[i];
        if (i != n - 1) std::cout << " ";
        else std::cout << std::endl;
    }
}

void outspace(P a) {
    std::cout << a.first << ' ' << a.second << '\n';
}

template<typename T>
void outendl(std::vector<T> a) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        std::cout << a[i] << '\n';
    }
}

std::vector<long long> lltovec(long long n, long long base = 10, long long minsize = -1) {
    std::vector<long long> res;
    while (minsize-- > 0 || n > 0) {
        res.push_back(n % base);
        n /= base;
    }
    // std::reverse(res.begin(), res.end());
    return res;
}

long long vectoll(std::vector<long long> vec, long long base = 10) {
    long long res = 0;
    std::reverse(vec.begin(), vec.end());
    for (auto i : vec) {
        res *= base;
        res += i;
    }
    std::reverse(vec.begin(), vec.end());
    return res;
}

std::vector<long long> lltobin(long long n) {
    std::vector<long long> res;
    for (int i = 0; i < 32; ++i) {
        res.push_back(n % 2);
        n /= 2;
    }
    std::reverse(res.begin(), res.end());
    return res;
}

long long bintoll(std::vector<long long> vec) {
    long long res = 0;
    for (auto i : vec) {
        res *= 2;
        res += i;
    }
    return res;
}

// 拡張ユークリッドの互除法（a*x + b*y = gcd(a,b) となる x,y を返す）
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0) { x = 1; y = 0; return a; }
    ll g = extgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
 
// M と互いに素な a の逆元（M が合成数の場合でも、a と M が互いに素ならば拡張ユークリッド法で求める）
ll modinv(ll a, ll M) {
    ll x, y;
    ll g = extgcd(a, M, x, y);
    if(g != 1) return -1; // 本来は起こらない（ここでは den について逆元を求めるので必ず gcd(den, M)=1）
    x %= M; if(x < 0) x += M;
    return x;
}

long long MOD = 998244353;
static const int MAXN = 2500000;  // 必要に応じて大きく設定

// 階乗・階乗逆元の配列
static long long fact[MAXN+1], invFact[MAXN+1];

// 繰り返し二乗法 (a^b mod M)
long long modpow(long long a, long long b, long long M) {
    long long ret = 1 % M;
    a %= M;
    while (b > 0) {
        if (b & 1) ret = (ret * a) % M;
        a = (a * a) % M;
        b >>= 1;
    }
    return ret;
}

// 前処理: 階乗と逆元のテーブルを作る
void initFactorials() {
    // 階乗テーブル
    fact[0] = 1;
    for (int i = 1; i <= MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    // 階乗逆元テーブル
    invFact[MAXN] = modpow(fact[MAXN], MOD - 2, MOD);  // フェルマーの小定理で逆元を計算
    for (int i = MAXN; i >= 1; i--) {
        invFact[i-1] = invFact[i] * i % MOD;
    }
}

// 組み合わせ数 C(n, r)
long long comb(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

class uftree {

    private:
    std::vector<int> union_find_tree;
    std::vector<int> rank;
    std::vector<int> nodes_count;

    public:

    uftree (int uftree_size) {
        union_find_tree.resize(uftree_size);
        rank.resize(uftree_size);
        nodes_count.resize(uftree_size);

        for (int i = 0; i < uftree_size; ++i) {
            union_find_tree[i] = i;
            rank[i] = 0;
            nodes_count[i] = 1;
        }
    }

    int find (int n) {
        if (union_find_tree[n] == n) return n;
        else {
            union_find_tree[n] = find(union_find_tree[n]);
            return union_find_tree[n];
        }
    }

    void unite (int x, int y) {
        x = find(x);
        y = find(y);

        if (x == y) return;

        if (1) {
            union_find_tree[y] = union_find_tree[x];
            nodes_count[x] += nodes_count[y];
        } else {
            union_find_tree[x] = union_find_tree[y];
            nodes_count[y] += nodes_count[x];
            if (rank[x] == rank[y]) rank[y]++;
        }
    }

    bool connected (int x, int y) {
        x = find(x);
        y = find(y);
        return x == y;
    }
    
    long long groupCount (int x) {
        x = find(x);
        return nodes_count[x];
    }

};

class maxSegmentTree {
    int n;
    std::vector<long long> tree, lazy;
    const long long MINI = -4e18;

    public:
    maxSegmentTree(int size) {
        n = size;
        tree.assign(4 * n, MINI);
        lazy.assign(4 * n, MINI);
    }

    void push(int node, int start, int end) {
        if (lazy[node] != MINI) {
            // 遅延値を現在のノードに適用
            tree[node] = std::max(tree[node], lazy[node]);

            // 子ノードに遅延値を伝播
            if (start != end) {
                lazy[node * 2] = std::max(lazy[node * 2], lazy[node]);
                lazy[node * 2 + 1] = std::max(lazy[node * 2 + 1], lazy[node]);
            }

            // 現在のノードの遅延値をクリア
            lazy[node] = MINI;
        }
    }

    void updateRange(int l, int r, long long value, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        push(node, start, end);

        if (start > r || end < l) {
            // 完全に範囲外
            return;
        }

        if (start >= l && end <= r) {
            // 完全に範囲内
            lazy[node] = value;
            push(node, start, end);
            return;
        }

        // 部分的に範囲が重なる場合
        int mid = (start + end) / 2;
        updateRange(l, r, value, node * 2, start, mid);
        updateRange(l, r, value, node * 2 + 1, mid + 1, end);
        tree[node] = std::max(tree[node * 2], tree[node * 2 + 1]);
    }

    long long queryRange(int l, int r, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        push(node, start, end);

        if (start > r || end < l) {
            // 完全に範囲外
            return MINI;
        }

        if (start >= l && end <= r) {
            // 完全に範囲内
            return tree[node];
        }

        // 部分的に範囲が重なる場合
        int mid = (start + end) / 2;
        long long leftQuery = queryRange(l, r, node * 2, start, mid);
        long long rightQuery = queryRange(l, r, node * 2 + 1, mid + 1, end);
        return std::max(leftQuery, rightQuery);
    }
};

class sumSegmentTree {
    int n;
    std::vector<long long> tree, lazy;

    public:
    sumSegmentTree(int size) {
        n = size;
        tree.assign(4 * n, 0);
        lazy.assign(4 * n, 0);
    }

    void push(int node, int start, int end) {
        if (lazy[node] != 0) {
            // 遅延値を現在のノードに適用
            tree[node] += (end - start + 1) * lazy[node];

            // 子ノードに遅延値を伝播
            if (start != end) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }

            // 現在のノードの遅延値をクリア
            lazy[node] = 0;
        }
    }

    void updateRange(int l, int r, long long value, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        push(node, start, end);

        if (start > r || end < l) {
            // 完全に範囲外
            return;
        }

        if (start >= l && end <= r) {
            // 完全に範囲内
            lazy[node] += value;
            push(node, start, end);
            return;
        }

        // 部分的に範囲が重なる場合
        int mid = (start + end) / 2;
        updateRange(l, r, value, node * 2, start, mid);
        updateRange(l, r, value, node * 2 + 1, mid + 1, end);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    long long queryRange(int l, int r, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        push(node, start, end);

        if (start > r || end < l) {
            // 完全に範囲外
            return 0;
        }

        if (start >= l && end <= r) {
            // 完全に範囲内
            return tree[node];
        }

        // 部分的に範囲が重なる場合
        int mid = (start + end) / 2;
        long long leftQuery = queryRange(l, r, node * 2, start, mid);
        long long rightQuery = queryRange(l, r, node * 2 + 1, mid + 1, end);
        return leftQuery + rightQuery;
    }

    long long lower_bound(int l, long long value, int node = 1, int start = 0, int end = -1, long long curval = 0) {
        if (end == -1) {
            end = n - 1;
            push(node, start, end);
            curval += queryRange(0, l - 1);
            if (tree[node] < value + curval) return n;
        }

        if (start == end) {
            if (tree[node] + curval < value) return start + 1;
            else return start;
        }

        int mid = (start + end) / 2;
        push(node * 2, start, mid);
        push(node * 2 + 1, mid + 1, end);
        if (tree[node * 2] + curval >= value) {
            return lower_bound(l, value, node * 2, start, mid, curval);
        } else {
            curval += tree[node * 2];
            return lower_bound(l, value, node * 2 + 1, mid + 1, end, curval);
        }
    }
};

struct DynamicSegTree {

    // 動的セグメント木のノード（遅延タグなし）
    struct Node {
        ll val;      // 区間の合計
        Node *lch, *rch;
        Node(): val(0), lch(nullptr), rch(nullptr) {}
    };


    int L, R;    // 管理区間 [L, R)
    Node* root;

    DynamicSegTree(int _L, int _R): L(_L), R(_R) {
        root = new Node();
    }

    // 点更新: idx に v を加算
    void point_update(Node*& node, int l, int r, int idx, ll v) {
        if (!node) node = new Node();
        if (l + 1 == r) {
            // 葉ノード
            node->val += v;
            return;
        }
        int m = l + (r - l) / 2;
        if (idx < m) {
            point_update(node->lch, l, m, idx, v);
        } else {
            point_update(node->rch, m, r, idx, v);
        }
        ll left = node->lch ? node->lch->val : 0;
        ll right = node->rch ? node->rch->val : 0;
        node->val = left + right;
    }

    // 区間 [ql, qr) の合計を取得
    ll range_query(Node* node, int l, int r, int ql, int qr) {
        if (!node || qr <= l || r <= ql) return 0;  // 範囲外
        if (ql <= l && r <= qr) {
            // 完全被覆
            return node->val;
        }
        int m = l + (r - l) / 2;
        return range_query(node->lch, l, m, ql, qr)
             + range_query(node->rch, m, r, ql, qr);
    }

    // ラッパー
    void update(int idx, ll v) {
        point_update(root, L, R, idx, v);
    }
    ll query(int ql, int qr) {
        return range_query(root, L, R, ql, qr);
    }
};

class SegmentTreeD {
    int n;
    std::vector<DynamicSegTree> tree, lazy;

    public:
    SegmentTreeD(int size) {
        n = size;
        tree.assign(4 * n, DynamicSegTree(0, 1000000));
    }

    void updateRange(int l, int r, long long value, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start > r || end < l) {
            // 完全に範囲外
            return;
        }

        if (start >= l && end <= r) {
            // 完全に範囲内
            tree[node].update(value, 1);
            return;
        }

        // 部分的に範囲が重なる場合
        int mid = (start + end) / 2;
        updateRange(l, r, value, node * 2, start, mid);
        updateRange(l, r, value, node * 2 + 1, mid + 1, end);
    }

    long long query(int id, int v, int node = 1, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start > id || end < id) {
            // 完全に範囲外
            return 0;
        }

        if (start >= id && end <= id) {
            // 完全に範囲内
            long long res = 0;
            if (start != end) {
                int mid = (start + end) / 2;
                long long leftQuery = query(id, v, node * 2, start, mid);
                long long rightQuery = query(id, v, node * 2 + 1, mid + 1, end);
                res += leftQuery + rightQuery;
            }
            return tree[node].query(0, v) + res;
        }

        return 0;
    }
};

vector<string> rot(vector<string> s, int h, int w) {
    vector<string> res = s;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            res[i][j] = s[h - j - 1][i];
        }
    }
    return res;
}

void outdouble(long double a) {
    std::cout << std::fixed << std::setprecision(10) << a << std::endl;
}

// Trieの各ノードを表すクラス
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool is_end;
    int count;
    
    TrieNode() : is_end(false) {
        count = 0;
    }
};

// Trie木を管理するクラス
class Trie {
private:
    TrieNode* root;
public:
    Trie() {
        root = new TrieNode();
    }
    
    // 文字列をTrie木に挿入するメソッド
    void insert(const string &word) {
        TrieNode* node = root;
        (node->count)++;
        for (char c : word) {
            // 子ノードが存在しなければ新たに作成する
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
            (node->count)++;
        }
        // 最後のノードを単語の終端とする
        node->is_end = true;
    }
    
    // 単語がTrie木に存在するか完全一致検索するメソッド
    bool search(const string &word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->is_end;
    }
    
    // 指定された接頭辞を持つ単語が存在するか確認するメソッド
    bool startsWith(const string &prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }

    int sameStartsLen(const string &word, const int sameCount) {
        TrieNode* node = root;
        int res = 0;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()
                    || (node->children[c])->count < sameCount) {
                return res;
            }
            node = node->children[c];
            res++;
        }
        return res;
    }
};

// Dinic法による最大流（O(E * sqrt(V)) ～ O(E * V^0.5) くらいで速いです）
struct Dinic {
    struct Edge {
        int to;             // 行き先
        long long cap;      // 残余容量
        int rev;            // 逆辺のインデックス
    };

    int N;                          // 頂点数
    vector<vector<Edge>> G;         // グラフ
    vector<int> level;              // s からの距離
    vector<int> prog;               // どこまで探索したか（current arc）

    Dinic(int n) : N(n), G(n), level(n), prog(n) {}

    // 有向辺 u -> v 容量 cap を追加
    void add_edge(int u, int v, long long cap) {
        Edge f = {v, cap, (int)G[v].size()};
        Edge r = {u, 0,   (int)G[u].size()};
        G[u].push_back(f);
        G[v].push_back(r);
    }

    // s からの BFS でレベルグラフ構築
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (auto &e : G[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
        return level[t] >= 0;
    }

    // 深さ優先でブロッキングフローを流す
    long long dfs(int v, int t, long long f) {
        if (v == t) return f;
        for (int &i = prog[v]; i < (int)G[v].size(); i++) {
            Edge &e = G[v][i];
            if (e.cap <= 0 || level[v] >= level[e.to]) continue;
            long long d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
        return 0;
    }

    // s から t への最大流
    long long max_flow(int s, int t) {
        long long flow = 0;
        const long long INF = numeric_limits<long long>::max();
        while (bfs(s, t)) {
            fill(prog.begin(), prog.end(), 0);
            long long f;
            while ((f = dfs(s, t, INF)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

struct MinCostFlow {
    struct Edge {
        int to;             // 行き先
        long long cap;      // 残余容量
        long long cost;     // コスト
        int rev;            // 逆辺のインデックス
    };

    int N;
    vector<vector<Edge>> G;

    MinCostFlow(int n) : N(n), G(n) {}

    // 有向辺 from -> to, 容量 cap, コスト cost を追加
    void add_edge(int from, int to, long long cap, long long cost) {
        Edge f = {to, cap,  cost, (int)G[to].size()};
        Edge r = {from, 0, -cost, (int)G[from].size()};
        G[from].push_back(f);
        G[to].push_back(r);
    }

    // s から t に最大 maxf だけ流したときの (流した量, 総コスト) を返す
    // 流せるだけ流して maxf に届かなかった場合も、その時点までの (flow, cost) を返します
    pair<long long, long long> min_cost_flow(int s, int t, long long maxf) {
        const long long INF = (1LL << 60);
        long long flow = 0;
        long long cost = 0;

        vector<long long> h(N, 0);      // ポテンシャル
        vector<long long> dist(N);      // 最短距離
        vector<int> prevv(N), preve(N); // 経路復元用

        while (maxf > 0) {
            // ダイクストラで残余グラフ上の s→t 最短路 (ポテンシャル付き)
            priority_queue<pair<long long,int>,
                           vector<pair<long long,int>>,
                           greater<pair<long long,int>>> pq;
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            pq.push({0, s});

            while (!pq.empty()) {
                auto [d, v] = pq.top();
                pq.pop();
                if (dist[v] < d) continue;
                for (int i = 0; i < (int)G[v].size(); i++) {
                    Edge &e = G[v][i];
                    if (e.cap <= 0) continue;
                    long long nd = d + e.cost + h[v] - h[e.to];
                    if (nd < dist[e.to]) {
                        dist[e.to] = nd;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        pq.push({nd, e.to});
                    }
                }
            }

            // これ以上 t に到達できない
            if (dist[t] == INF) break;

            // ポテンシャルを更新
            for (int v = 0; v < N; v++) {
                if (dist[v] < INF) h[v] += dist[v];
            }

            // s→t の最短路に流せる最大量を計算
            long long d = maxf;
            for (int v = t; v != s; v = prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }

            maxf -= d;
            flow += d;
            cost += d * h[t];  // h[t] が実際の s→t 最短コストになっている

            // 実際に流して残余グラフを更新
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }

        return {flow, cost};
    }
};



// vector<int> cl = {-1, 0, 1, 0, -1};

// vector<ll> cl = {-1, 0, 1, 1, 1, 0, -1, -1, -1, 0};

int main()
{
    ll te;
    cin >> te;
    while (te--) {
        ll n;
        string s;
        cin >> n >> s;
        if (s[0] == 'A') {
            if (n >= 2 && s[1] == 'B') {
                ll f = 0;
                for (int i = 2; i < n; ++i) {
                    if (s[i] == 'B') {
                        f = 1;
                        s[i] = 'A';
                    } else {
                        if (f == 1) break;
                    }
                }
            } else {
                if (n >= 2) s[1] = 'B';
                for (int i = 2; i < n; ++i) {
                    if (s[i] == 'B') {
                        s[i] = 'A';
                    } else {
                        break;
                    }
                }
            }
        } else {
            s[0] = 'A';
            for (int i = 1; i < n; ++i) {
                if (i == 1) {
                    if (s[i] == 'A') {
                        s[i] = 'B';
                        continue;
                    } else {
                        break;
                    }
                }
                if (s[i] == 'B') {
                    s[i] = 'A';
                } else {
                    break;
                }
            }
        }
        s[0] = 'B';
        cout << s << '\n';
    }
}
yukicoder

結果

ソースコード
