Integerのn bit目が簡単に分かる方法(Rubyで競プロ ABC100D)

## はじめに
競技プログラミング自体については解説しません。
n bit目が確認できるメソッドがあることと、
いやそれ確認できるとなんか良いことあるの？
ということを、ABC(AtcoderBeginnerContest)の問題で使ってみたいと思います。

## で、n bit目どうやって確認するの？
Integerにはクラスメソッド[ ]があって、これでnbit目が立ってるのかどうか確認できます
(一番したのbitは0bit目としてカウントします)

```ruby
def check_bits(int)
  print "int: #{int}  "
  (int.bit_length-1).step(0,-1) do |i|
    print int[i]
  end
end
check_bits(100) #=> int: 100  1100100
100.to_s(2)              #=> "1100100"
```

といった感じです。

以下、実際に競プロの問題で[ ] を使ってみるだけの話になります。

## ABC100DをRubyで書いてみる

ABC100DはAtCoder Beginner Contest 100のD問題略です(ACBC100Dじゃん)
https://beta.atcoder.jp/contests/abc100/tasks/abc100_d

解答はこちら
https://img.atcoder.jp/abc100/editorial.pdf

ということで実際にコードにします。
その前にどんな問題でどんな入力でどんな出力をしたいのかをざっくりまとめます。
(Qiitaって数式かけるんですね...)

>**入力**
>
```math
N　M \\
a_0　b_0　c_0　\\
a_1　b_1　c_1　\\
\vdots　\\
a_{N-1}　b_{N-1}　c_{N-1}　\\
```
  

>**出力**
[a,b,c]の配列がNこあり(上でもらったN行のa,b,cのこと)
ここから下記の式(*)が最大となるようにM個配列を取り出したときのその最大の値

>``` math
\begin{vmatrix}
\sum a_i
\end{vmatrix}
+
\begin{vmatrix}
\sum b_i
\end{vmatrix}
+
\begin{vmatrix}
\sum c_i
\end{vmatrix}
```

問題の答えはpdfの解説読めばわかると思うので、ざっくりいいます。

仮に絶対値の条件がなかったら、(*)シンプルにこのようにまとめられますね

``` math
\sum (a_i+b_i+c_i)
```
つまり、N個の配列[a, b, c]をa+b+cが大きい方からM個取って上記を計算すればよいのです。


ここでAだけ絶対値の条件がついたとしましょう。
最大となるのは以下のどちらかです

``` math
\sum -a_i
+
\sum b_i
+
\sum c_i
　or　
\sum (a_i+b_i+c_i)
```

そして前者もシンプルに以下のように書けますね

``` math
\sum (-a_i+b_i+c_i)
```

ということでこの場合の答えは
`配列をa+b+cが大きい順にM個取ってきたときのその和` か
`配列を-a+b+cが大きい順にM個取ってきたときのその和` です。

このようにして考えると、この問題の答え(すべき出力)は以下の8つのどれかです

```math
Nこの配列[a, b, c]を  \left\{
\begin{array}{ll}
　a+b+c \\
-a+b+c \\
　a-b+c \\
-a-b+c \\
　a+b-c \\
-a+b-c \\
　a-b-c \\
-a-b-c \\
\end{array}
\right. が大きい順にM個取ってきたものの和
```
なのでこの8つを計算して、一番大きいやつを探しましょう。
ここでなんで8つかというと,a,b,cがプラスかマイナスかで2^3通り=8つ
答えの候補があるわけです。

a, b, cがプラスかマイナスかって、0から7までの２進数表記を利用したら、
いい感じにかけそうじゃないですか？
0回目のループでは a+b+c ( 0 = 000 )
7回目のループでは-a-b-c ( 7 = 111 )　が対応しそうです。
なので、これを利用していい感じにRubyでこの問題を解いてみましょう。
(ここまで長過ぎて誰もついてきてないかも)

```Main.rb
# 最初に半角スペース区切りの整数を取ってきます。
n, m = gets.chomp.split(' ').map(&:to_i)
# [a, b, c]の配列がいっぱい入ってる配列,設定がケーキなのでcakes
cakes = []; n.times { cakes << gets.chomp.split(' ').map(&:to_i).to_a } 
# ビットの0,1と係数の-1,1を対応付けるメソッドを作っておきます( x = [-1,1] を作って x[i[n]] としても良いと思います。)
def cb(i);	i==1 ? 1 : -1;end
# ケーキの値の和を入れる変数と、最大の和を入れる変数を作っておきます。
sum_cakes, ans = 0, 0
for i in 0..7 do
  # 0..7 の 2進数表記の0/1を利用して、8通りの係数を表せますので、それを利用して各配列の和を計算し
  # その和を降順ソートしてm個目までの和を取ります。 AtCoderのRubyは古いので.sumできません。
  sum_cakes = cakes.map { |cake|  cb(i[0])*cake[0] + cb(i[1])*cake[1] + cb(i[2])*cake[2] }.sort.reverse[0, m].inject(:+)
  # m == 0 の場合、array[0,0].inject(:+)のところでnilが返ります。nilに対して nil > 0　は比較できないので、
  # ぼっち演算子を利用して比較するようにしておきます。
  ans = sum_cakes if sum_cakes &.> ans
end
puts ans
```

コメントが多くてわかりにくいかもしれませんが、 0..7 の2進数表記を利用して、
わざわざ

```ruby
array = [
[1, 1, 1]
...
[-1, -1, -1]
]
```

のような配列を作らなくても良くなってますね。
状態が増えても、for in の値を変えて、mapの中を１要素増やすだけで対応ができるので、
なかなか便利だなと思います。


## 最後に
このときのABC参加して、D問題をC++で書いたのですが、
こういうbitでの組み合わせ列挙を知らなかった(今もC++でどうやるかはわからないのですが)ので、
同じような処理を8回コピペして貼り付けて提出したところ、
係数のつけ間違いがあり、微WAが出て本番で泣いたので、
そういう係数付け間違いとかが起こりうる実装はしたくないですね。
Rubyも競プロも俄なので、これからも頑張っていきたいと思います。

## なぜこんな話を？

実は、Integerに[]のメソッドがあるのを知らなくて、バグが見つからないことがありました。
(予想通りの値が返ってこないところを探そうと思ってたが、
Integerの[]はIntegerを返すので、そこが間違えていると気づくのがかなり後でした)
そのときにめっちゃムカついたので、なんとか無理やり使ってやろうと思ってこの記事を書いたので、
ABC100Dももっとスマートな書き方があるかもしれません。