[GO] 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)