Pythonで10進数→2進数 競技プログラミングのテクニック02-

プログラミング

どーも、masukenです。

今回はABC128の問題を解いていて、Pythonで10進数から2進数に変換するには
どうすればいいのだろうか?と疑問に思ったので、
それを整理して、解説したいと思います。

スポンサーリンク

ABC 128-C Switches

ABC 128-C Switches

この問題は、問題文を理解するのに苦労します。情報を整理すると、

  • N個のスイッチが存在している。
  • M個の電球が存在している。
  • 電球はそれぞれki個のスイッチと繋がっている。
  • 電球はスイッチONの数を2で割った数の余りとpiが一致すれば点灯する。

となっています。

入力1を例にして上で述べた情報を整理すると、

入力例1
N = 2 , M = 2
k1 = 2, s11 = 1, s12 = 2
k2 = 1, s21 = 1
p1 = 0, p2 = 1

のようになります。

この問題を解く方針

この問題では、スイッチの数、電球の数であるN、Mはそれぞれ10個以下という条件があります。
例えば、スイッチが10個あったとして、それを全探索したとしても、
2^10 = 1024通りしかありません。
そのため、この問題は全探索で解くことにします。

また、この問題ではスイッチ、電球のON、OFFを問題としているため、
スイッチのON、OFFはBinary形式で表した方が分かりやすそうです。

そのため、スイッチがn個ある時の全てのパターンをバイナリで
ex. n = 4 switch = [0, 1, 1, 0] → スイッチ1がOFF、スイッチ2がON、3がON、4がOFFを表す。
電球が持っているスイッチをバイナリで
ex. 電球1の標準入力が n = 4 k1 = 3 s11 = 1 s12 = 2 s13 = 4の場合 [1, 0, 1, 1]
のように表したいと思います。

Decimal → Binary

Decimalは10進数、Binaryは2進数のことを表しています。
この章では10進数→2進数に変換する方法をまとめています。

10進数→2進数に変換する方法

上では10進数から2進数に変換する際のコードを例示しています。

bin(数値)とすることにより、数値の2進数を表現することができます。
しかしこの場合、前に’0b’というものがついてきてしまいます。
‘0b’とはこれから続く数字はBinaryですよと示す記号のようなものです。(プレフィックス)
しかし、問題を解く上では邪魔そうなので’0b’を出力しないようにしたいと思います。

format(数値, ‘b’) で出力すると’0b’が出なくなりました。
ちなみに’b’←もBinaryを表しています。
これを’o’や’x’に変えれば、8進数や16進数でも表すことができます。(16進数は’h’ではない)

listにしたい場合は、上から3番目のコードのようにすることで可能となります。

また、この問題の場合はスイッチがn個ある時のパターンを全て探索したいため、
2進数にしたときの桁数を合わせた方が解きやすそうです。
そのため、左の方を0で埋めてしまいましょう、としたのが4番目のコードです。
zfill(桁数)とすることで2進数の数値の桁数を合わせることができます。
bの出力を見るとわかるように10(d)→1010(b)と10の2進数表記は4桁の数となりますが、
zfillを使うことにより、2進数の左を0で埋めることができます。

スイッチのON、OFFをBinary形式で表す

これはスイッチのON、OFFをBinary形式で表すためのコードです。
nは桁数を表しています。
for文で2^nまでの10進数の数字を全て2進数に変換していることが分かります。
また、listやzfillを使うことで後で処理しやすい形に変換しています。

まとめ

今回はABC 128-Cの問題を解くに当たって使用した、
Pythonで10進数を2進数に変換する方法を解説しました。

競技プログラミングを行なっていく上でまだまだ知らない知識はありますが、
一つずつ理解して使えるようにしていこうと思っています。

それでは、また。

コメント

タイトルとURLをコピーしました