競プロやります。

競プロを頑張るブログです。

トップ > ABC/ARC > AtCoder Beginner Contest 117

AtCoder Beginner Contest 117

ABC/ARC

C - Streamline

https://atcoder.jp/contests/abc117/tasks/abc117_c

方針

座標 X_1, X_2, \dots, X_M を「目的地」と書きます。以下では X はソートされているものとします。

まずコマの数が目的地の数以上のとき ( N \geq M のとき)、初めから全ての目的地にコマを置けばよいので、答えは 0 です。

コマの数より目的地の数のほうが多いときは、コマの移動距離をできるだけ短くしたいので、目的地間の、距離が最も短い区間を移動させることにすればよいです。初手のコマ設置で到達できない目的地は M - N 個ですから、 dX_i = X_{i+1} - X_i として dX を昇順にソートすると、答えは \displaystyle \sum_{i=1}^{M-N} dX_i となります。

ソースコード

X の添え字が問題文や上記の方針とずれています。1 - indexedにするために余分な X_0 を持つのであれば、 X_0 = -\text{inf} で初期化しないと、 X をソートした際に X=0 が紛れ込みます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N, M;  cin >> N >> M;
    vector<int> X(M);
    for(int i=0; i<M; i++)  cin >> X[i];
    sort(X.begin(), X.end());

    // コマの数が目的地の数より多いとき
    if(N>=M){
        cout << 0 << endl;
        return 0;
    }

    vector<int> dX(M-1);
    for(int i=0; i<M-1; i++){
        dX[i] = X[i+1] - X[i];
    }
    sort(dX.begin(), dX.end());

    // dX の小さいものから順に M-N 個の和をとる
    int ans = 0;
    for(int i=0; i<M-N; i++){
        ans += dX[i];
    }
    cout << ans << endl;
}

D - XXOR

https://atcoder.jp/contests/abc117/tasks/abc117_d
コンテスト中は話題の嘘解法(上位ビットから順に貪欲)で通しました。以下は公式の解説を参考にしています。

方針

以下で「i ビット目」と書くとき、0 ビット目から始まるとします。

0 \leq X \leq K という制限を考えない場合、 f(X) を大きくするためには、 X XOR A_k の各ビットに立つ 1 の数を出来るだけ多くすればよいです。よって X の i ビット目を、各 A_k の i ビット目に注目して

  • A_k の i ビット目が 1 である k の数が、 0 である k の数よりも多いとき、 X の i ビット目は 0
  • それ以外のとき、 X の i ビット目は 1

という方針で決めていけば、 f(X) を大きくできます。

0 \leq X \leq K の条件下では、むやみに X のビットを 1 にすると K を越えてしまうため、上の方針は単純には適用できなくなります。そこで、 X < K+1 を満たすように X の上位ビットを決め打ってしまえば、X の残りのビットは上述の方針で決めていけることを利用します (上位ビットで X < K+1 となれば、下位ビットでこの関係が覆ることはないため)。

K \leq 10^{12} < 2^{40} ゆえ、 K+1 は2進数表記で K+1 = (K_{40}K_{39}\dots K_{0}) と表すことができます。同様に X = (X_{40}X_{39} \dots X_{0}) と表せます。 X < K+1 となるための条件は、ある i \geq 0 が存在して、
　　(1)　 X_k = K_k~(k > i)
　　(2)　 X_i < K_i \Leftrightarrow X_i = 0,~ K_i = 1
となることです。 X の上位ビットをこのように決めたとき、残りのビットを当初の方針で決めることで、 f(X) を最大にする X と、そのときの f(X) の値が求まります。各 i について f(X) の最大値を求めれば、それらの中の最大値が所望の値となります。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N;  ll K;
    cin >> N >> K;
    vector<ll> A(N);
    for(int i=0; i<N; i++) cin >> A[i];

    // A の各ビットに 1 がいくつ立っているかを数えておく
    int nBit = 41;
    vector<int> cnt(nBit,0);
    for(int i=0; i<N; i++){
        ll a = A[i];
        int j = 0;
        while(a > 0){
            if(a%2==1) cnt[j]++;
            a/=2;
            j++;
        }
    }

    // K+1 の2進数表記 Kbin を求める
    ll KK = K + 1;
    vector<int> Kbin(nBit,0);
    for(int i=0; i<nBit; i++){
        if(KK%2==1) Kbin[i] = 1;
        KK/=2;
    }

    ll ans = 0;
    for(int i=0; i<nBit; i++){
        // X < K+1 となる条件(2)： Kbin[i] = 1
        if(Kbin[i]==0) continue;

        // Xbin は X の2進数表記
        vector<int> Xbin(nBit,0);
        // 条件(2)： X の i ビット目は 0
        Xbin[i] = 0;
        // 条件(1)： i ビット目より上位では X と K+1 は一致する
        for(int j=i+1; j<nBit; j++){
            Xbin[j] = Kbin[j];
        }
        // i ビットより下位では、
        // 各 A の j ビット目の 1 の数が N の半分以下のとき
        // X の j ビット目も 1 にする。
        for(int j=0; j<i; j++){
            if(cnt[j]<(N+1)/2){
                Xbin[j] = 1;
            }
        }

        // 求めた X の2進数表現から X を求める。
        ll X = 0;
        for(int j=0; j<nBit; j++){
            if(Xbin[j]==1) X += (ll)1 << j;
        }

        // f(X) を計算する
        ll tmp = 0;
        for(int j=0; j<N; j++){
            tmp += X^A[j];
        }
        
        ans = max(ans, tmp);
    }
    cout << ans << endl;
}