Ant book with python (chapter3 intermediate edition ~)

Introduction

We will solve the problems of the programming contest challenge book (commonly known as ant book) with python. We plan to update it little by little, including similar issues.

For the beginner's edition, I think you should refer to @ saba's article. https://qiita.com/saba/items/affc94740aff117d2ca9

3-1 Not just searching for values! "Binary search"

p128 lower_bound

N = 5
A = [2, 3, 3, 5, 6]
K = 3

#Index of the leftmost Ai that is K or higher
print(bisect_left(A, K))

p129 cable master

N = 4
K = 11
L = [8.02, 7.43, 4.57, 5.39]

def f(target):
    cnt = 0
    for i in range(N):
        cnt += math.floor(L[i] / target) #How many strings of length target can be taken from each string
    if cnt >= K: #If you get more than K
        return True
    else:
        return False

ng = 0
ok = 10 ** 9 + 1
for i in range(100):
    mid = (ng + ok) / 2
    if f(mid):
        ng = mid
    else:
        ok = mid
print(math.floor(ok * 100) / 100) #Find up to two decimal places

p131 aggressive cows

N = 5
M = 3
X = [1, 2, 8, 4, 9]
X.sort()

def c(d):
    last = 0 #Put the first hut
    # M -Can the hut be placed at a distance of d or more from the current location once?
    for _ in range(M - 1):
        crt = last + 1 #Advance crt to find a place to put the next hut
        while crt < N and X[crt] - X[last] < d:
            crt += 1 

        if crt == N: #If you can't find a place to put the hut next
            return False

        last = crt #Put the next hut

    return True # M -If you put a hut once

ok = -1
ng = 10 ** 9 + 1

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if c(mid):
        ok = mid
    else:
        ng = mid
print(ok)

p132 Average maximization

N = 3
K = 2
W = [2, 5, 2]
V = [2, 3, 1]

def c2(x, w, v):
    #A set of products selected to satisfy "the value per unit weight is x or more"
    # S([w1, v1], [w2, v2]...[wk, vk])And. This time
    # sum(v1, v2...vk) / sum(w1, w2...wk) >=From x
    # sum(v1, v2...vk) - x * sum(w1, w2...wk) >= 0
    # sum(v1 - x * w1, v2 - x * w2, ...vk - x * wk) >= 0

    # v[i] - x * w[i]When k are taken in descending order, it should be 0 or more
    cnt = 0
    items = [v[i] - x * w[i] for i in range(N)]
    items.sort(reverse = True)
    for i in range(K):
        cnt += items[i]
    return cnt >= 0

ok = 0
ng = 10 ** 9 + 1

for i in range(100):
    mid = (ng + ok) / 2
    if c2(mid, W, V):
        ok = mid
    else:
        ng = mid
print(ok)

3-2 Carefully selected! Frequent technique (1)

p135 subsequence

N = 10
S = 15
A = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8]
right = 0
total = 0
ans = float('inf')

for left in range(N):
    while right < N and total < S:
        #Advance right until the condition is met total>=Censor when it becomes S

        # left, right, total = 0
        # total <Because it is S, A[0]Add to total and increase right by one
        # left, right, total = 0, 1, 5
        # ...
        # left, right, total = 0, 4, 14
        # total <Because it is S, A[4]Add to total(At this point total<(Become S) Increase right by one
        # left, right, total = 0, 5, 24
        # total >=Because it is S, A[5]Do not add

        total += A[right]
        right += 1

    #If total<If right reaches the right end with S
    if total < S:
        continue
 
    # left, right = 0,If 5, it is a closed section[0, 4]Sum becomes S or more
    #→ Half-open section[0, 5)Sum becomes S or more
    ans = min(ans, right - left)

    if left == right:
        right += 1
    total -= A[left]

    # print(left, right)

print(ans)

p137 Jessica's Reading Problem

P = 5
A = [1, 8, 8, 8, 1]
dict = {}
for i in A:
    dict[i] = 0

l = 0
cnt = 0
ans = float('inf')
#Advance one right and sharpen the left as much as possible
for r in range(P):
    #Add a new one
    if dict[A[r]] == 0: #If a new element comes
        cnt += 1
    dict[A[r]] += 1

    #Shave the left while including all the elements
    while True:
        #If there is only one element, it cannot be scraped
        if dict[A[l]] == 1:
            break
        #If there are two or more elements, scrape
        dict[A[l]] -= 1
        l += 1

    if cnt < len(dict.items()):
        continue

    ans = min(ans, r - l + 1)
print(ans)

p138 Face The Right Way

N = 7
S = 'BBFBFBB'

def judge(k):
    imos = [0] * N
    #Whether to turn over the first time
    if S[0] == 'B':
        imos[0] = 1
    #If the cow is facing backwards from the front, turn it over
    # k =If 4
    # BBFBFBB
    # [  ]
    #  [  ]
    #   [  ]
    #    [  ]
    #Turn over up to 4 times
    for i in range(1, N - k + 1):
        if i < k:
            rev = imos[i - 1]
        else:
            rev = imos[i - 1] - imos[i - k]
        if (S[i] == 'B') ^ (rev % 2):
            imos[i] += 1
        imos[i] += imos[i - 1]

    #Find out if the rest of the cows are facing forward
    for i in range(N - k + 1, N):
        if i < k:
            rev = imos[N - k]
        else:
            rev = imos[N - k] - imos[i - k]
        if (S[i] == 'B') ^ (rev % 2):
            return float('inf')

    return imos[N - k]

K = 0
M = float('inf')
for i in range(1, N + 1):
    opt = judge(i)
    if opt < M:
        M = opt
        K = i
print(K, M)

p141 Fliptile

M = 4
N = 4
maze = [
[1, 0, 0, 1],
[0, 1, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
]

def changer(o, f):
    for i in range(1, M):
        for j in range(N):
            #Examine the maze and flip one above
            #If maze is black and flip is flipped an even number of times or maze is white and flip is flipped an odd number of times
            if (maze[i - 1][j] == 1) ^ (f[i - 1][j] % 2):
                o[i][j] += 1
                f[i][j] += 1
                f[i - 1][j] += 1
                if j >= 1:
                    f[i][j - 1] += 1
                if j < N - 1:
                    f[i][j + 1] += 1
                if i < M - 1:
                    f[i + 1][j] += 1

    return o, f

#Full search for the first line
#When the first line is decided, the second and subsequent lines are uniquely decided
#Full search for the first line:O(2 ** N)Fill in the second and subsequent lines:O(MN)Because it takes
#The total amount of calculation is O(MN(2 ** N))become
for bit in range(1 << N):
    opt = [[0] * N for i in range(M)]
    flip = [[0] * N for i in range(M)]
    for i in range(N):
        if bit & (1 << i):
            opt[0][i] += 1
            flip[0][i] += 1
            if i >= 1:
                flip[0][i - 1] += 1
            if i < N - 1:
                flip[0][i + 1] += 1

    opt, flip = changer(opt, flip)

    #Judgment for the last column
    for j in range(N):
        #If not
        if (maze[M - 1][j] == 1) ^ (flip[M - 1][j] % 2):
            break
    else:
        for i in opt:
            print(*i)

p145 physics experiment

#Think of balls as slipping through like ants
N, H, R, T = 2, 10, 10, 100
g = 10

def judge(time):
    if time < 0:
        return H
    t = math.sqrt(2 * H / 10)
    k = int(time / t)
    if k % 2 == 0:
        d = time - k * t
        return H - g * d * d / 2
    else:
        d = k * t + t - time
        return H - g * d * d / 2

ans = []
for i in range(N):
    #Drop the ball every second
    ans.append(judge(T - i))
#You can think of the balls as slipping through each other
ans.sort()
for i in range(N):
    #Note that R is centimeters but H is meters
    print(ans[i] + (2 * R * i / 100))

p147 4 values whose sum is 0


#Binary search
def binary_search_loop(data, target):
    imin = 0
    imax = len(data) - 1
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return imid
        elif target < data[imid]:
            imax = imid - 1
        else:
            imin = imid + 1
    return False

N = 6
A = [-45, -41, -36, -36, 26, -32]
B = [22, -27, 53, 30, -38, -54]
C = [42, 56, -37, 75, -10, -6]
D = [-16, 30, 77, -46, 62, 45]

re_A = []
re_C = []
# Ai + Bj
for i in range(N):
    for j in range(N):
        re_A.append(A[i] + B[j])
re_A.sort()
# Ci + Dj
for i in range(N):
    for j in range(N):
        re_C.append(C[i] + D[j])
re_C.sort()

ans = 0
for i in re_A:
    # ind1:Leftmost index among those with a total of 0 or more
    # ind2:Leftmost index among those with a total of 1 or more
    #             ind1       ind2
    # [...-2, -1, (0), 0, 0, (2), 2, 3]
    ind1 = bisect_left(re_C, 0 - i)
    ind2 = bisect_left(re_C, 0 - i + 1)
    ans += ind2 - ind1
print(ans)

p148 Giant knapsack

N = 4
w = [2, 1, 3, 2]
v = [3, 2, 4, 2]
W = 5

#Half full enumeration+Binary search
def re_list(weight, value):
    fore_list = []
    #First, combine all the ways
    for bit in range(1 << len(weight)):
        wei = 0
        val = 0
        for i in range(len(weight)):
            if bit & (1 << i):
                wei += weight[i]
                val += value[i]
        fore_list.append([wei, val])
    fore_list.sort()

    #List rebuild
    #I'm erasing what I obviously don't need
    # ABC032 D -See the explanation of the knapsack problem
    alta_w = []
    alta_v = []
    now = -1
    for i in fore_list:
        if now < i[1]:
            now = i[1]
            alta_w.append(i[0])
            alta_v.append(i[1])
    return alta_w, alta_v

def half_knapsack(N, limit, weight, value):
    #Half full enumeration
    fore_w, fore_v = re_list(weight[:N // 2], value[:N // 2])
    back_w, back_v = re_list(weight[N // 2:], value[N // 2:])

    ans = 0
    for b_w, b_v in zip(back_w, back_v):
        if b_w > limit:
            continue

        opt = b_v
        index = bisect_right(fore_w, limit - b_w)
        if index > 0:
            opt += fore_v[index - 1]
        ans = max(ans, opt)

    return ans
print(half_knapsack(N, W, w, v))

number of p150 regions

#Given x,Since the upper limit of y is small, it is not compressed at all in this input example.
W, H, N = 10, 10, 5
# (x1, y1)From(x2, y2)Draw a line
X1 = [i - 1 for i in [1, 1, 4, 9, 10]]
X2 = [i - 1 for i in [6, 10, 4, 9, 10]]
Y1 = [i - 1 for i in [4, 8, 1, 1, 6]]
Y2 = [i - 1 for i in [4, 8, 10, 5, 10]]

#Vertical
row = set()
r_index = {}
#side
col = set()
c_index = {}
#conversion
for x, y in zip(X1 + X2, Y1 + Y2):
    #Which row is needed
    row.add(y)
    if y > 0:
        row.add(y - 1)
    if y < H - 1:
        row.add(y + 1)

    #Which column is needed
    col.add(x)
    if x > 0:
        col.add(x - 1)
    if x < W - 1:
        col.add(x + 1)

#Which coordinates will be after compression
H = len(row)
row = sorted(list(row))
for i in range(H):
    r_index[row[i]] = i

W = len(col)
col = sorted(list(col))
for i in range(W):
    c_index[col[i]] = i

X1 = [c_index[i] for i in X1]
X2 = [c_index[i] for i in X2]
Y1 = [r_index[i] for i in Y1]
Y2 = [r_index[i] for i in Y2]

# print(X1, Y1, X2, Y2)
# X1: [0, 0, 3, 8, 9]
# Y1: [3, 7, 0, 0, 5]

# X2: [5, 9, 3, 8, 9]
# Y2: [3, 7, 9, 4, 9]

#Then solve normally
maze = [[0] * W for i in range(H)]
#Draw a line
for x1, y1, x2, y2 in zip(X1, Y1, X2, Y2):
    #Vertical line
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        for i in range(y1, y2 + 1):
            maze[i][x1] = 1
    #horizontal line
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        for i in range(x1, x2 + 1):
            maze[y1][i] = 1

#p35 lake counting
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

def dfs(y, x):
    maze[y][x] = 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == 0:
            dfs(ny, nx)

ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == 0:
            dfs(y, x)
            ans += 1
print(ans)

3-3 Let's know various data structures

Recommended Posts

Ant book with python (chapter3 intermediate edition ~)
I tried to solve the ant book beginner's edition with python
Solve "AtCoder version! Ant book (beginner)" with Python!
100 Language Processing Knock with Python (Chapter 1)
"Effective Python 2nd Edition" Chapter 3 <Functions>
100 Language Processing Knock with Python (Chapter 3)
Ant book in python: Sec. 2-5 Graph
Ant book in python: page 42 coin problem
Ant book in python: Priority queue self-implementation
Ant book in python: Sec. 2-4, data structures
Ant book in python: Sec.2-5 Dijkstra's algorithm
"Effective Python 2nd Edition" Chapter 1 <Pythonic Thinking>
Ant book in python: page 43 Interval scheduling
100 Language Processing Knock with Python (Chapter 2, Part 2)
Ant book in python: Sec. 2-5 Graph (preparation)
100 Language Processing Knock with Python (Chapter 2, Part 1)
Get Started with TopCoder in Python (2020 Edition)
Ant book in python: page 49 Fence Repair
FizzBuzz with Python3
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Scraping 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)
I tried playing mahjong with Python (single mahjong edition)
I want to solve APG4b with Python (Chapter 2)
Bingo with python
Zundokokiyoshi with python
Excel with Python
Microcomputer with Python
Ant book in python: page 47 Saruman's Army (POJ 3069)
Cast with python
Try to solve the programming challenge book with python3
Destroy the intermediate expression of the sweep method with Python
[Chapter 3] Introduction to Python with 100 knocks of language processing
[Chapter 2] Introduction to Python with 100 knocks of language processing
[Basics of Modern Mathematical Statistics with python] Chapter 1: Probability
[Technical book] Introduction to data analysis using Python -1 Chapter Introduction-
[Chapter 4] Introduction to Python with 100 knocks of language processing
Serial communication with Python
Zip, unzip with python
Django 1.11 started with Python3.6
Python with eclipse + PyDev.
Socket communication with Python
Data analysis with python 2
Scraping with Python (preparation)
A * algorithm (Python edition)
Try scraping with Python.
Learning Python with ChemTHEATER 03
Sequential search with Python
"Object-oriented" learning with python
First Python 3rd Edition
Handling yaml with python
Solve AtCoder 167 with python
Serial communication with python