paizaラーニング レベルアップ問題集 巡回セールスマン問題メニュー JavaScript ビットによる集合の表現

ビットによる集合の表現 (paizaランク C 相当)

注意点

k=0の時、２行目が空行になります。
なので、単に

const S = lines[1].split(" ").map(Number);

とすると、空行の時エラーになります。
lines[1]がk=0の時は実行されない工夫がいります。

解答例(C++の場合参考)

ビット論理和|を使います。a|bは、aとbで、どちらかが1の位置で1で返します。

b を b と 2^s_i の論理和で更新します。
bのビット列の1の位置はそのまま１で、
2^s_iが1、かつ、bが0の位置が1になります。
b = b | 2^s_i
2^s_i は、1 を s_i 回左ビットシフトすることで作れる。
すなわち、
2^s_i = 1 << s_i
よって、
b = b | 1 << s_i
書き方を変えると、
b |= 1 << s_i
これはbをbと1<<s_iの論理和で更新するイメージ。

例、s_i=3の時までを表にした。

s_i	3	2	1	0
2^s_i	2^3	2^2	2^1	2^0
整数値	8	4	2	1
左ビットシフト	3回	2回	1回	0回
1 << s_i	1 << 3	1 << 2	1 << 1	1 << 0
ビット表記	1000	100	10	1
ビット表記で1になる位	8の位	4の位	2の位	1の位

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, k] = lines[0].split(" ").map(Number);

let b = 0;
for (let i = 0; i < k; i++) { //k=0の時不実行
  const s = lines[1].split(" ").map(Number)[i];
  b |= 1 << s;
}
console.log(b);

解答例(Python3の場合参考)

b に 2^s_i を足すやり方。
答えはビット列ではなく整数値で出すので、
都市s_iを整数値2^s_iにして、bに加えていく。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, k] = lines[0].split(" ").map(Number);

let b = 0;

if (k !== 0) { //k=0の時不実行
  b = lines[1].split(" ").reduce((sum, s_i) => sum += 2 ** Number(s_i), 0);
}

console.log(b);

ビット列に足すイメージは以下の通り。
都市を表す数値が、他と被らず積み上がる。

入力例1の時。
集合S = 3 5 0 2 1

bit = 0 //ビット列
sum = 0 //整数値
とすると、

3
1 << 3 = 1000(2) = 2^3 = 8
bit += 1 << 3 = 1000(2)
sum += 2^3 = 8

bit = 1000(2)
sum = 8

5
1 << 5 = 100000(2) = 2^5 = 32
bit += 1 << 5 = 100000(2)
sum += 2^5 = 32

bit = 101000(2)
sum = 40

0
1 << 0 = 1(2) = 2^0 = 1
bit += 1 << 0 = 1(2)
sum +== 2^0 = 1

bit = 101001(2)
sum = 41

2
1 << 2 = 100(2) = 2^2 = 4
bit += 1 << 2
sum += 2^2 = 4

bit = 101101(2)
sum = 45

1
1 << 1 = 10(2) = 2^1 = 2
bit += 1 << 1
sum += 2^1 = 2

bit = 101111(2)
sum = 47

となる。