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

ビットによる集合の表現 (paizaランク C 相当) 注意点 k=0の時、２行目が空行になります。 なので、単に とすると、空行の時エラーになります。 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