【ABC384】C問題の復習 - bit演算【Golang】

問題リンク：https://atcoder.jp/contests/abc384/tasks/abc384_c
解法：bit演算

# C - Perfect Standings の復習
考え方としては、31人の人間がそれぞれ回答する問題を選んであげて、それに応じた得点をつけてあげる。
全員分の回答する問題及び得点をつけてあげたら、条件に沿ってソート処理して標準出力する。
回答する問題の選び方として、A,B,C,D,Eそれぞれの問題を「取る/取らない」をbit演算をもとに決めてあげることがポイントとなる。

## Golangでの回答コード
```go:ABC-C.go

package main

import (
	"fmt"
	"sort"
)

func main() {
    // 各問題の得点を入力してもらう
	points := make([]int, 5)
	for i := 0; i < 5; i++ {
		fmt.Scan(&points[i])
	}

    // 問題はA〜E
	names := []string{"A", "B", "C", "D", "E"}

	// その人が回答する問題と得点を格納する構造体
	type participant struct {
		name  string
		score int
	}

    // participant型のスライス（31人分の回答する問題と得点を格納していく）
	participants := []participant{}

	// i番目の人はどの問題を選ぶかをjで決める
	for i := 1; i < (1 << 5); i++ { // 1~31人のそれぞれについて処理
		name := ""
		score := 0
		for j := 0; j < 5; j++ {
			if i&(1<<j) > 0 { // i番目の人が選ぶべき問題をjをもとに決めてあげる
				name += names[j]
				score += points[j]
			}
		}
		participants = append(participants, participant{name, score})
	}

	// スコアの降順、スコアが同じ場合は辞書順でソート
	sort.Slice(participants, func(i, j int) bool {
		if participants[i].score == participants[j].score {
			return participants[i].name < participants[j].name
		}
		return participants[i].score > participants[j].score
	})

    // 出力
	for _, p := range participants {
		fmt.Println(p.name)
	}

}

```

## 「if i&(1\<< j) > 0」について：

### **式の意味**

1. **`1<<j` (ビットシフト)**
    - 数字 `1` を左に `j` ビットだけシフトします。
    - 結果として、2進数で「1」が `j` 桁目に移動したビット列が得られます。
    - 例えば:
        - `j = 0` の場合: `1<<0` → `00001` (2進数)
        - `j = 1` の場合: `1<<1` → `00010` (2進数)
        - `j = 2` の場合: `1<<2` → `00100` (2進数)
2. **`i & (1<<j)` (ビットAND)**
    - 変数 `i` の `j` 桁目が1かどうかを確認する処理です。
    - ビットAND演算 (`&`) は、対応するビットが両方とも1の場合にのみ1を返します。
    - 例えば:
        - `i = 10110`（2進数）で、`j = 2` の場合:
            - `1<<2` → `00100`
            - `i & (1<<2)` → `10110 & 00100` → `00100` → 真 (2進数で0以外)
3. **`> 0` (条件判定)**
    - AND演算の結果が0より大きい場合、そのビットが「1」であることを意味します。
    - 条件が真の場合、そのビット位置に対応する問題を選択します。

---

### **例を使った可視化**

### **前提**

`i = 13`（2進数で `01101`）として、各ビットに対して処理を確認します。

| ビット位置 (`j`) | `1<<j` (シフト後のビット列) | `i & (1<<j)` | 結果 (`> 0`) |
| --- | --- | --- | --- |
| `j = 0` | `00001` | `01101 & 00001 = 00001` | 真 (ビット位置0が1) |
| `j = 1` | `00010` | `01101 & 00010 = 00000` | 偽 (ビット位置1が0) |
| `j = 2` | `00100` | `01101 & 00100 = 00100` | 真 (ビット位置2が1) |
| `j = 3` | `01000` | `01101 & 01000 = 01000` | 真 (ビット位置3が1) |
| `j = 4` | `10000` | `01101 & 10000 = 00000` | 偽 (ビット位置4が0) |

---

### **処理の流れ**

1. `i = 13` の場合、2進数で `01101`。
2. `j = 0～4` の各ビットについて処理を行う:
    - `j = 0`: ビット0が1なので、「問題A」を選択。
    - `j = 1`: ビット1が0なので、何もしない。
    - `j = 2`: ビット2が1なので、「問題C」を選択。
    - `j = 3`: ビット3が1なので、「問題D」を選択。
    - `j = 4`: ビット4が0なので、何もしない。

### **結果**

`i = 13` の場合、選択された問題は **A, C, D** になります。

お絵描き：
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3771904/b13cb76f-8acd-a319-04c0-f39586327b2b.png)

---

### **全体の動きのイメージ**

- `i` を 1 から 2^5−1（= 31）まで順に変化させることで、全ての部分集合を列挙します。
    
- 各 `i` は「どの問題を解くか」をビットで表現しており、ビット位置が1の箇所に対応する問題が選択されます。

例えば：

- `i = 3` → `00011` → 問題 A, B
- `i = 19` → `10011` → 問題 A, B, E

## 最後に
自分の復習用に書いてみました。
再帰でもできるみたいですが、今の自分には難易度が高いかもと思ったので、今回はbit演算で復習してみました。
アルゴリズムの勉強めっちゃ楽しいので、どんどん精進して参ります！