ただのメモ

他の人に見せても良い方のメモ

Competitive Programing Typical 90 Problem day2

2nd day.

Today's theme is Brute Force Search by using bit transformation.

Bit transformation is useful when we want to express all subsets of set.

 

Code is below.

  • 全探索が有効打になるのは、そもそもの有り得る解の数が少ないとき。
  • Bit全探索を使って、文字の組み合わせを全て試した。
  • Bitに変えると、0か1かの文字列なので、今回の"(", ")"の2通りに上手く変換できた。
  • これが3種類だと、3進法に変える。p種類なら、p進法を使えばよい。
  • 今回の使用した、"checker"では、0を切ったらやめた。本当は上限を設けても良かった。

ここまで書いたが、何言ってるか伝わりにくく感じたので、イメージをお絵描きしたい。

  • こちらを参照する。
  • 実際に色分けをしつつ、書いた折れ線グラフがこちら。

f:id:medical-science:20220105161535p:plain

 

from itertools import accumulate
N = int(input())
def checker(s): 
  #ビット風の数字列が条件を満たすか調べる
  temp = 0
  for i in range(N):
    temp += s[i]
    if temp >= 0:
      #途中で0を割ってほしくない
      pass
    else:
      return False
      break
  else:
    if temp == 0:
      #終わりが0なら、良い
      return True
    else:
      return False

def transform_into_bit(x):
  temp2 = [0] * N
  for i in range(N):
    if x%2 == 0:
      element2 = 0
    else:
      element2 = 1
    temp2[i] = 2 * element2 -1
    x //= 2
    #2で割って、1の位を見る
  else:
    return temp2
    #リストで返す




all_answer = 
#全ての答えを記憶
def bit_all_search():

  for j in range(2**N):
    temp3 = transform_into_bit(j)
    if checker(temp3):
      #良い答えを選別
      answer = 
      for k in range(N):
        #ここで文字列に変換する
        if temp3[k] == 1:
          answer.append("(")
        else:
          answer.append(")")
      else:
        print(*answer, temp3)
        all_answer.append(list(accumulate(temp3)))
        #後のために、累積和をとる
    else:
      pass

bit_all_search()


import matplotlib.pyplot as plt
x = [for i in range(N+1)]
M = len(all_answer)
colorlist = []
#色分けするために、色のリストを作る
for a in range(11):
  for b in range(11):
    for c in range(11):
      colorlist.append([a*0.1, b*0.1, c*0.1])
for i in range(M):
  plt.plot(x, [0]+all_answer[i], marker = 'o', color=colorlist[20 * i] )
  #全ての答えをグラフにする。
plt.show()
print("number of solution",M)

 

何通りかの式が気になるが、今は良いとする。

バイバイ!