AtCoder Library Beginner Contest ABL 参加記

ABC3完でした。Dは冷静になりたかった。。。勉強不足です。

A - Repeat ACL

問題へのリンク

解説

for文を使います。

実装

int main() {
    int K;
    cin >> K;
    rep(i,K){
        cout <<"ACL";
    }
    cout << endl;
}

B - Integer Preference

問題へのリンク

解説

区間の位置を固定して、真ん中が交叉してるかを考えればよいです。swapを忘れて1WA。

実装

int main() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    if(A > C){
        swap(A, C);
        swap(B, D);
    }
    if(C <= B){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

C - Connect Cities

問題へのリンク

解説

連結成分を一つの頂点だとみなして、連結させるには、連結成分数 - 1回です。

実装

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind T(N);
    rep(i,M){
        int a, b;
        cin >> a >> b;
        a--, b--;
        T.unite(a, b);
    }
    cout << T.group_num() - 1 << endl;
}

D - Flat Subsequence

問題へのリンク

解説

in-place DPというやつらしいです。値を添字に持つこと、もらうDPにすると区間になるので、セグ木で高速化できます。

以下のけんちょんさんの記事に丁寧に解説されています。LISがこれで求められるのは確かにとなりますね。

qiita.com

実装

#include<atcoder/segtree>

ll op(ll a, ll b){
    return max(a, b);
}
ll e(){
    return 0;
}
const int A_MAX = 300010;
int main() {
    int N, K;
    cin >> N >> K;
    atcoder::segtree<int, op, e> S(A_MAX);
    vector<int> A(N);
    rep(i,N)cin >> A[i];
    ll ans = 0;
    for(int i = 0; i < N; i++){
        int l = max(0, A[i] - K);
        int r = min(A_MAX-1, A[i]+K+1);
        ll prod = S.prod(l, r);
        S.set(A[i], prod+1);
        chmax(ans, prod+1);
    }
    cout << ans << endl;
}