[PYTHON] Atcoder Beginner Contest 146 Participation Diary

C

It turns out that the full search is more difficult than the range. I thought there was some kind of law, but I couldn't solve it.

The point of this problem is

1. Notice that the $ A × N + B × d (N) $ circle has linearity

2. Notice that binary search can solve linear problems Is.

3. is self-explanatory.

4. You have to be aware that ascending sorted arrays are synonymous with linear functions

I didn't understand 2.

A , B , X = map(int,input().split())
ans = 10**9 // 2
diff = ans
digit_ans = len(str(ans))
while not A * ans + B * digit_ans <= X < A * (ans+1) + B * len(str(ans+1)):
    diff = max(diff // 2 , 1)
    if A * ans + B * digit_ans > X:
        ans -= diff
    else:
        ans += diff
    digit_ans = len(str(ans))
    #print(ans)
    if ans >= 10 ** 9:
        print(10**9)
        exit()
    elif ans <= 0:
        print("0")
        exit()
print(ans)

D It can be solved by defining one route and coloring other than the color used. Greedy algorithm. When I tried to do the color scheme and searched with a two-dimensional list, TLE. Is it a memory problem because it was solved by using the dictionary type? It is thought that. (The big comment out in the middle is the remnants of the two-dimensional list specification)

from collections import deque
#Input, initialization
N = int(input())
tree = [[] for _ in range(N)]
input_list = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    input_list.append([a, b])
    tree[a].append(b)
    tree[b].append(a)
 
 
#Store node color in visited
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
#Color with bfs
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            if visited_edge[now_node][next_node] != 0:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            visited_edge[next_node][now_node] = now_color
            visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
'''
def bfs(now_node, max_val=0):
    queue = deque([[tree[now_node], -1, now_node]])
    while queue:
        next_nodes, before_color, now_node = queue.pop()
        now_color = 1
        for next_node in next_nodes:
            key = tuple(sorted([now_node, next_node]))
            if not dict.get(key) is None:
                continue
            if now_color == before_color:
                now_color += 1
            if max_val < now_color:
                max_val = now_color
            dict[key] = now_color
            # visited_edge[now_node][next_node] = now_color
            queue.appendleft([tree[next_node], now_color, next_node])
            now_color += 1
    return max_val
 
ans = bfs(0)
print(ans)
for a, b in input_list:
    # print(visited_edge[a][b])
    print(dict[tuple(sorted([a,b]))])