AtCoder Beginner Contest 188（ABC188）

atcoder.jp

冷え
Bondo416さんのAtCoder Beginner Contest 188での成績：2857位
パフォーマンス：892相当
レーティング：1478→1432 (-46) :(#AtCoder #ABC188 https://t.co/Hv9RlsSvQC

— ボンド@競プロ (@bond_cmprog) January 10, 2021

A - Three-Point Shot

$ \min(a, b) + 3 \gt \max(a, b) $かどうかをチェック
提出コード

void solve(){
    int X, Y;
    cin >> X >> Y;
    if(X > Y) swap(X, Y);
    if(X + 3 > Y) cout << "Yes" << endl;
    else cout << "No" << endl;
}

B - Orthogonality

問題文の通りに$ A_i \times B_i $の総和を求めてそれが0かどうか調べる
提出コード

void solve(){
    int N;
    cin >> N;
    ll sum = 0;
    vector<int> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];

    REP(i,N) sum += A[i] * B[i];
    if(sum == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

C - ABC Tournament

$ N $が小さいので愚直にシミュレートをすればいい
シミュレートして最後に負けた人が答え
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(1<<N);
    REP(i,1<<N) cin >> A[i];
    vector<int> idx(1<<N);
    iota(idx.begin(), idx.end(), 0);
    int ans = 0;
    while((int)idx.size() > 1){
        vector<int> next;
        for(int i=0;i<(int)idx.size();i+=2){
            if(A[idx[i]] > A[idx[i+1]]){
                ans = idx[i+1];
                next.emplace_back(idx[i]);
            }
            else{
                ans = idx[i];
                next.emplace_back(idx[i+1]);
            }
        }
        idx = next;
    }
    cout << ans + 1 << endl;
}

D - Snuke Prime

imos法で一日あたりのコストを$ imos_i $として求めておけば各日において
$ \min(imos_i, C) $の総和が答えとなる
ただし、値が大きいので座圧する必要がある
イベントソートだと座圧しなくても解くことが出来る
提出コード

void solve(){
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> a(N), b(N), c(N);
    Compress<ll> cmp;
    REP(i,N){
        cin >> a[i] >> b[i] >> c[i];
        cmp.add(a[i]);
        cmp.add(b[i]+1);
    }
    cmp.build();
    int sz = cmp.size();
    vector<ll> imos(sz+1);
    REP(i,N){
        imos[cmp.get(a[i])] += c[i];
        imos[cmp.get(b[i]+1)] -= c[i];
    }
    REP(i,sz) imos[i+1] += imos[i];
    ll ans = 0;
    REP(i,sz-1){
        ans += min(imos[i], C) * (cmp[i+1] - cmp[i]);
    }
    cout << ans << endl;
}

提出コード（イベントソート）

void solve(){
    int N;
    ll C;
    cin >> N >> C;
    vector<ll> a(N), b(N), c(N);
    vector<pair<ll, ll>> event;
    REP(i,N){
        cin >> a[i] >> b[i] >> c[i];
        event.emplace_back(a[i], c[i]);
        event.emplace_back(b[i]+1, -c[i]);
    }
    sort(event.begin(), event.end());
    ll ans = 0, pre = 0, cur_c = 0;
    for(auto [d, cost] : event){
        ans += min(cur_c, C) * (d - pre);
        pre = d;
        cur_c += cost;
    }
    cout << ans << endl;
}

E - Peddler

制約から与えられるグラフはDAGとなる
そのため町$ i $から移動できる町を$ j $とすると
$ dp[j] = \min(dp[j], dp[i], A_i) $として町$ j $に辿り着ける町の中で金の最安値として$ i $の昇順にdpをする
そうすると各町$ i $の$ A_i - dp[i] $の最大値が答え
解説の解法2だとDAGじゃなくても解ける
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        g[--x].emplace_back(--y);
    }
 
    vector<ll> dp(N, LINF);
    REP(i,N){
        for(auto nv : g[i]) chmin(dp[nv], min(A[i], dp[i]));
    }
    ll ans = -LINF;
    REP(i,N) chmax(ans, A[i] - dp[i]);
    cout << ans << endl;
}

提出コード（解法2）

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    vector<vector<int>> g(N);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        g[--x].emplace_back(--y);
    }
    vector<int> idx(N);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y){
        return A[x] < A[y];
    });
    vector<bool> used(N);
    ll ans = -LINF;
    for(int i : idx){
        if(used[i]) continue;
        queue<int> q;
        q.emplace(i);
        while(!q.empty()){
            int v = q.front(); q.pop();
            for(auto nv : g[v]){
                if(used[nv]) continue;
                chmax(ans, A[nv] - A[i]);
                q.emplace(nv);
                used[nv] = true;
            }
        }
    }
    cout << ans << endl;
}

F - +1-1x2

類題がAGCにあるのでよしなにする
解説（AGCのだけど）はアルメリアさんのものがわかりやすいと思うので割愛（サボり）
atcoder.jp
betrue12.hateblo.jp

提出コード

void solve(){
    ll X, Y;
    cin >> X >> Y;
    ll ans = LINF;
    map<ll, ll> memo;
    priority_queue<LP, vector<LP>, greater<LP>> pq;
    pq.emplace(0, Y);
    while(!pq.empty()){
        auto [v, x] = pq.top(); pq.pop();

        if(v >= ans) continue;
        chmin(ans, v + abs(X-x));

        int r = (x & 1);
        ll nv = v + r + 1;
        int d = 2;
        if(nv < ans && (!memo.count(x / d) || nv < memo[x/d])){
            pq.emplace(nv, x / d);
            memo[x / d] = nv;
        }
        nv = v + (d - r) + 1;
        if(nv < ans && (!memo.count(x / d + 1) || nv < memo[x/d + 1])){
            pq.emplace(nv, x / d + 1);
            memo[x / d + 1] = nv;
        }
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 187（ABC187）

atcoder.jp

しょっぱい
Bondo416さんのAtCoder Beginner Contest 187での成績：1031位
パフォーマンス：1451相当
レーティング：1481→1478 (-3) :(#AtCoder #ABC187 https://t.co/2FGkSRg73O

— ボンド@競プロ (@bond_cmprog) January 2, 2021

A - Large Digits

桁和を求めてそのmaxを出力する
提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    int suma = 0, sumb = 0;
    while(A > 0){
        suma += A % 10;
        A /= 10;
    }
    while(B > 0){
        sumb += B % 10;
        B /= 10;
    }
    cout << max(suma, sumb) << endl;
}

B - Gentle Pairs

傾きは$ \frac{y_i - y_j}{x_j - x_i} $なので$ -1 \leq \frac{y_j - y_i}{x_j - x_i} \leq 1 $を満たすものを数えればいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    int ans = 0;
    REP(i,N) for(int j=i+1;j<N;j++){
        int xx = x[j] - x[i];
        int yy = y[j] - y[i];
        if(abs(yy) <= abs(xx)) ans++;
    }
    cout << ans << endl;
}

C - 1-SAT

!がついているものとついていないものをそれぞれsetなどで管理する
!がついている文字列を見ていき、!を除いた文字列がもう片方のsetに入っていればそれを出力する
提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    set<string> st;
    set<string> ex;
    REP(i,N){
        if(S[i][0] == '!') ex.insert(S[i]);
        else st.insert(S[i]);
    }
    for(auto s : ex){
        if(st.find(s.substr(1,(int)s.size())) != st.end()){
            cout << s.substr(1, (int)s.size()) << endl;
            return;
        }
    }
    cout << "satisfiable" << endl;
}

D - Sum of difference

$ i $番目の町で演説すると高橋くんは$ A_i + B_i $票、青木くんは$ - A_i $票得られる
よって高橋くんが得する票数はその差分$ A_i + B_i - (- A_i) = 2A_i + B_i $になる
そのためこの降順にソートして貪欲に演説していけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    // vector<ll> A(N), B(N);
    vector<pair<ll, ll>> v(N);
    ll sumA = 0;
    REP(i,N){
        ll A, B;
        cin >> A >> B;
        sumA += A;
        v[i].first = 2 * A + B;
        v[i].second = A;
    }
    sort(v.rbegin(), v.rend());
    ll sum = 0;
    REP(i,N){
        sum += v[i].first - v[i].second;
        sumA -= v[i].second;
        // dumps(v[i].first, v[i].second);
        if(sum > sumA){
            cout << i + 1 << endl;
            return;
        }
    }
}

E - Through Path

適当な頂点を根とした根付き木として考える
そうすると各クエリはある頂点の部分木に$ x $加算するか部分木以外の全頂点に$ x $加算するクエリになる
どちらの点が部分木に含まれるかどうかは予めdfsなどで各頂点の深さを求めておき、深い方の頂点を部分木の頂点とすればいい
ここで部分木以外の全頂点に加算するクエリを全頂点に$ x $加算し、部分木に$ - x$加算するクエリとすれば全て部分木に加算するクエリにまとめられる
全体に加算する値と各頂点にその頂点の部分木にどれだけ加算するかの値を持っておけば最後に根から木上の累積和を取ればいい
オイラーツアー + imos法とかでも解ける
提出コード

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> g(n);
    vector<int> a(n), b(n);
    REP(i,n-1){
        cin >> a[i] >> b[i];
        g[--a[i]].emplace_back(--b[i]);
        g[b[i]].emplace_back(a[i]);
    }
    vector<ll> plus(n), minus(n);
    int q;
    cin >> q;
    ll sum = 0;
    vector<int> depth(n);
    auto rec = [&](auto && self, int v, int par, int dep = 0)->void{
        depth[v] = dep;
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, dep + 1);
        }
    };
    rec(rec, 0, -1);
    while(q--){
        int t, e, x;
        cin >> t >> e >> x;
        --e;
        dumps(depth[a[e]], depth[b[e]]);
        if(t == 1){
            if(depth[a[e]] < depth[b[e]]){
                sum += x;
                minus[b[e]] += x;
            }
            else{
                plus[a[e]] += x;
            }
        }
        else{
            if(depth[a[e]] < depth[b[e]]){
                plus[b[e]] += x;
            }
            else{
                sum += x;
                minus[a[e]] += x;
            }
        }
    }
    vector<ll> ans(n);
    auto dfs = [&](auto && self, int v, int par, ll num) -> void{
        ans[v] = sum + num + plus[v] - minus[v];
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v, num + plus[v] - minus[v]);
        }
    };
    dfs(dfs, 0, -1, 0);
    REP(i,n) cout << ans[i] << endl;
}

提出コード（オイラーツアー + imos）

void solve(){
    int N;
    cin >> N;
    vector<vector<int>> g(N);
    vector<pair<int, int>> edge(N);
    REP(i,N-1){
        int a, b;
        cin >> a >> b;
        g[--a].emplace_back(--b);
        g[b].emplace_back(a);
        edge[i] = make_pair(a, b);
    }
    vector<int> ls(N), rs(N);
    int idx = 0;
    auto dfs = [&](auto && self, int v, int par) -> void{
        ls[v] = idx++;
        for(auto nv : g[v]){
            if(nv == par) continue;
            self(self, nv, v);
        }
        rs[v] = idx;
    };
    dfs(dfs, 0, -1);
    vector<ll> imos(N+1);
    int q;
    cin >> q;
    while(q--){
        int t, e, x;
        cin >> t >> e >> x;
        auto [a, b] = edge[--e];
        if(t == 2) swap(a, b);
        if(ls[a] < ls[b]){
            imos[0] += x;
            imos[N] -= x;
            imos[ls[b]] -= x;
            imos[rs[b]] += x;
        }
        else{
            imos[ls[a]] += x;
            imos[rs[a]] -= x;
        }
    }
    REP(i,N) imos[i+1] += imos[i];
    REP(i,N) cout << imos[ls[i]] << "\n";
}

F - Close Group

まず、全ての集合についてその集合がクリークかどうかを前計算で求める
ある集合にその集合に含まれない頂点を1つ加えるとすると、その頂点から集合に含まれる全ての頂点にへの辺が存在すればその頂点を加えた集合もクリークになる
その次に、ある集合が最小何個のクリークで構成出来るかbitDPで求めればいい
これはある集合に対し、その部分集合を列挙すれば良く、$ \mathcal{O}(3^N) $で出来る
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> g(N);
    REP(i,M){
        int A, B;
        cin >> A >> B;
        --A, --B;
        g[A] |= (1 << B);
        g[B] |= (1 << A);
    }
    vector<int> dp(1<<N, INF);
    dp[0] = 1;
    REP(i,1<<N) REP(j,N) if(i >> j & 1){
        int tar = i - (1 << j);
        if(dp[tar] <= 1 and (g[j] & tar) == tar) dp[i] = 1;
    }
    for(int i=1;i<(1<<N);i++){
        for(int j=i;j>0;j=(j-1)&i){
            chmin(dp[i], dp[i^j] + dp[j]);
        }
    }
    cout << dp[(1<<N)-1] << endl;
}

パナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）

atcoder.jp

うーん
Bondo416さんのパナソニックプログラミングコンテスト（AtCoder Beginner Contest 186）での成績：1171位
パフォーマンス：1348相当
レーティング：1495→1481 (-14) :(#AtCoder #パナソニックプログラミングコンテスト（ABC186） https://t.co/yIAfE6aq4D

— ボンド@競プロ (@bond_cmprog) December 19, 2020

A - Brick

$ \lceil \frac{N}{W} \rceil $ を出力
提出コード

void solve(){
    int N, W;
    cin >> N >> W;
    cout << N / W << endl;
}

B - Blocks on Grid

一番小さい値に合わせればいいのでその差分の和が答え
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector A(H, vector(W, 0));
    int mi = INF;
    REP(i,H) REP(j,W){
        cin >> A[i][j];
        chmin(mi, A[i][j]);
    }
    int ans = 0;
    REP(i,H) REP(j,W) ans += A[i][j] - mi;
    cout << ans << endl;
}

C - Unlucky 7

正の整数を10進法と8進法に変換するのは愚直にやっても間に合うので全探索すればいい
提出コード

void solve(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i=1;i<=N;i++){
        int tmp = i;
        bool ok = false;
        while(tmp > 0){
            int num = tmp % 10;
            if(num == 7) ok = true;
            tmp /= 10;
        }
        tmp = i;
        while(tmp > 0){
            int num = tmp % 8;
            if(num == 7) ok = true;
            tmp /= 8;
        }
        if(ok) ans++;
    }
    cout << N - ans << endl;
}

D - Sum of difference

絶対値が扱いにくいので降順ソートをすると$ A_i - A_j \geq 0 $となって扱いやすい
$ A_i $を固定すると
$ A_i - A_{i + 1} + A_i - A_{i+2} + ... + A_i - A_{N - 1} = A_i * (N - i - 1) - \sum _{j = i + 1} ^{N - 1} A_j $
となるので、予め累積和を求めておけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    sort(A.rbegin(), A.rend());
    vector<ll> cum(N+1);
    for(int i=N-1;i>=0;i--) cum[i] = cum[i+1] + A[i];
    ll ans = 0;
    REP(i,N){
        ans += A[i] * (N - i -1) - cum[i+1];
    }
    cout << ans << endl;
}

E - Throne

何回移動したかを$ x $とすると$ S + Kx \equiv 0 \pmod N $を満たす$ x $を求められればいい
これは$ K $の逆元が存在すれば求めることが出来る
まず、$ g = gcd(N, S, K) $とし、$N = N / g, S = S / g, K = K / g $と置き換える
$gcd(N, K) \neq 1 $のとき、$ K $の逆元が存在しないので-1
それ以外の場合逆元を求めれば良く、ACLのinv_modを使えばこれを求められる
また、$ y = Kx $とし、$ S + Kx \equiv 0 \pmod N $を

• $ y \equiv 0 \pmod K $
• $ y \equiv -S \pmod N $

とすれば、中国剰余定理で解が存在するかどうかと、存在すればその解を求めることが出来る
提出コード

void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    ll g = gcd(gcd(N, S), K);
    N /= g, S /= g, K /= g;
    if(gcd(N, K) != 1){
        cout << -1 << endl;
        return;
    }
    cout << (N - S + N) % N * inv_mod(K, N) % N << endl;
}

提出コード（中国剰余定理）

void solve(){
    ll N, S, K;
    cin >> N >> S >> K;
    auto [y, z] = crt({0, N-S}, {K, N});
    if(y == 0) cout << -1 << endl;
    else cout << y / K << endl;
}

F - Rook on Grid

移動方法を考えると、最初に右に移動し、次に下に移動する、もしくは最初に下に移動し、次に右に移動するの2パターン考えられる
右・下の移動を考えると、各列において最初にぶつかる障害物までの位置を求めることで移動可能なマスを数えられ、下・右の場合も同様に求められる
$ w_i $を$ i $列目に一番上にある障害物の位置、$ h_i $を$ i $行目の一番左にある障害物の位置とすると
それぞれの移動可能なマスは$ \sum _{i = 0} ^{h_0} w_i + \sum _{i = 0} ^{w_0} h_i $となる
ただし、重複して数えているマスがあるので重複マスを引いて上げる必要がある
上から順に各行を見ていき、各マスがすでに障害物が出現したかどうかをBITなどで管理し、その総和を引いていけばいい
提出コード

void solve(){
    int H, W, M;
    cin >> H >> W >> M;
    vector<int> h(H, W), w(W, H);
    REP(i,M){
        int x, y;
        cin >> x >> y;
        --x, --y;
        chmin(w[y], x);
        chmin(h[x], y);
    }
    ll ans = 0;
    REP(i,w[0]) ans += h[i];
    REP(i,h[0]) ans += w[i];
    BIT<int> bit(W);
    REP(i,h[0]) bit.add(i,1);
    vector<vector<int>> obj(H+1);
    REP(i,h[0]) obj[w[i]].emplace_back(i);
    REP(i,w[0]){
        for(auto j : obj[i]) bit.add(j, -1);
        ans -= bit.sum(0, h[i]);
    }
    cout << ans << endl;
}

Codeforces Round #690 (Div. 3)

codeforces.com

A. Favorite Sequence

問題文に書いてあるとおりに前後前後…の順に出力
deque使えば楽だったね
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> b(n);
    REP(i,n) cin >> b[i];
    vector<int> ans;
    REP(i,n/2){
        ans.emplace_back(b[i]);
        ans.emplace_back(b[n-i-1]);
    }
    if(n & 1) ans.emplace_back(b[n/2]);
    REP(i,n) cout << ans[i] << " ";
    cout << endl;
}

B. Last Year's Substring

先頭からのsubstringと後ろからのsubstringで2020を作れるかを判定する
提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    if(n < 4){
        cout << "NO" << endl;
        return;
    }

    for(int i=0;i<=4;i++){
        string t = s.substr(0,i);
        t += s.substr(n-4+i, 4-i);
        if(t == "2020"){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

C. Unique Number

よくわからないので手元で計算して埋め込んだ
和が大きくなるように貪欲に作っていって、出来た文字列をソートすればいい
提出コード

vector<ll> mi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 189, 289, 389, 489, 589, 689,789, 1789, 2789, 3789, 4789, 5789, 6789, 16789, 26789, 36789, 46789, 56789, 156789, 256789,356789, 456789, 1456789, 2456789, 3456789, 13456789, 23456789, 123456789, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000};
void solve(){
    int x;
    cin >> x;
    ll ans = mi[x];
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

D. Number into Sequence

操作を行って最終的に残る数を$ x $とすると、$ x, x, x, ... $のように$ x $が連続したものになる
$ a $の総和は不変のため、上記のような$ x $の候補は総和の約数になる
よってこの約数それぞれに対し、操作が可能かどうかと可能ならその操作回数を調べればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    REP(i,n){
        cin >> a[i];
        sum += a[i];
    }
    auto res = divisor(sum);
    ll ans = n-1;
    for(auto x : res){
        int cur = 0;
        REP(i,n){
            cur += a[i];
            if(cur == x) cur = 0;
            else if(cur > x){
                cur = -1;
                break;
            }
        }
        if(cur == 0){
            chmin(ans, n-sum/x);
        }
    }
    cout << ans << endl;
}

E2. Close Tuples (hard version)

数列をソートして考える
このとき最小値を固定してその組み合わせの数を加算していく
$ a_i $を最小値として固定したとき、$ a_i + a_r \leq k $を満たす一番右端のindexを$ r $とすると、$ r - i - 1 $個の中から$ m - 1 $個選ぶ組み合わせの数になるので各$ i $に対して$ _{r - i - 1} C _{m - 1} $の総和を求めればいい
提出コード

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());

    mint ans = 0;
    REP(i,n){
        int t = upper_bound(a.begin(), a.end(), a[i]+k) - a.begin();
        t -= (i + 1);
        if(t >= m-1) ans += bc.com(t, m-1);
    }
    cout << ans << endl;
}

F. The Treasure of The Segments

区間$ [ l_i, r_i] $がいくつの区間を覆っているかは、全ての区間の個数から$ r_j \lt l_i $を満たす個数と$ r_i \lt l_k $を満たす個数を引いたものになる
これは累積和を使えば計算できるが、値が大きいので座圧する必要がある
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    Compress<int> cmp;
    REP(i,n){
        cin >> l[i] >> r[i];
        cmp.add(l[i]);
        cmp.add(r[i]);
    }
    cmp.add(0);
    cmp.add(INF+10);
    cmp.build();
    int sz = cmp.size();
    vector<int> cumL(sz+1), cumR(sz+1);
    REP(i,n){
        cumL[cmp.get(r[i])]++;
        cumR[cmp.get(l[i])]++;
    }
    REP(i,sz) cumL[i+1] += cumL[i];
    for(int i=sz-1;i>0;i--) cumR[i-1] += cumR[i];
    int ans = 0;
    REP(i,n){
        chmax(ans, n - cumL[cmp.get(l[i])-1] - cumR[cmp.get(r[i])+1]);
    }
    cout << n - ans << endl;
}

AtCoder Beginner Contest 185（ABC185）

atcoder.jp

ちょい冷え
Bondo416さんのAtCoder Beginner Contest 185での成績：1030位
パフォーマンス：1447相当
レーティング：1501→1495 (-6) :(#AtCoder #ABC185 https://t.co/KXWAcGGx4A

— ボンド@競プロ (@bond_cmprog) December 13, 2020

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();
    }
}