接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

AtCoder Beginner Contest 185(ABC185)

atcoder.jp

A - ABC Preparation

$ min(A_1, A_2, A_3, A_4) $を出力
提出コード

void solve(){
    int mi = 101;
    REP(i,4){
        int a;
        cin >> a;
        chmin(mi, a);
    }
    cout << mi << endl;
}

B - Smartphone Addiction

実際にシミュレートをし、途中で0以下になればNo
提出コード

void solve(){
    ll N, M, T;
    cin >> N >> M >> T;
    vector<ll> A(M), B(M);
    REP(i,M) cin >> A[i] >> B[i];
    ll cur = N;
    ll pre = 0;
    REP(i,M){
        cur -= (A[i] - pre);
        if(cur <= 0){
            cout << "No" << endl;
            return;
        }
        cur = min(N, cur + B[i] - A[i]);
        pre = B[i];
        // dump(cur);
    }
    cur -= T - pre;
    if(cur > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - Duodecim Ferra

$ dp[i][j] := i $個目まで見たときの長さの総和が$ j $のときの場合の数としてDPをする
想定解は$ _{L - 1} C _{11} $に等しい、気づかなかった
提出コード

void solve(){
    int L;
    cin >> L;
    vector dp(13, vector<ll>(222));
    dp[0][0] = 1;
    REP(i,12){
        REP(j,222){
            // i本目を何cmで切るか
            for(int k=1;k<=189;k++){
                if(j + k > L) continue;
                if(dp[i][j] == 0) continue;
                dp[i+1][j+k] += dp[i][j];
            }
        }
    }
    ll ans = 0;
    cout << dp[12][L] << endl;
}

D - Stamp

連続した白色の区間の長さが最小の部分がネックになるのでその長さを$ mi $とする
白色の区間の長さを$ k $とするとその区間は$ \lceil \frac{k}{mi} \rceil $回操作を行う必要があるので、その総和が答え
マス$ A $に$ 0, N+1 $を追加すると実装が少し楽
提出コード

void solve(){
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M);
    REP(i,M) cin >> A[i];
    if(M == 0){
        cout << 1 << endl;
        return;
    }
    if(N == M){
        cout << 0 << endl;
        return;
    }
    ll mi = LINF;
    A.emplace_back(0);
    A.emplace_back(N+1);
    ll sz = A.size();
    sort(A.begin(), A.end());
    REP(i,sz-1){
        if(A[i+1] - A[i] - 1 == 0) continue;
        chmin(mi, A[i+1] - A[i] - 1);
        // dump(mi);
    }
    ll ans = 0;
    REP(i,sz-1){
        ans += (A[i+1] - A[i] - 1 + mi - 1) / mi;
    }
    cout << ans << endl;
}

E - Sequence Matching

$ dp[i][j] := A $を $ i $文字目まで、$ B $を $ j $文字目まで見たときの$ x + y $の最小としてDPをする
これは編集距離と同様のことをやっている(本番中全然気づかなかった)
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(M);
    REP(i,N) cin >> A[i];
    REP(j,M) cin >> B[j];
    vector dp(N+1, vector(M+1, 0));
    REP(i,N+1) dp[i][0] = i;
    REP(j,M+1) dp[0][j] = j;
    for(int i=1;i<=N;i++) for(int j=1;j<=M;j++){
        dp[i][j] = min({dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (A[i-1] != B[j-1])});
    }
    cout << dp[N][M] << endl;
}

F - Range Xor Query

XORの区間和と一点更新はBITかセグ木に載せられるのでどちらかを使えばいい
本番中はセグ木を使った
提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;

    SegTree<long long> seg(N, [](long long a, long long b) {
            return a ^ b;
        },
        0);
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        seg.set(i, A[i]);
    }
    seg.build();
    REP(i,Q){
        ll T, X, Y;
        cin >> T >> X >> Y;
        X--;
        if(T == 1){
            ll x = seg.get(X, X+1);
            seg.update(X, x ^ Y);
        }
        else{
            cout << seg.get(X, Y) << endl;
        }
        // seg.print();
    }
}