B - Sum AND Subarrays

はじめに

競技プログラミングDwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選
B - Sum AND Subarrays
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

ある日、ドワンゴ社員のニワンゴくんは、長さ N の整数列 (a1,…,aN) を見つけました。
ニワンゴくんは、数列 a の性質に興味を持っています。

数列 a の空でない連続する部分列 al,…,ar (1≤l≤r≤N) の 美しさ は、 al+…+ar と定義されます。
ニワンゴくんは、ありうる N(N+1)/2 個の空でない連続する部分列のうち、 K 個を選んで取ってきて、
それらの美しさのビット毎の論理積 (AND) を計算したとき、
その最大値がどうなるかを知りたがっています (取ってくる部分列の間で重複する要素があっても構いません)。

彼の代わりに最大値を求めてください。

制約

・2≤N≤1000
・1≤ai≤109
・1≤K≤N(N+1)/2
入力として与えられる数値はすべて整数である

入力

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

N K
a1 a2 … aN

出力

答えを出力せよ。

解き方

1.問題文について

この問題で出力するものは、問題文の以下の部分に書かれています。

ありうる N(N+1)/2 個の空でない連続する部分列のうち、 K 個を選んで取ってきて、
それらの美しさのビット毎の論理積 (AND) を計算したときの最大値

これを言い換えると以下のようになります。

a1 a2 … aNの空ではない連続する部分文字列のうち、
任意のK個の論理積を計算したときの最大値

・a1 a2 … aNの空ではない連続する部分文字列
→入力されるa1 a2 … aNから作ることのできる、
空ではない(空集合は不可)連続する(入力された順番で繋がる)部分文字列
・任意のK個の論理積を計算したときの最大値
この部分は入力1を見ると分かり易いです。

*入力例1

4 2
2 5 2 5
*入力例1の解説

異なる空でない連続する部分列は 10 個存在します。全列挙すると、

・1 番目から始まるもの: {2},{2,5},{2,5,2},{2,5,2,5}
・2 番目から始まるもの: {5},{5,2},{5,2,5}
・3 番目から始まるもの: {2},{2,5}
・4 番目から始まるもの: {5}
です (数列の要素が同じでも、異なる添字から始まる列は異なるものとみなすことに注意してください)。

このうち異なる 2 個の部分列の美しさのビット毎の論理積 (AND) として得られる値の最大値は 12 です。 これは {5,2,5} (美しさ 12) と {2,5,2,5} (美しさ 14) を選んだ時に達成できます。

最後の2行に注目します。

このうち異なる 2 個の部分列の美しさのビット毎の論理積 (AND) として得られる値の最大値は 12 です。 これは {5,2,5} (美しさ 12) と {2,5,2,5} (美しさ 14) を選んだ時に達成できます。

この二行から、
部分文字列の数字の和を求めて
その和をK個選んで
ビット毎の論理積を求めたときの最大値を
出せばいいということが分かります。

ビット毎の論理積は、
数字を二進数に変換して
それぞれの桁を見比べて
どちらも1であれば1、それ以外は0とするようなものです。
入力例1の12と14を例にすると以下のように計算できます。

10進数→2進数
12→1100
14→1110
論理積は
  1100
+ 1110
---------
  1100

以下のページに、表と図があって分かり易いです。
シスアド講座  論理演算

つまり、
この問題分をまとめると以下のようになります。

入力されるa1 a2 … aNの異なる空でない連続する部分列の和から
任意のK個を取り出すときに、取り出したK個のビット毎の論理積の最大値を求める。

2.問題を解く

この問題は以下の二段階で解きます。
①入力で与えられたa1 a2 … aNの異なる空でない連続する部分列の和を全列挙する。
②全列挙した部分列から、
K個取り出したときの美しさのビット毎の論理積 (AND) の最大値を求める。

①入力で与えられたa1 a2 … aNの異なる空でない連続する部分列の和を全列挙する。

以下のように二重ループを回しました。

        var n = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var N = n[0];
        var K = n[1];
        //a1 a2 … aN
        var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        //空ではない部分文字列の和を保存するためのリスト
        var list = new List<long>();
        //N回まわす
        for (long i = 0; i < N; ++i)
        {
            //空ではない部分文字列の和
            var sum = 0L;
            //N-i回まわす
            //このループの中で和を求める
            for (long j = i; j < N; ++j)
            {
                sum += line[j];
                if (sum != 0L) list.Add(sum);
            }
        }

これを動かすとlistの中に、
空ではない部分文字列の和が全列挙されます。

②全列挙した部分列から、K個取り出したときの美しさのビット毎の論理積 (AND) の最大値を求める。

以下の解き方を参考にしています。

dwacon5th-prelims.contest.atcoder.jp

ここから全列挙した和からK個取り出したときの最大値を求めていきます。
以下のような場合が考えられるので
10進数で数が大きいもの順に並べて
上からK個の論理積を出す方法では求められません。

K=2
和のリスト={5,6,9}

この例で大きいもの順に上から二つとると「0」になりますが、
5と6をとると「100」になるので、こちらが最大値です。

そのため、
なるべく左の桁に1が立ち、
かつ、その後も1が続くような組み合わせ
を考えます。

コードを見ながら解説していきます。

 //和の中の最大値
var max = (int)(Math.Log(list.Max(), 2));
//答えを格納する変数
var ans = 0L;
//最大値から0までループを回す
 for (var i = max; i > -1; --i)
{
      //2のi乗
      var bit = (long)Math.Pow(2, i);
      //2のi乗との論理積
      //結果が1以上になったもの(結果で1が立っている)ものだけをリストに保存
      var ansList = list.Where(x => (x & bit) != 0).ToList();
      //Kよりもリスト内の数が大きければ
      if (K <= ansList.Count())
      {
          //次の処理にリストをコピーする
          list = ansList;
          //これまでの答えとの論理和
          ans |= bit;
      }

まず、
部分集合の和の中の最大値を
ループの起点にしている理由は
リストの中で一番数が大きい(二進数ではより左に1が立っている)からです。
最大値以上に
部分集合からK個取り出した論理積が大きくなることはないので
最大値を起点にしています。

次に2のi乗は、
二進数において1の立つ桁になります。

10進数→2進数
2^0→1
2^1→10
2^2→100
2^3→1000
…

つまり、
2のi乗との論理積を出して0以外の数になるということは
その桁に1が立っていることを表します。
そして、
その桁に1が立っている和の数がK個以上あれば
次のループ処理のためにリストをコピーし
(次のループではこの中から2i-1の桁で1が立っているものがK個以上あるか調べる)
答えに論理和で加えます。
論理和論理積とは違い、
1と1以外に、0と1でも1が立ちます。
そのため、
前のループで答えに足していた数に
そのまま数を加えることができます。

論理演算子について、以下のページに一覧があります。
具体例もあるので、分かり易いです。

ufcpp.net

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Bmondai
{
    static void Main()
    {
        var n = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        var N = n[0];
        var K = n[1];
        //a1 a2 … aN
        var line = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
        //空ではない部分文字列の和を保存するためのリスト
        var list = new List<long>();
        //N回まわす
        for (long i = 0; i < N; ++i)
        {
            //空ではない部分文字列の和
            var sum = 0L;
            //N-i回まわす
            //このループの中で和を求める
            for (long j = i; j < N; ++j)
            {
                sum += line[j];
                if (sum != 0L) list.Add(sum);
            }
        }

        //和の中の最大値
        var max = (int)(Math.Log(list.Max(), 2));
        //答えを格納する変数
        var ans = 0L;
        //最大値から0までループを回す
        for (var i = max; i > -1; --i)
        {
            //2のi乗
            var bit = (long)Math.Pow(2, i);
            //2のi乗との論理積
            //結果が1以上になったもの(結果で1が立っている)ものだけをリストに保存
            var ansList = list.Where(x => (x & bit) != 0).ToList();
            //Kよりもリスト内の数が大きければ
            if (K <= ansList.Count())
            {
                //次の処理にリストをコピーする
                list = ansList;
                //これまでの答えとの論理和
                ans |= bit;
            }
        }
        Console.WriteLine(ans);
    }
}