[AtCoder] ABC 128 C – Switches

問題

方針

ビット全探索

制約を見ずにこの問題を解こうとすると、ドツボに嵌るかもしれません。スイッチの数と電球の数は最大でも \( 10 \) なので、全探索を考えます。スイッチの状態は on/off の \( 2 \) 通りなので、ビット全探索を用います。

例えば、スイッチが on のときを \( 1 \)、off のときを \( 0 \) と表します。スイッチの数が \( 3 \) 個のとき、スイッチの状態のパターンは、\( (0, 0, 0)\), \( (0, 0, 1)\), \( (0, 1, 0)\), \((1, 0, 0) \), \( (0, 1, 1)\), \( (1, 0, 1)\), \(( 1, 1, 0)\), \( (1, 1, 1)\) の \( 2^3 \) 通りあります。

実装

全体のスイッチの状態はビット列で表現できるので、ある電球に接続されているスイッチが on である個数を数え上げ、条件を満たすかどうか調べます。これを全ての電球に対して行います。

コード

提出したコード

ビット全探索と実装部分