けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 117 D - XXOR (400 点)

以下の典型思考で解けるけど、苦手意識...^^;

  • XOR な問題は各桁ごとに見る
  •  x の動ける範囲が  K 以下と指示されているときは、 x を上位ビットから見ていったときに、それがどこまで  K と一致するかを考える (桁 DP でおなじみの考え方)

問題へのリンク

問題概要

 N 個の非負整数  A_1, A_2, \dots, A_N および非負整数  K が与えられる。非負整数  X に対して

  •  f(X) = ( X XOR  A_1) + ( X XOR  A_2) +  \dots + ( X XOR  A_N)

で定義される関数  f(X) を考える。 X 0 以上  K 以下を動くときの、この関数値の最大値を求めよ。

制約

  •  1 \le N \le 10^{5}
  •  0 \le K, A_i \le 10^{12}

考えたこと: XOR の扱い

XOR な問題では各桁ごとに考えるのは鉄則ではある。基本的には、 X \le K という条件さえなかったら

  • 各桁ごとに見て、 N 個の  A_1, A_2, \dots, A_N のうち
    • その桁のビットが立っている部分の方が多かったら、その桁はビット反転させない
    • その桁のビットが立っていない部分の方が多かったら、その桁をビット反転する

という風にしたい。ただし、 X \le K という条件があるので、ある上位桁でビット反転してしまったがために、その下位桁でビット反転した方がいいのにビット反転できずに最終結果が悪くなることがありうる。そこで次の考察に移る。

X <= K という条件の扱い方

 X \le K という条件の扱い方としては、


 X \le K であるとは、上位ビットから見たときに  X K のビットが初めて一致しなかった桁が  d であったとしたとき

  •  d より上位の桁については、 X K と一致
  •  d 桁目については  X 0 で、 K 1 である
  •  d より下位の桁については  X はなんでもいい

という風に  d で場合分けして考えるのが手筋ではある。この考え方をもろに使う有名な例として桁 DP がある。

今回もこの考え方で場合分けすれば自然に解くことができる。すなわち上記の  d で場合分けしてあげて、

  •  d より上位の桁については  K と合わせる
  •  d 桁目については、 K 1 でなければダメ、 X 0 とする
  •  d より下位の桁については Greedy に決められる。

あるいは、最初から直接桁 DP で解いてしまっても良い (次節に)。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
        
    long long res = 0;
    for (int d = 60; d >= -1; --d) { // d = -1 は X = K の場合
        if (d != -1 && !(K & (1LL<<d))) continue;
        
        long long tmp = 0;
        for (int e = 60; e >= 0; --e) {
            long long mask = 1LL<<e;
            int num = 0;
            for (int i = 0; i < N; ++i) if (A[i] & mask) ++num;
            
            if (e > d) {
                if (K & mask) tmp += mask * (N - num);
                else tmp += mask * num;
            }
            else if (e == d) {
                tmp += mask * num;
            }
            else {
                tmp += mask * max(num, N - num);
            }
        }
        res = max(res, tmp);
    }
    cout << res << endl;
}

解法 2: 桁 DP

というわけで、この問題が桁 DP で解けるということ自体はとても自然だと思うし、そもそも


K 以下の x についての f(x) の最大値を求めることが要求されている時点で、桁DPがうまくいくことが多い


という風にやった方も多いと思う。慣れていたらゴチャゴチャ考えずに、そうやった方が早いかもしれない。詳しくは

の方に書いてみました。

#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }

long long dp[100][2];

int main() {
    int N;
    long long K;
    cin >> N >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    for (int i = 0; i < 100; ++i) dp[i][0] = dp[i][1] = -1;
    dp[45][0] = 0;
    for (int d = 44; d >= 0; --d) {
        long long mask = 1LL<<d;
        int num = 0;
        for (int i = 0; i < N; ++i) if (A[i] & mask) ++num;
        
        if (dp[d+1][1] >= 0) chmax(dp[d][1], dp[d+1][1] + mask * max(num, N-num));
        if (dp[d+1][0] >= 0) {
            if (K & (1LL<<d)) {
                chmax(dp[d][1], dp[d+1][0] + mask * num);
                chmax(dp[d][0], dp[d+1][0] + mask * (N-num));
            }
            else {
                chmax(dp[d][0], dp[d+1][0] + mask * num);
            }
        }
    }
    cout << max(dp[0][0], dp[0][1]) << endl;
}

解法 3: 半分全列挙

びっくりしたけど、確かにそれでもできるか...!!!

  • 上 6 桁と下 6 桁をそれぞれ全探索しておく
  • 上 6 桁を決めると、下 6 桁がどこまで OK かが決まる

という感じの。