[PYTHON] Journal de participation Atcoder Beginner Contest 146

C

Il s'avère que la recherche complète est plus difficile que la plage. Je pensais qu'il y avait une sorte de règle, mais je ne pouvais pas la résoudre.

Le point de ce problème est

1. Notez que le cercle $ A × N + B × d (N) $ a une linéarité

2. Notez que la dichotomie peut résoudre des problèmes linéaires Est.

3. est explicite.

4. Vous devez être conscient que les tableaux triés ascendants sont synonymes de fonctions linéaires

Je n'ai pas compris 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 Il peut être résolu en définissant un itinéraire et une coloration autre que la couleur utilisée. Méthode gourmande. TLE quand j'ai essayé de faire l'arrangement des couleurs et recherché avec une liste en deux dimensions. Est-ce un problème de mémoire parce qu'il a été résolu en utilisant le type de dictionnaire? On pense que. (Le gros commentaire au milieu est les vestiges de la spécification de liste bidimensionnelle)

from collections import deque
#Entrée, initialisation
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)
 
 
#Stocker la couleur du nœud dans visité
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
#Couleur avec 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]))])