XXOR

- [XXOR](https://atcoder.jp/contests/abc117/tasks/abc117_d)

## コンテスト中の考察（嘘解法だけど）

- 考察。以下の文章は日本語が崩壊してます。
- 問題文読んでも特に何も思い浮かばないのでサンプルで実験してみる
- サンプル1は以下の通り

```sh
# 入力
3 7
1 6 3

# 出力
14
```

- 1, 6, 4を桁毎にみてマスクKを通した結果、各桁の1の個数が多い方が嬉しい。なので、各桁毎の1の個数を数えてみる。ある桁に注目する。そのとき1の個数より0の個数の方が多いなら、その桁のビットは1にする方が良い。そうした方が、最終的にその桁の1の個数が増えるから嬉しい（日本語壊れた）

<img width="268" alt="xxor_1.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/67bca68e-0299-de24-e58c-e729beec2a04.png">


- 上位の桁の方が数が大きいので、上位のマスク値からビットを立てるかどうかを決定すると良さそう（間違ってるんですがね）。[Sum AND Subarrays](https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b)になんとなく似てるなーと思った。
- その方針でコードを出す。[これとか](https://atcoder.jp/contests/abc117/submissions/4164215)。でもWAが出てしまう。
- ここで、マスク値がKを超える場合を考慮していないことに気がつく。なので、「上位ビットから見ていってマスク値を決めていき、マスク値がKを超えるならそこで終了」という方針に切り替える。[その方針のコード](https://atcoder.jp/contests/abc117/submissions/4164998)を提出するもWAを食らう。
- ここで、「上位ビットから取るのが最善ではないのでは？？？」ということに気がつく。マスク値を決定し、$2^1$が2つと、$2^2$が1つのどちらを取るかを考えたとき、$2^1$が2つの方をとった方がいい。なぜなら、最終的なスコアは両者ともに同じだが、マスク値は$2^1$を立てる方が小さくて済むから（また日本語が壊れた）
- ということで、マスクのある桁を立てた時の値が大きい順に取っていく方針に変えた。`{ある桁を立てた時にプラスされるスコア, 立てる桁}`っていう配列を降順にソートした。そうすれば、いい感じになる（桁の小さい方から取るやつやりたかったけど方法がわからなかった）。そのコードが[これ](https://atcoder.jp/contests/abc117/submissions/4165581)。このコードもWA。原因はマスク値がKを超える場合を考慮してないことだったので、それを考慮するコードに変更。そしてAC。そのコードが[これ](https://atcoder.jp/contests/abc117/submissions/4165875)。
- という感じなんですが、これは嘘解法です



## 嘘解法で落ちるケース

<blockquote class="twitter-tweet" data-lang="ja"><p lang="ja" dir="ltr">D問題<br><br>5 2<br>0 0 0 2 2<br><br>何が出力されますか？</p>&mdash; Mister (@mistter_gp) <a href="https://twitter.com/mistter_gp/status/1092055240289837056?ref_src=twsrc%5Etfw">2019年2月3日</a></blockquote>

- 「以下のケースで何が出力されますか？」という問いに対し、6と9の割合がだいたい半分づつとなった。ちなみに答えは「9」になるのが正しい。マスク値は0, 1, 2の3通りある。マスク値が0のとき答えは4、マスク値が1のとき答えは9、マスク値が2のとき答えは6となる。よって、値が最大になるのはマスク値が1のときの「9」となる。

```
5 2
0 0 0 2 2
```

- この投票の信憑性とかはともかく、僕の解法は嘘解法ということになる（えーん）



## 理想の考察

- いつもは理想の考察を書くんだが、どうやって思いつくかがよくわからない...



## 解法

<img width="434" alt="xxor_2.png" src="https://qiita-image-store.s3.amazonaws.com/0/218584/8a87c177-47be-9f19-33b2-6f117693b2a8.png">


- 上記の図のような状況を考える。この状態から次にする操作は、青で丸した部分のマスクビットを決めることである
- このときにする操作は2つある。1つ目は青丸ビットを1にすること。2つ目はこの青丸ビットを0にすることである。
- 青丸ビットを0にするという操作は、もともと1だったビットを0にするという操作になる。つまり、この時点でマスク値は確実にKより小さくなる。そのため、「10010????」というマスク値の「?」の部分は何を入れてもよくなる。なので、以下のビットはマスク値の上限を気にせずスコアが大きくなるようにマスク値を決めることにのみに集中すれば良い。
- 青丸ビットを1にするという操作は、Kの青丸ビットに操作を加えないということである。つまり、この時点でマスク値はK以下になるかは決まっていない。よって、「10011????」というマスク値の「?」はまだ確定できない
- こんな感じのことを全ビットに対して行う
- あとはコード見た方が早そう
- DPは`dp[i][j]: 上からiビット目まで決めたとき。jはマスク値がK未満かどうか`みたいな感じ。DPテーブルを−1で初期化するのは、その値を更新したかを判定するため



## 桁DP

- `dp[i桁見る][未満フラグ] = 総数`みたいに計算するDPらしい。





## [コード](https://atcoder.jp/contests/abc117/submissions/4175947)

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_DIGIT = 50; // 多めにとってある
int dp[100][2]; // dp[i][j]: 上からi桁目までみたとき、jはi桁目までK以下かで確定してるかどうか

signed main() {
  int N, K;
  cin >> N >> K;

  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  fill(dp[0], dp[100], -1);
  dp[MAX_DIGIT][0] = 0; // 初期状態。上位桁から決めていき、最初はマスク値がK以下か確定していない状態

  for (int digit = MAX_DIGIT-1; digit >= 0; digit--) {
    int mask = 1LL << digit; // 上からdigit桁目を立てたマスク

    // Aでもともと上からdigit桁目にビットが立っているものの個数
    int num = 0;
    for (int i = 0; i < N; i++) {
      if (A[i] & mask) {
        num++;
      }
    }

    // マスク値の上からdigit桁目を0, 1にしたときのスコア
    int score0 = mask * num; // 上からdigit桁目のマスクビットを立てない時のスコア
    int score1 = mask * (N - num); // 上からdigit桁目のマスクビットを立てる時のスコア

    // 1 -> 1(マスク値がK以下に確定した状態 -> マスク値がK以下に確定した状態）
    // マスク値がK以下であることは確定しているので、上からdigit桁以降のビットは立てても立てなくても良い
    // なので、ビットを立てたときと立ててないときのスコアの大きい方を採用する
    if (dp[digit+1][1] != -1) {
      dp[digit][1] = max(dp[digit][1], max(dp[digit+1][1] + score0, dp[digit+1][1] + score1));
    }

    // 0 -> 1(マスク値がK以下に確定していない状態 -> マスク値がK以下に確定した状態)
    // Kの立っている上からdigit桁目を引っ込めることでマスク値がK以下に確定する。なのでscore0を採用する
    if (dp[digit+1][0] != 1) {
      if (K & mask) { // Kの上からdigit桁目が立っていたら引っ込める
        dp[digit][1] = max(dp[digit][1], dp[digit+1][0] + score0);
      }
    }

    // 0 -> 0(マスク値がK以下に確定していない状態 -> マスク値がK以下に確定していない状態)
    // Kの上からdigit桁目をそのままにするということ
    // なので、Kの上からdigit桁目が0ならscore0を採用し、 Kの上からdigit桁目が1ならscore1を採用する
    if (dp[digit+1][0] != -1) {
      if (K & mask) { // Kの上からdigit桁目が立ってる
        dp[digit][0] = max(dp[digit][0], dp[digit+1][0] + score1);
      } else { // Kの上からdigit桁目が立ってない
        dp[digit][0] = max(dp[digit][0], dp[digit+1][0] + score0);
      }
    }
  }

  // dp[0][1]: K以下のマスク値を使った時の最大値
  // dp[0][0]: マスク値Kを使った時の最大値
  cout << max(dp[0][1], dp[0][0]) << endl;

  return 0;
}
```



## 要点

- ビット使う問題は、桁ごとに考えると嬉しくなることが多い
- 桁毎に考える問題では桁DPが使える？（要出典）
  - 桁DPこれが初めてだから使いどころをよくわかってない





## メモ

- [Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s)。EDPCで出てた桁DP問題
- [けんちょんさんのD問題解法ブログ](http://drken1215.hatenablog.com/entry/2019/02/03/224200)。ちょっと難しい
- [けんちょんさんのD問題詳細ブログ](http://drken1215.hatenablog.com/entry/2019/02/04/013700)。こっちの方がわかりやすい。これをメインに理解していった。
- [とーらすさんの桁DP解説記事](http://torus711.hatenablog.com/entry/20150423/1429794075)。けんちょんさんがオススメしてた。
- [ペケンペイさん(?)の桁DP解説記事](https://pekempey.hatenablog.com/entry/2015/12/09/000603)。けんちょんさんがオススメしてた。ありえんくらいわかりやすいけど、初見で見るとちょいむずいかも
- [アルメリアさんの本コンテスト解説記事](https://betrue12.hateblo.jp/entry/2019/02/03/234159)。桁DPの概要知ってから読むとわかりやすい。
- 半分全列挙でもとけるらしい