ACL Beginner Contest

atcoder.jp

更新はや
Bondo416さんのACL Beginner Contestでの成績：921位
パフォーマンス：1327相当
レーティング：1422→1412 (-10) :(#AtCoder #ACLBeginnerContest https://t.co/ka2zry80qp

— ボンド@競プロ (@bond_cmprog) September 26, 2020

A - Repeat ACL

K回"ACL"を繋げたものを出力する
提出コード

void solve(){
    string S = "ACL";
    int K;
    cin >> K;
    string ans = "";
    REP(i,K) ans += S;
    cout << ans << endl;
}

B - Integer Preference

片方の区間の端点がもう片方の区間内に入っていればいい
もしくは、どちらかの最大がもう片方の最小未満なら"No"になる
提出コード

void solve(){
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    if((A <= C and C <= B) or (A <= D and D <= B) or (C <= A and A <= D) or (C <= B and B <= D)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Connect Cities

UnionFindを使って与えられた辺で頂点同士を結ぶ
全部くっつければいいので1頂点を固定してmergeされてないものをどんどんmergeしていき、その回数を答える
各連結成分同士を結ぶには1辺あれば結ぶ事ができるので連結成分の個数-1でも求められる
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    UnionFind uf(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        uf.unite(u, v);
    }
    int ans = 0;
    for(int i=1;i<N;i++){
        if(uf.issame(0, i)) continue;
        uf.unite(0, i);
        ans++;
    }
    cout << ans << endl;
}

D - Flat Subsequence

インラインDPとかっていうらしい
最後にiを選んだときの数列Bの長さの最大とする
今を見ている時の更新式はとなる
これを愚直にやると、間に合わないので工夫する必要がある
更新式を見ると、ある区間内の最大を1つ取得できればいい
そのためセグメント木を使うことで区間内の最大を高速に求めることが出来る
よって、セグメント木にdp配列を載せて上記の様に更新していけばいい
提出コード

int op(int a, int b){
    return max(a, b);
}

int e(){
    return 0;
}

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<int> dp(303030);
    segtree<int, op, e> seg(303030);
    seg.set(A[0], 1);
    for(int i=1;i<N;i++){
        int l = max(0, A[i] - K);
        int r = min(303030-1, A[i] + K);
        int ma = seg.prod(l, r+1);
        seg.set(A[i], ma + 1);
    }
    cout << seg.all_prod() << endl;
}

E - Replace Digits

見た目が遅延セグ木なんだけど載せ方が全然わからなかった
アルメリアさんの記事と、解説放送がとてもわかりやすかった
実装は解説放送を参考にした

今、「1111」と「2222」が与えられて「11112222」を作りたいとする
これはとできればこれを達成することが出来る
これは、構造体Sに区間のサイズ、もしくはを直接持たせてあげればいい
また、ある区間「1234」を全て1で置き換えて「1111」を作りたいとする
置き換えたい値を「F l」その対象を「S r」とする
をr.bekiとすると、と置き換えればいい
割り算そのままでも通ったけど、結構重いので予め定数にしておくといいっぽい
betrue12.hateblo.jp

提出コード

using mint = modint998244353;

struct S {
    mint a;
    mint beki;
};

using F = int;

S op(S l, S r) { return S{l.a * r.beki + r.a, l.beki * r.beki}; }
S e() { return S{0, 1}; }

S mapping(F l, S r) {
    if(l != 0) return S{(r.beki-1)/9 * l, r.beki};
    else return r;
}

F composition(F l, F r) {
    return (l == 0 ? r : l);
}

F id() { return 0; }


void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<S> a(N, {1, 10});
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);

    while(Q--){
        int l, r, D;
        cin >> l >> r >> D;
        --l;
        seg.apply(l, r, D);
        printf("%d\n", seg.all_prod().a.val());
    }
}