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

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

C - Perfect Standings の復習

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

Golangでの回答コード

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 になります。

お絵描き：

---

全体の動きのイメージ

• i を 1 から 2^5−1（= 31）まで順に変化させることで、全ての部分集合を列挙します。

• 各 i は「どの問題を解くか」をビットで表現しており、ビット位置が1の箇所に対応する問題が選択されます。

例えば：

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

最後に

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