接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 258（ABC258）

AtCoder Beginner Contest 258（ABC258）

AtCoderBeginnerContest AtCoderBeginnerContest258 ABC ABC258

atcoder.jp

A - When?

$ 21 + (K \geq 60 ) $ と $ K \pmod{60} $ を0埋めで出力

提出コード

void solve(){
    int K;
    cin >> K;
    printf("%02d:%02d\n",21+K/60,K%60);
}

B - Number Box

始点と方向を全探索して最大を求める

提出コード

void solve() {
    int N;
    cin >> N;
    vector A(N, vector<char>(N));
    REP(i,N) REP(j,N) {
       cin >> A[i][j];
    }
    ll ans = 0;
    REP(i,N) REP(j,N){
        REP(d,8) {
            string s  = "";
            REP(k,N) {
                int nx = i + dx[d] * k;
                int ny = j + dy[d] * k;
                nx = (nx + N) % N;
                ny = (ny + N) % N;
                s += A[nx][ny];
            }
            chmax(ans, stoll(s));
        }
    }
    cout << ans << endl;
}

C - Rotation

実際に操作を行う代わりに$ S_0 $ が文字列の何番目にあるかの変数を持つ

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    string s;
    cin >> s;
    int f = 0;
    while(Q--){
        int t, x;
        cin >> t >> x;
        if(t == 1) {
            f += x;
            f %= N;
        }
        else {
            --x;
            cout << s[(x - f + N)%N] << endl;
        }
    }
}

D - Trophy

ステージ $ i $ までクリアすることを全探索する
その際に、残りのプレイ回数は $ B_i $ 分のものをクリアするとして求める

提出コード

void solve(){
    ll N, X;
    cin >> N >> X;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    ll ans = 8 * LINF;
    ll sum = 0;
    REP(i,N){
        // i番目までクリア
        sum += A[i] + B[i];
        if(X-i-1>=0) chmin(ans, sum+(X-i-1)*B[i]);
    }
    cout << ans << endl;
}

E - Packing Potatoes

ダブリングをする
$ i \pmod{N} $ 番目のものから箱詰めを行い、新しい箱に変えるインデックス $ j \pmod{N} $ は一意に決まるのでこれをダブリングで求める

提出コード

void solve(){
    ll N, Q, X;
    cin >> N >> Q >> X;
    vector<ll> W(N);
    REP(i,N) cin >> W[i];
    vector<ll> cum(2*N+1);
    REP(i,2*N) cum[i+1] = cum[i] + W[i%N];
    vector to(45, vector<int>(N));
    vector val(45, vector<ll>(N));
    ll sum = accumulate(ALL(W), 0LL);
    REP(i,N) {
        ll cnt = X / sum;
        dumps(sum, cnt, X, cum[i]);
        ll t = lower_bound(ALL(cum), cum[i]+(X%sum)) - cum.begin();
        to[0][i] = t % N;
        val[0][i] = t - i + N * cnt;
        dumps(i, t);
    }
    REP(i,44) REP(j,N) {
        to[i+1][j] = to[i][to[i][j]];
        val[i+1][j] = val[i][j] + val[i][to[i][j]];
    }
    while(Q--){
        ll K;
        cin >> K;
        ll cur = 0;
        ll pre = 0;
        ll cur_ans = 0;
        ll pre_ans = 0;
        REP(i,45) if(K >> i & 1) {
            cur_ans += val[i][cur];
            cur = to[i][cur];
        }
        REP(i,45) if((K-1) >> i & 1){
            pre_ans += val[i][pre];
            pre = to[i][pre];
        }
        cout << cur_ans - pre_ans << endl;
    }
}

G - Triangle

$ A_i $ を2進数として見たときに、$ i, j $ を固定したときの条件を満たす $ k $ の個数は $ A_i \& A_j $ の立っているビットの個数と等しくなる
$ A_i $ を2進数をbitsetで管理することで実行時間以内に間に合う

提出コード

void solve(){
    int N;
    cin >> N;
    vector<bitset<3000>> vs;
    REP(i,N){
        string s;
        cin >> s;
        reverse(ALL(s));
        vs.emplace_back(bitset<3000>(s));
    }
    ll ans = 0;
    REP(i,N) REP(j,i+1,N) if(vs[i][j]) {
        ans += (vs[i] & vs[j]).count();
    }
    cout << ans / 3 << endl;
}