研究室の秘書さんがバレンタインチョコをくれたので今年は勝ち組になれました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc117)にて開催されました、AtCoder Beginner Contest 117の第四回目です。

今回は、第四問「D - XXOR」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

N 個の非負整数 A 1 , A 2 , . . . , A N および非負整数 K が与えられます。

0 以上 K 以下の整数 X に対して、f(X)=(X XOR A1) + (X XOR A2) + ... + (X XOR AN) とします。

ここで、非負整数 a , b に対して a XOR b は a と b のビットごとの排他的論理和を表します。

f の最大値を求めてください。

XOR とは整数 A , B のビットごとの排他的論理和 X は、以下のように定義されます。

X を二進表記した際の 2 k ( k ≥ 0 ) の位の数は、 A , B を二進表記した際の 2 k の位の数のうち一方のみが 1 であれば 1 、そうでなければ 0 である。例えば、 3 XOR 5= 6 となります (二進数表記すると: 011 XOR 101= 110 )。

2.入力例

入力入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 … A_N

出力 f の最大値を出力せよ。

3.初見の感想

当日は時間が無くて解けない問題でした
論理演算やシフト演算、最近やってなさ過ぎてリファレンス見返すレベルでした

4.学びポイント

まずは例を使って考えてみる

入力例が以下の場合で考えます

3 7
1 6 3

まずは入力された数値(今回だと1,6,3)を2進数表記に変換します

001
110
011

これらの数字全てとXORを取った時の和の値が最大となればよいのです

どういう数字とXORをとれば数字が大きくなるでしょう？

答えは単純です。

入力の数値をビット反転させた値をいれてあげれば値が大きくなるのです。

例えば入力の値が3(011)ならば、4(100)とXORをとると、全ての桁が1となり7(111)という大きな数値が出力されます。

つまり我々は入力の値群から桁ごとに0と1、どちらが頻度が高いのかを分析すればよいのです。

例えば下の入力の場合なら、

001
110
011

３つの２進数の中で、一番左の桁は0が多い、真ん中は1、右の桁は1が多い…となりますね。

この頻度の高い011を反転させた100こそがXORの相手にすべき数値なのです！

ここまでわかると、あとはXORをとった値の和をとるだけですね！

論理演算、シフト演算のやり方(コメントで具体例も示しています)

AND演算

ANS=X&Y;
// 1(001)=5(101)&1(001)

OR演算

ANS=X|Y;
// 5(101)=4(100)|1(001)

シフト演算

long bit = 1L;

bit <<= 1;
// bit=10;(2進数表記)

bit >>= 1;
// bit=1;(2進数表記)

5.コードの簡単な解説

まず、入力の値のパースを行う

 string[] line = System.Console.ReadLine().Split(' ');
            int N = int.Parse(line[0]);
            int K = int.Parse(line[1]);
            string[] line2 = System.Console.ReadLine().Split(' ');
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(line2[i]);
            }

２進数の桁数をlogで取得し、桁ごとに1の出現頻度が過半数かを配列に保存

long length = (long)Math.Log(K, 2);
            int[] count = new int[length + 1];
            long bit = 1L;
            for (int i = 0; i <= length; ++i)
            {
                for (long j = 0; j < N; ++j) if ((bit & A[j]) != 0) count[i]++;
                bit <<= 1;
            }

出現頻度配列をもとに反転を行い、結果を出力

bit = 1L;
            bit <<= (int)length;
            var num = 0L;
            var temp = 0L;
            for (long i = length; 0 <= i; --i)
            {
                if (count[i] < ((N + 1) / 2)) temp |= bit;
                if (temp <= K) num = temp;
                else temp = num;
                bit >>= 1;
            }
            var ans = 0L;
            for (int i = 0; i < N; ++i) ans += (num ^ A[i]);
            Console.WriteLine(ans);

6.全コード

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] line = System.Console.ReadLine().Split(' ');
            int N = int.Parse(line[0]);
            int K = int.Parse(line[1]);
            string[] line2 = System.Console.ReadLine().Split(' ');
            int[] A = new int[N];
            for (int i = 0; i < N; i++)
            {
                A[i] = int.Parse(line2[i]);
            }
            long length = (long)Math.Log(K, 2);
            int[] count = new int[length + 1];
            long bit = 1L;
            for (int i = 0; i <= length; ++i)
            {
                for (long j = 0; j < N; ++j) if ((bit & A[j]) != 0) count[i]++;
                bit <<= 1;
            }
            bit = 1L;
            bit <<= (int)length;
            var num = 0L;
            var temp = 0L;
            for (long i = length; 0 <= i; --i)
            {
                if (count[i] < ((N + 1) / 2)) temp |= bit;
                if (temp <= K) num = temp;
                else temp = num;
                bit >>= 1;
            }
            var ans = 0L;
            for (int i = 0; i < N; ++i) ans += (num ^ A[i]);
            Console.WriteLine(ans);
        }
    }
}

7.最後に

具体例で考えることの重要性…ですね！

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

【プログラミングコンテスト】AtCoder Beginner Contest 117④