Learn search with Python # 2bit search, permutation search

bit search, permutation search

Deepen understanding of bit search and permutation search through past questions of AtCoder Beginner Contest.

bit full search

Problem: ABC079C --Train Ticket Joisino, sitting in the waiting room at the station, is looking at the ticket. On the ticket, she has four, and the integers A, B, C, and D, which are 0 or more and 9 or less, are written in this order as reference numbers. Create an expression by putting + or-in op1, op2, op3 so that A op1 B op2 C op3 D = 7. Note that no input is given for which there is no answer, and if there are multiple answers, any of them may be output. Constraints: 0 <= A, B, C, D <= 9

ABC079C.py


ABCD="0290"
# 1<<3 = 1000 = 8 => [+or-,+or-,+or-]8 ways
for bit in range(1<<3):
  res=int(ABCD[0])
  form=ABCD[0]
  for i in range(3):
    if(bit & 1<<i):
      res+=int(ABCD[i+1])
      form+='+'+ABCD[i+1]
    else:
      res-=int(ABCD[i+1])
      form+='-'+ABCD[i+1]
      
  if res == 7:
    form+='=7'
    print(form)
    break

Problem: ABC128C --Switches N switches with on and off states and switches with M bulbs are numbered 1 to N, and bulbs are numbered 1 to M. The light bulb i is connected to ki switches and lights up when the remainder of the number of switches si1, si2, ..., siki that are on divided by 2 is equal to pi. How many combinations of switch on/off states are there so that all the light bulbs light up? Constraints: 1 <= N, M <= 10

ABC128C.py


N,M = 2,2
ks = [[2,1,2],[1,2]]
P = [0,1]
S = []
for ss in ks:
  S.append(ss[1:])
ans=0
#(1<<N) = 100(2) = 4(10) 
#(on,off)(on,on)(off,off)(off,on)4 ways
for bit in range(1<<N):
  flag = True
  for i in range(M):
    on=0
    #Switch scan connected about bulb i
    for s in S[i]:
      #AND(sw2,swi)&(1<<(s-1))
      if bit & (1<<(s-1)):
        on+=1
    #Whether the number of lights is even or odd
    if on%2 != P[i]:
      flag=False
      break
  #Both flags=If True
  if flag:
    ans+=1
print(ans)

Problem: ABC031D-Wordplay Japan has a culture of puns that associate numbers with short strings. Takahashi who was interested in this is 1 or more Positive integer v1 consisting only of numbers less than or equal to K, v2, ... ,The string w1 corresponding to vN and each positive integer,w2,...,wN pair(v1, w1), (v2, w2), ... , (vN, wN)Therefore, I decided to infer which number corresponds to which character string. That is, K character strings s1 that satisfy the following conditions, s2, ... ,I want to find sK. For any integer i that satisfies 1 ≤ i ≤ K, 1 ≤|si|Satisfy ≤3. For any integer i that satisfies 1 ≤ i ≤ N, the numbers obtained when the integer vi is decomposed digit by digit are d1 in order from the top., d2, ... ,When dl, the character string sd1, sd2, ... ,The string of sdl concatenated in this order is equal to wi. K strings s1, s2, ... ,Create a program that outputs sK

ABC031C.py


Permutation full search

Problem: ABC145C --Average Length There are N towns on the coordinate plane. Town i is located at coordinates (xi, yi). The distance between town i and town j is √ (xi−xj) 2 + (yi−yj) 2. When you visit all of these towns once, there are a total of N! Streets to visit. Distance traveled from the first visited town, through the second visited town, the third visited town, ..., to the Nth visited town (movement from town to town is a straight line) Let) be the length of the route. Calculate the average length of these N! Paths. Constraints: 2 <= N <= 8

ABC145C.py


import itertools
import math
N=3
xy=[[0,0],[1,0],[0,1]]

lists=list(itertools.permutations(range(N)))

def dis(X,Y):
  distance = math.sqrt((X[0]-Y[0])**2+\
                 (X[1]-Y[1])**2)
  return distance

sum=0
for i in range(len(lists)):
  distance=0
  for j in range(N-1):
    distance+=dis(xy[lists[i][j]],xy[lists[i][j+1]])
  sum+=distance
print(sum/len(lists))

Recursive function full search

Problem: ABC165C --Many Requirements Given positive integers N, M, Q and a pair of four integers (ai, bi, ci, di) Q pairs. Consider a sequence A that meets the following conditions: @A is a positive integer sequence of length N. @ 1 ≤ A1 ≤ A2 ≤ ⋯ ≤ AN ≤ M The score of this sequence is defined as follows. For i that satisfies Abi−Aai = ci, find the maximum score of di (0 if such i does not exist) A. Constraints: 2 <= N <= 10, 1 <= M <= 10,

ABC165C.py


N,M,Q = 3,4,3
#N,The point is that M is small->You can search all
abcd=[[1,3,3,100],[1,2,2,10],[2,3,2,10]]
score=0
com=[]
#score calculation
def calc():
    now=0
    global score
    for a,b,c,d in abcd:
      if com[b-1] - com[a-1] == c:
        now+=d
    score = max(score,now)

def combi(num,com,N):
  #Calculate when the length is reached
  if len(com) == N:
    calc()
    return 
  for i in range(num,M+1):
    com.append(i)
    combi(i,com,N)
    com.pop()
      
combi(1,com,N)
print(score)

Recommended Posts

Learn search with Python # 2bit search, permutation search
Full bit search with Python
Sequential search with Python
Learn Python with ChemTHEATER
python bit full search
Binary search with python
Binary search with Python3
Bit full search with Go
Search engine work with python
Search twitter tweets with python
Streamline web search with python
Build mlpy with python3.3 (64bit) (windows 64bit)
Algorithm learned with Python 10th: Binary search
Change Python 64bit environment to 32bit environment with Anaconda
Getting Started with python3 # 1 Learn Basic Knowledge
Algorithm learned with Python 9th: Linear search
Search the maze with the python A * algorithm
Learn Python! Comparison with Java (basic function)
Learn the design pattern "Singleton" with Python
Algorithm learned with Python 12th: Maze search
Learn the design pattern "Facade" with Python
FizzBuzz with Python3
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Scraping with Python
Statistics with python
Scraping with Python
Python with Go
Twilio with Python
Integrate with Python
Play with 2016-Python
AES256 with python
Tested with Python
python starts with ()
with syntax (Python)
Bingo with python
Zundokokiyoshi with python
PYTHON2.7 64bit version
Excel with Python
Microcomputer with Python
Learn python gestures
Cast with python
Csv output from Google search with [Python]! 【Easy】
Automatically search and download YouTube videos with Python
Causal reasoning and causal search with Python (for beginners)
Learn algorithms with Go @ Full search_Linear search method
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Serial communication with Python
Zip, unzip with python
Primality test with Python
Python with eclipse + PyDev.
Getting Started with python3 # 2 Learn about types and variables
Socket communication with Python
Data analysis with python 2
[Python] Try optimizing FX systole parameters with random search
Scraping with Python (preparation)
Try scraping with Python.
"Object-oriented" learning with python
Run Python with VBA
Solve AtCoder 167 with python
Serial communication with python
[Python] Use JSON with Python