[Python] Binary Acing 2020D

Acing 2020D

X is so large that it cannot be simply simulated. Here, the popcount of X is at most N, so the value of X divided by the popcount is always less than N. Also, when Xi is inverted, the popcount of such an integer is equal to (X's popcount ± 1). Therefore, for all numbers from 1 to N, divide them by popcount and replace them too much to find the number of operations until it becomes 0, and then for each digit such that Xi = 1, (X). If you find the sum of too much divided by (popcount + 1) of and the sum of too much divided by (popcount-1 of X), f (Xi) will be calculated as f (Xi) if Xi is 1. The sum of the remainders divided by)-2 ^ i divided by (popcount-1 of X) is calculated, and this is divided by (popcount-1 of X) to obtain a number less than N. Similarly, if Xi is 0, find the sum of the remainders divided by (X popcount + 1) + 2 ^ i divided by (X popcount + 1), and divide this by (X popcount + 1). You can get a number less than N by dividing by). From the above, it was found that the number of operations required to reach 0 can be determined by O (1) for each Xi.

Here, regarding the amount of calculation for calculating the number of operations for all numbers from 1 to N, the number of popcounts of 2 * 10 ^ 5 or less is at most 18, and the number of popcounts of 18 or less is at most 4, 4 or less. You can see that the popcount is at most 2, the number of popcounts less than 2 is at most 1, and it reaches 0 in a maximum of 5 operations. Therefore, it can be said that the number of operations can be calculated for all numbers from 1 to N by O (NlogN), and it was found that this problem can be solved by O (NlogN). However, note the case where the X popcount is 0 or 1.

Sample code


n = int(input())
x = input()
 
#Original popcount
original_pop_count = x.count('1')
#Invert-1count
one_pop_count = original_pop_count - 1
#Invert+1count
zero_pop_count = original_pop_count + 1
 
#Residual in each ± 1
if one_pop_count == 0:
  one_mod = 0
else:
  one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
#Precalculation of f
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1
 
#Precalculation of pow2
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            # - 2^i % 2
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        # + 2^i % 2
        nxt %= zero_pop_count
        print(f[nxt] + 1)

Recommended Posts

[Python] Binary Acing 2020D
Calculate 2D IDCT ~ Python
Binary search in Python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Binary search with python
Binary search with Python3
Binary search in Python (binary search)
Atcoder Acing Programming Contest Python
Create 3d gif with python3
Python: 3D array image (numpy.array)
python> Handling of 2D arrays
Binary search in Python / C ++
Algorithm in Python (binary search)
Solve ABC175 D in Python
AtCoder ABC 182 Python (A ~ D)
Python 2D array trap [Copy array]
Write a binary search in Python
3D skeleton structure analysis with Python
Python
Save the binary file in Python
Create a binary file in Python
I'm addicted to Python 2D lists
[Python scipy] Upscale / downscale 2D data
AtCoder ABC130 D Cumulative Sum Binary Search Solved by Ruby and Python
[Python, Julia] 3D display in Jupyter-Mayavi library
Algorithm learned with Python 10th: Binary search
[Python] How to convert a 2D list to a 1D list
ABC 157 D --Solve Friend Suggestions in Python!
Try working with binary data in Python
Algorithm in Python (ABC 146 C Binary Search
2D FEM stress analysis program with Python
Python> link> 2D array initialization and assignment
Example of 3D skeleton analysis by Python
Don't use \ d in Python 3 regular expressions!
Solve AtCoder ABC168 with python (A ~ D)
AtCoder Beginner Contest: D Question Answers Python
Solve ABC165 A, B, D in Python