A person who wants to clear the D problem with ABC of AtCoder tried to scratch

Introduction

Purpose

from now on

Link to the problem

Answer

ABC 142 D

import math 

A, B = [int(item) for item in input().split()]

def gdc(A, B):
    if B == 0:
        return A
    else:
        return gdc(B, A % B)

def chk_pn(num):
    flag = True
    if num  <= 3:
        pass
    else:    
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                flag = False
                break
    return flag

def mk_factor(num):
    max_divisor = int(math.sqrt(num))+1
    divisor = 2
    factor_list = [1]

    while divisor <= max_divisor:
        if num % divisor == 0:
            factor_list.append(divisor)
            num /= divisor
        else:
            divisor += 1
    
    factor_list.append(num) #Don't forget to include the undivided number in the divisor
    return factor_list

GDC = gdc(A, B)
pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]
# print(pn_factor)
print(len(set(pn_factor)))

ABC 141 D


import heapq as hp
N, M = [int(item) for item in input().split()]
price_list = sorted([-1 * int(item) for item in input().split()])

total_m = 0

def discount(price_list, ticket_num):
    total_ticket =0
    hp.heapify(price_list)

    while total_ticket < ticket_num:
        temp = hp.heappop(price_list)
        hp.heappush(price_list, -1* (-1*temp//2))
        total_ticket += 1

    return price_list

res = discount(price_list, M)
print(res)
print(-1 * sum(res))

ABC 140 D

     def compress(arr):
    """The person who compressed and disappeared is happy"""
    cnt_h = 0
    new_arr = []
    comp_arr = ['L']

    #At first, the beginning is L. This rotation is no-can
    if arr[0] == 'R':
        for item in arr:
            if item == 'L':
                new_arr.append('R')
            else:
                new_arr.append('L')

            prev_item = item
    else:
        new_arr = arr
    #Count compression operations and compressed scraps

    for i in range(1, N):
        if new_arr[i - 1] == new_arr[i]:
            cnt_h += 1
        else:
            comp_arr.append(new_arr[i])

    return [comp_arr, cnt_h] 


def execute(arr, cnt_h, K):
    #Number of operations required to invert all boundaries
    max_rotation = len(arr)//2
    #It ends when all become L or the number of inversions reaches K
    if max_rotation <= K:
        cnt_h += len(arr) - 1
    else:
        cnt_h += 2*K

    return cnt_h

ABC 139 D

N = int(input())
print((N-1)*N //2 )

ABC 138 D

python list version

N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]

query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]

val_list = [0 for _ in range(N)]

linked_node_list = [[] for _ in range(N)]

#Create a link relationship for undirected graphs (including upstream connections)
for a, b in tree_list:
    a, b = int(a)-1, int(b) -1
    linked_node_list[a].append(b) #Add child
    linked_node_list[b].append(a) #Add parent


for index, val in query_list_int:
    val_list[index-1] += val

stack = [0] #Generates a stack containing the value of the root node and stores the target to be patrolled
parent = [0] * (N+1) #Stores a stack that stores visited nodes

#If you use a recursive function, you will get stuck in the memory limit, so execute it sequentially with while
#Use LIFO on the stack. Since it becomes a LIFO, you can perform a depth-first search while looking at the youngest person.
#Remember the parent node and try to play it
#If you define it with a directed graph, you don't need to play the parent

while True:
    #Patrol in order from the route
    v=stack.pop()
    for child in linked_node_list[v]:
        if child != parent[v]:
            parent[child] = v #Store visited nodes
            stack.append(child) #Store the connection destination node of this node v on the stack
            val_list[child] += val_list[v] #Cumulative sum
    if not stack:
        #The patrol ends when the stack runs out
        break

print(*val_list)

pypy3 node object version


from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)

    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)

            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

Problems to practice D problem

Disco2020 B


N = int(input())
A_list = [int(item) for item in input().split()]

all_sum = sum(A_list)

F_sum_list = [A_list[0]]

for j in range(1,N):
    F_sum_list.append(F_sum_list[-1] + A_list[j])

delta_list = [abs(all_sum - 2* i) for i in F_sum_list]

print(min(delta_list))

ABC 146 C


A, B, X = [int(item) for item in input().split()]
res_list = []
left = 1 -1
right = 10 ** 9 + 1

is_search = True

while is_search:
    N = (left + right)//2
    res = A * N + B * len(str(N))

    if res > X:
        right = N
    elif res <= X:
        res_list.append(N)
        left = N

    if right - left <= 1:
        is_search = False

if res_list == []:
    print(0)
else:
    print(max(res_list))
import math
 
A, B, X = [int(item) for item in input().split()]
 
res = 0
res_list = []
delta = 10**9 // 4
N= 10**9 // 2
 
 
is_search = True
 
while is_search:
    res = A * N + B * len(str(N))
    if res > X:
        N = N -delta
    elif res <= X:
        res_list.append(N)
        N = N + delta
 
    if delta <= 0:
        break
 
    delta = delta // 2 
 
new_res_list = []
for i in range(N - 1000, N + 1000):
    res = A * i + B * len(str(i))
    if res <= X:
        new_res_list.append(i)
 
 
if new_res_list == [] or max(new_res_list) <1:
    print(0)
else:
    if 1<= max(new_res_list) < 10**9:
        print(max(new_res_list))
    else:
        print(10**9)

Recommended Posts

A person who wants to clear the D problem with ABC of AtCoder tried to scratch
I wanted to solve the ABC164 A ~ D problem with Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
[AtCoder explanation] Control the A, B, (C), D problems of ABC165 with Python!
[AtCoder explanation] Control the A, B, C, D problems of ABC181 with Python!
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve AtCoder ABC168 with python (A ~ D)
[AtCoder explanation] Control the A, B, C problems of ABC182 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC187 with Python!
[AtCoder explanation] Control the A, B, C problems of ABC184 with Python!
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
I tried to create a model with the sample of Amazon SageMaker Autopilot
I tried to solve the problem with Python Vol.1
I tried to visualize the characteristics of new coronavirus infected person information with wordcloud
The 15th offline real-time I tried to solve the problem of how to write with python
I tried to find the entropy of the image with python
I tried to find the average of the sequence with TensorFlow
How to write offline real time I tried to solve the problem of F02 with Python
Finding a solution to the N-Queen problem with a genetic algorithm (2)
[Python] I want to make a 3D scatter plot of the epicenter with Cartopy + Matplotlib!
I tried to solve a combination optimization problem with Qiskit
A story about how to deal with the CORS problem
AtCoder ABC 182 Python (A ~ D)
Create a 2D array by adding a row to the end of an empty array with numpy
I wrote a doctest in "I tried to simulate the probability of a bingo game with Python"
I tried using PI Fu to generate a 3D model of a person from one image
I tried to unlock the entrance 2 lock sesame with a single push of the AWS IoT button
A story about a person who uses Python addicted to the judgment of an empty JavaScript dictionary
I tried to automate the watering of the planter with Raspberry Pi
[AtCoder commentary] Win the ABC165 C problem "Many Requirements" with Python!
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
Try to solve the N Queens problem with SA of PyQUBO
I tried to create a list of prime numbers with python
I tried to expand the size of the logical volume with LVM
I tried to improve the efficiency of daily work with Python
PhytoMine-I tried to get the genetic information of plants with Python
I tried to make a mechanism of exclusive control with Go
Solve ABC166 A ~ D with Python
A beginner who has been programming for 2 months tried to analyze the real GDP of Japan in time series with the SARIMA model.
I tried to make a thumbnail image of the best avoidance flag-chan! With RGB values ​​[Histogram] [Visualization]
A super beginner who does not know the basics of Python tried to graph the stock price of GAFA
I want to solve the problem of memory leak when outputting a large number of images with Matplotlib
I tried to visualize the age group and rate distribution of Atcoder
I tried to express sadness and joy with the stable marriage problem.
[Introduction to Python] How to sort the contents of a list efficiently with list sort
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
I tried to get the authentication code of Qiita API with Python.
I tried to analyze the negativeness of Nono Morikubo. [Compare with Posipa]
A beginner of machine learning tried to predict Arima Kinen with python
I tried to visualize the text of the novel "Weathering with You" with WordCloud
I tried to get the movie information of TMDb API with Python
Try to solve a set problem of high school math with Python
I tried to display the altitude value of DTM in a graph
I tried to verify the result of A / B test by chi-square test
I tried to predict the behavior of the new coronavirus with the SEIR model.
I tried to easily create a high-precision 3D image with one photo [-1]. (Is the hidden area really visible?)
AtCoder ABC155 Problem D Pairs Review Note 1
I tried to move the 3D model by doing something like motion capture with just a laptop + webcam
AtCoder Green tried to solve with Go
I wanted to know the number of lines in multiple files, so I tried to get it with a command
I tried 3D detection of a car