ABC 253 参加記

88分6完(5ペナ)で493位、パフォーマンスは1843でした。レートが1700を超えました！(次の日のARCで落ちましたが…)

A Median?

問題

整数$a, b, c$が与えられます。$b$がこれらの整数の中央値かどうか判定してね。

  • $1 \leq a, b, c \leq 100$

提出コード

int main(){

    vector<int> T(3); rep(i, 3) cin >> T[i];
    auto S = T;
    sort(all(S));

    YesNo(S[1] == T[1]);

}

B Distance Between Tokens

問題

$H$行$W$列のマス目があって、$2$つの異なるマスに駒が置かれてるよ。一方を上下左右の隣接マスに動かしてもう一方と同じマス目に移動するためには最小で何手必要？

  • $2 \leq H, W \leq 100$
  • $S_i(1 \leq i \leq H)$はo(コマ)か-(何も置かれてないマス)
  • ちょうど$2$つoが存在するよ

提出コード

int main(){

    ll H, W; cin >> H >> W;
    vector<string> A(H); for(int i = 0; i < H; i++) cin >> A[i];
    
    vpll B;

    rep(i, H) rep(j, W) if(A[i][j] == 'o'){
        B.pb({i, j});
    }
    ll ans = abs(B[0].fi - B[1].fi) + abs(B[0].se - B[1].se);
    cout << ans << '\n';
}

C Max - Min Query

問題

整数の多重集合$S$があって、最初$S$は空です。$Q$個のクエリをさばいてね。

  • 1 x : $S$に$x$を1つ追加
  • 2 x c: $S$から$x$を$\min(c, (Sに含まれるxの個数))$個削除
  • 3: ($S$の最大値) $-$ ($S$の最小値) を出力
  • $1 \leq Q \leq 2 \times 10^5$
  • $0 \leq x \leq 10^9$
  • $1 \leq c \leq Q$
  • 3のクエリを処理するとき、$S$は空でない

考察

multisetでもできるかもしれないけど大変そうなのでmapで値と個数を持つようにします。こうすると頑張るとできます。

提出コード

int main(){

    ll Q; cin >> Q;

    map<int, int> S;
    while(Q--){
        int t; cin >> t;
        if(t == 1){
            int x; cin >> x;
            S[x]++;
        }elif(t == 2){
            int x, c; cin >> x >> c;
            S[x] -= c;
            if(S[x] <= 0) S.erase(x);
        }else{
            auto min = S.begin();
            auto max = S.end(); max--;
            cout << abs(max->fi - min->fi) << endl;
        }
    }

}

どっちが大きいのかわすれちゃったからとりあえずabsをしちゃいました　先頭が小さくて後ろが大きいです。

D FizzBuzz Sum hard

問題

$1$以上$N$以下の整数で$A$の倍数でも$B$の倍数でもないものの総和をもとめてね。

  • $1 \leq N, A, B \leq 10^9$

考察

総和じゃなくて個数だとだいぶ有名な気がします。個数で考えて適当に総和にするとよいです。

$f(x) = \cfrac{x(x+1)}{2}$としたとき、答えは$f(N) - Af(N/A) - Bf(N/B) + \text{lcm}(A, B) f(N/\text{lcm}(A, B))$(割り算は切り捨て)

となります。ベン図を考えるとわかりやすいです。$\text{lcm}(A, B)$を$A \times B$としてしまい1ペナ…

提出コード

/*最大公約数*/
ll gcd(ll x, ll y){
    if (x < y) swap(x, y);
    while (y > 0){
        ll r = x % y;
        x = y;
        y = r;
    }
    return x;
}
/*最小公倍数*/
ll lcm(ll x,ll y){
    return x * y / (gcd(x, y));
}

ll su(ll n){
    return n * (n+1) / 2;
}


int main(){

    ll N, A, B; cin >> N >> A >> B;

    ll ans = 0;
    ans += su(N);
    ans -= A * su(N / A);
    ans -= B * su(N / B);
    ans += lcm(A, B) * su(N / lcm(A, B));

    cout << ans << '\n';

}

E Distance Sequence

問題

長さ$N$の整数からなる数列$A = (A_1, \cdots, A_N)$であって、以下の条件をすべて満たすものは何通りありますか？

  • $1 \leq A_i \leq M~(1 \leq i \leq N)$
  • $|A_i - A_{i+1}| \geq K~(1 \leq i \leq N-1)$

ただし、答えは大きくなるので$998244353$で割ったあまりを求めてね

  • $2 \leq N \leq 1000$
  • $1 \leq M \leq 5000$
  • $0 \leq K \leq M-1$

考察

DPしてねって問題に書いてあるのでDPします。普通にやるとやばいのでうまい感じにやります。僕は累積和を使いました。

$K=0$の時は壊れちゃうので別で処理を書きましょう。これを忘れて1ペナしました。

提出コード

// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/Modint.md
// https://github.com/Kyo-s-s/Kyo_s_s_Library/blob/main/md/CumulativeSum.md


int main(){

    ll N, M, K; cin >> N >> M >> K;
    
    vector<Mint> dp(M, 1);

    if(K == 0){
        auto m = Mint(M);
        m = m.pow(N);
        cout << m << endl;
        exit(0);
    }


    rep(n, N - 1){

        vector<Mint> pd(M, 0);
        CumulativeSum Cum(dp);
        Mint Sum = sum(dp);
        Cum.build();

        rep(m, M){
            ll low = max(m - K + 1, 0LL);
            ll hig = min(M, m + K);

            pd[m] = Sum - Cum.sum(low, hig);
        }
        swap(dp, pd);

    }
    
    Mint ans = sum(dp);
    cout << ans << endl;

}

F Operations on a Matrix

問題

縦$N$行横$M$列の行列があり、はじめすべての成分は$0$です。以下のクエリを$Q$個さばいてね。

  • 1 l r x : $l, l+1, \cdots, r$列目の成分すべてに$x$を足す
  • 2 i x: $i$行目の成分すべてを$x$で書き換える
  • 3 i j: $(i, j)$成分を出力する
  • $1 \leq N, M, Q \leq 2 \times 10^5$
  • $1 \leq l \leq r \leq M$
  • $1 \leq i, j \leq N$
  • $1 \leq x \leq 10^9$

考察

最後にクエリ2が来てから何が足されたかを見ることによって$(i, j)$成分についての値を答えることができます。

クエリを逆から読んでいきます。クエリ2を読んだときにその行のそれ以前のクエリ3についての答えが確定します。これをやります。最初に2 i 0($1 \leq i \leq N$)があることにしておくと実装が楽です。クエリ1は区間加算なので遅延セグ木を持ってきます。

提出コード

#include <atcoder/all>
using namespace atcoder;

struct q {
    int t, l, r, i, j, x;
};

using S = long long;
using F = long long;

const S INF2 = 8e18;

S op(S a, S b){ return std::max(a, b); }
S e(){ return -INF2; }
S mapping(F f, S x){ return f+x; }
F composition(F f, F g){ return f+g; }
F id(){ return 0; }


int main(){

    ll N, M, Q; cin >> N >> M >> Q;
    vector<q> Query;

    rep(i, N){
        q add;
        add.t = 2;
        add.i = i + 1;
        add.x = 0;
        Query.pb(add);
    }

    rep(u, Q){
        q add;
        cin >> add.t;
        if(add.t == 1) cin >> add.l >> add.r >> add.x;
        elif(add.t == 2) cin >> add.i >> add.x;
        else cin >> add.i >> add.j;
        Query.pb(add);   
    }

    reverse(all(Query));
    vector<pll> Ans; // idx, val
    vector<S> v(M + 10, 0);

    lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
    vector<vector<tuple<ll, ll, ll>>> Index(N + 10);    // i行列に対し、<j列目でidxでその時の遅延セグ木のval>　の行列

    ll idx = Q + 1;
    for(auto que: Query){
        if(que.t == 1){
            seg.apply(que.l, que.r+1, que.x);
        }elif(que.t == 2){
            for(auto [j, in, va]: Index[que.i]){
                ll val = seg.get(j);
                ll an = val - va + que.x;
                Ans.pb({in, an});
            }
            Index[que.i].resize(0);
        }else{
            ll val = seg.get(que.j);
            Index[que.i].pb({que.j, idx, val});
        }
        idx--;
    }

    sort(all(Ans));

    for(auto [in, an]: Ans) cout << an << "\n";

}

バグらせそうだったので1-indexedで書きました。焦って書いたのでぐちゃぐちゃです…

Comment is disabled to avoid unwanted discussions from 'localhost:1313' on your Disqus account...

Theme Name