AtCoder Beginner Contest 121 - 競プロやります。

C - Energy Drink Collector
- 方針
- ソースコード
D - XOR World
- 方針
- ソースコード

C - Energy Drink Collector

https://atcoder.jp/contests/abc121/tasks/abc121_c

方針

安い栄養ドリンクから順番に、

B 本すべて買っても計 M 本に達しない場合は全部買う
一部買えば計 M 本に達するときは、必要なだけ買う

というのを繰り返せば答えが得られます。

ソースコード

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

int main(){
    int N, M;  cin >> N >> M;
    vector<pair<ll,ll>> P(N);
    for(int i=0; i<N; i++){
        cin >> P[i].first >> P[i].second;
    }

    // 値段の昇順に並び替える。
    sort(P.begin(), P.end());
    ll ans = 0;
    for(int i=0; i<N; i++){
        ll A = P[i].first;
        ll B = P[i].second;
        if(M>B){
            // 全て買っても M 本に満たない場合は全部買う
            M-=B;
            ans += A*B;
        }else{
            // 一部だけ買えば計 M 本となる場合
            ans += A*M;
            cout << ans << endl;
            return 0;
        }
    }
}

D - XOR World

https://atcoder.jp/contests/abc121/tasks/abc121_d
コンテスト中には解けませんでした。反省ですね。

方針

問題文にある通り、 A, A+1, ……, B を2進数で表したとき、k ビット目の 1 が奇数個である場合は $f(A,B)$ の k ビット目は 1 になり、偶数個の場合は 0 になります。そこで A から B の k ビット目の 1 の個数を、各 k について真面目に求めていく方針をとります。 k の範囲ですが、 $B \leq 10^{12} < 2^{50}$ ですから、 $0 \leq k \leq 50$ としておけば十分です。

$g(N, k) =$ 0 以上 $N$ 以下の中での k ビット目の 1 の個数、とすると $g(B, k) - g(A-1, k) =$ A から B の k ビット目の 1 の個数、となります。よって $g(N,k)$ が求められればこの問題を解くことが出来ます。

まずは 0 から適当な値まで 2 進数で書き出してみます：

すると、

$2^0$ の位：0, 1, 0, 1, 0, 1 ……
$2^1$ の位：0, 0, 1, 1, 0, 0, 1, 1, ……
$2^2$ の位：0, 0, 0, 0, 1, 1, 1, 1, ……

と言った具合に、 $2^k$ の位は「0 が $2^k$ 個続いた後に 1 が $2^k$ 個続く」(※) というパターンの繰り返しであることが分かります。

0 から N までの数の k ビット目で、(※) のパターンは $\mathrm{floor}((N+1)/2^{k+1})$ 個入っており、このなかに 1 は $\mathrm{floor}((N+1)/2^{k+1})\times 2^k$ 個入っています (0 から数えると N は N+1 番目の数であることに注意します)。
また (※) のパターンが丸々入るのが続いた後に、(※)の最初の $(N+1)\% 2^{k+1}$ 文字だけが後ろに続きます。この中に 1 は $\max(0, (N+1)\% 2^{k+1} - 2^k)$ 個入ります。

以上をまとめて
　　 $g(N, k) = \mathrm{floor}((N+1)/2^{k+1})\times 2^k + \max(0, (N+1)\% 2^{k+1} - 2^k)$
と求まりました。

例えば、下から 3 ビット目(k=2) の 0 , 1の並びを 0 から N = 22 について書き出してみると、
0, 0, 0, 0,　1, 1, 1, 1,　0, 0, 0, 0,　1, 1, 1, 1,　0, 0, 0, 0,　1, 1, 1
となっています (0 から 22 までについて並べているので、23個の数字が並びます)。この中に "00001111" というパターンはちょうど $\mathrm{floor}(23/8) = 2$ 個入っており、その後ろにパターンの最初の $23\%8 = 7$ 文字である "0000111" が付け加わっています。よって 0 から 22 のなかに、３ビット目が 1 であるようなものの個数は 2*4+3=11 個です。

ソースコード

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

ll g(ll N, ll k){
    ll p = (ll)1 << k;
    return (N+1)/(2*p)*p + max((ll)0, (N+1)%(2*p) - p);
}

int main(){
    ll A, B;
    cin >> A >> B;
    
    ll ans = 0;
    ll p = 1;
    for(ll k=0; k<=50; k++){
        // A から B の中の k ビット目の 1 の数
        ll cnt = g(B,k) - g(A-1,k);

        // cnt が奇数のとき
        // f(A,B) の k ビット目が 1 になる。
        if(cnt%2==1) ans+=p;
        p*=2;
    }
    cout << ans << endl;
}