AtCoder Beginner Contest 121の解説

A問題 - White Cells

小学校の時の算数の問題の「花壇に道を作ります。その時の花壇の面積はなんですか。」っていうのと似ている。

まず全てのマス目の数はH×W。そこから縦のぶんと横のぶんを引きます。
あとは2回引いてしまった（重なった部分）があるので、そこの部分を1回分補充してあげればOK。

B問題 - Can you solve this?

なんか難しそうだけど、実装するだけな問題。
BとA1, BとA2, BとA3, .....のようにそれぞれで計算していく。適当な変数(例えばres)を0で初期化しておいて、Bのi番目とAnのi番目をかけ合わせたものをresに加えていって、最後にcを加えてそれが0より大きかったらans++するみたいな感じでできます。配列の扱いに注意。

C問題 - Energy Drink Collector

自分の場合、１回目は何も考えずに「全ての飲み物をvectorに追加してsortして小さい順に取っていけばいいやん！」と考えてTLEしました。補導されそうですね。まあ確かに10^5個の店に最大で10^5本売ってたら最大で10^10本になるし。

売店を安く売っている順にソートして、端からどんどん買っていけばいいです。売り切れたら次の店に行けばいいです。
vector > のようにすると、ソートした時に左側、つまり値段でソートされるので楽です。

D問題 - XOR World

排他的論理和がわからない人もそうじゃない人も、一旦「▶ 排他的論理和とは」を見ましょう。
"1の数が奇数個ならば1、偶数個ならば0"というヒントが書いてあります！

つまりこの問題は、A~Bまでの数を2進法表記した時の1の登場回数を求めたらよさそうです。入力例1なら2~4までなので

2. 010
3. 011
4. 100

{1,2,1} <- それぞれの桁での1の登場回数

みたいなのが作れたらACできそう。でも直接2~4を求めるのは難しそうなので、0からBまでの数 - 0からA-1までの数 みたいな感じで求めることにします。

0からBまでの数を書いていったときのそれぞれの桁での1の登場回数は

4なら{2,2,1}(下から数えてます)、
13なら{7,6,6,6}になるはずです。どう計算するんやと。

13で考える

上に描いた図の右から3段目に注目して上から読むと、00001111000011となっています。0から始まっているので13+1 = 14番目です。
00001111を一つのかたまりとして見ると、14番目まではかたまりが1つと000011なので3桁目の合計は6、という風に計算ができます。つまり

ll res = 0;
    res += (b + 1) / i * (i / 2);
    if (i / 2 < (b + 1) % i) {
      res += (b + 1) % i - i / 2;
    }

• i は かたまりの幅（00001111なら8になる）、
• i/2は一つのかたまりに含まれている1の数(00001111なら4になる)
• もしもかたまりで割った余りが000011のように後半部分と重なっていたら、重なってるぶんだけ足す(000011なら2を足す)

みたいな感じです。これをi = 1から順番にi *= 2しつつ下の桁から求めていきました。

自分のコード

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

int main() {
  ll a, b;
  cin >> a >> b;
  vector<ll> va;
  vector<ll> vb;

  // Bについて
  bool con = true;
  for (ll i = 2; con; i *= 2) {
    if (b < i) con = false;  // 最後の桁っぽかったら
    ll res = 0;
    res += (b + 1) / i * (i / 2);  // 0からなので、BはB+1番目になる
    if (i / 2 < (b + 1) % i) {
      res += (b + 1) % i - i / 2;
    }
    vb.push_back(res);
  }

  // Aについて
  con = true;
  for (ll i = 2; con; i *= 2) {  // bと同じ回数繰り返したいので
    if (b < i) con = false;
    ll res = 0;
    res += a / i * (i / 2);  // A-1番目なので
    if (i / 2 < a % i) {
      res += a % i - i / 2;
    }
    va.push_back(res);
  }

  // 0~B - 0~A をしたやつを作る
  vector<ll> vc(vb.size());
  for (ll i = 0; i < vc.size(); i++) {
    vc[i] = vb[i] - va[i];
  }

  ll ans = 0;
  ll step = 1;
  for (ll i = 0; i < vc.size(); i++) {
    // もしその桁が奇数(つまり1)だったら答えに足す
    if (vc[i] % 2) ans += step;
    step *= 2;
  }

  cout << ans << endl;
}