接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 190（ABC190）

AtCoder Beginner Contest 190（ABC190）

AtCoderBeginnerContest AtCoderBeginnerContest190 ABC ABC190

atcoder.jp

A - Very Very Primitive Game

実際にシミュレートをし、先に操作を行えなくなった方の負け
提出コード

void solve(){
    int A, B, C;
    cin >> A >> B >> C;
    int x = C;
    while(A >= 0 and B >= 0){
        if(x) B--;
        else A--;
        x = 1 - x;
    }
    if(B == -1) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Magic 3

$ X_i \lt S $ and $ Y_i \gt D $を満たす$ i $が存在すればYesそうでなければNo
提出コード

void solve(){
    ll N, S, D;
    cin >> N >> S >> D;
    vector<int> X(N), Y(N);
    REP(i,N) cin >> X[i] >> Y[i];
    bool ok = false;
    REP(i,N){
        if(X[i] < S and Y[i] > D) ok = true;
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Bowls and Dishes

bit全探索をする
$ i $番目のbitが0のとき$ C_i $の皿にボールを乗せ、1のとき$ D_i $の皿にボールを乗せることにして全探索すればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    REP(i,M){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
    }
    int K;
    cin >> K;
    vector<int> C(K), D(K);
    REP(i,K){
        cin >> C[i] >> D[i];
        --C[i], --D[i];
    }
    int ans = 0;
    REP(i,1<<K){
        vector<int> ball(N);
        REP(j,K){
            // dumps(C[i], D[i]);
            if(i >> j & 1) ball[C[j]] = 1;
            else ball[D[j]] = 1;
        }
        int tmp = 0;
        REP(j,M){
            if(ball[A[j]] and ball[B[j]]) tmp++;
        }
        chmax(ans, tmp);
    }
    cout << ans << endl;
}

D - Staircase Sequences

難しい
等差数列の和を考える
$ n $を項数、$ a $を初項とすると$ N = \frac{n}{2} \left( 2a + n - 1 \right) $が成り立つ
$ 2N = n \left( 2a + n - 1 \right) $とすると、$ n $と$ 2a + n - 1 $は$ 2N $の約数となる
また、$ n $は$ 2N $の約数なので
$ \frac{2N}{n} = 2a + n - 1 $が成り立ち、$ \frac{2N}{n} - n + 1 = 2a $となる
よって、$ 2N $の約数を全列挙し、$ \frac{2N}{n} - n + 1 $が偶数になるかどうかを調べればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    int ans = 0;
    for(auto d : divisor(2*N)){
        ll x = 2 * N / d;
        if((x - d + 1) % 2 == 0) ans++;
    }
    cout << ans << endl;
}

E - Magical Ornament

任意のペア$ \left( i, j \right) \left( 1 \leq i, j \leq K \right) $についての$ \left( C_i, C_j \right) $間の最短経路がわかっていれば、bitDPで解くことができる
これは予め各$ C_i $を始点とした最短経路を求めておけばいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<ll> A(M), B(M);
    Dijkstra<ll> d(N, LINF);
    REP(i,M){
        cin >> A[i] >> B[i];
        --A[i], --B[i];
        d.make_edge(A[i], B[i], 1);
        d.make_edge(B[i], A[i], 1);
    }

    int K;
    cin >> K;
    vector<int> C(K);
    REP(i,K){
        cin >> C[i];
        --C[i];
    }

    vector dist(K, vector<ll>(K, LINF));
    REP(i,K){
        d.solve(C[i]);
        REP(j,K) if(i != j){
            chmin(dist[i][j], d.cost[C[j]]);
            chmin(dist[j][i], d.cost[C[j]]);
        }
    }

    vector dp(K, vector(1<<K, LINF));
    REP(i,K) dp[i][0] = 0;
    for(int bit=1;bit<(1<<K);bit++){
        REP(j,K) if(bit >> j & 1){
            REP(k,K){
                ll cost = dp[j][bit-(1<<j)] + dist[j][k];
                if(bit == ((1<<K) - 1)) chmin(dp[k][bit], dp[j][bit-(1<<j)]);
                chmin(dp[k][bit], cost);
            }
        }
    }

    ll ans = LINF;
    REP(i,K) chmin(ans, dp[i][(1<<K)-1]);

    if(ans == LINF) ans = -2;
    cout << ans + 1 << endl;
}

F - Shift and Inversions

$ k = 0 $の場合については、BITを使って転倒数を求めればいい
それ以外の場合を考える
今ある数列を$ [a_0, a_1, \dots, a_{N-1} ] $とすると操作後の数列は
$ [a_1, a_2, \dots, a_{N-1}, a_0] $となる
数列から$ a_0 $を取り除いたときの転倒数の変化を考えると$ [a_1, \dots, a_{N-1} ] $の中で$ a_0 $未満のものの個数分転倒数が減少する
また、数列の末尾に$ a_0 $を追加したときの転倒数の変化は、$ [a_1, \dots, a_{N-1} ] $の中で$ a_0 $より大きいものの個数分増加する
よって、一番はじめに転倒数を求めた後は上記のように各操作での転倒数の差分を計算すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(2*n);
    REP(i,n){
        cin >> a[i];
        ++a[i];
        a[i+n] = a[i];
    }
    ll ans = 0;
    BIT<int> b(n);
    REP(i,n){
        ans += i - b.sum1(a[i]);
        b.add1(a[i], 1);
    }
    for(int i=n;i<2*n;i++){
        cout << ans << endl;
        ans -= a[i-n] - 1;
        ans += n - a[i-n];
    }
}