[PYTHON] Atcoder Anfängerwettbewerb 146 Teilnahme Tagebuch

C

Es stellt sich heraus, dass die vollständige Suche schwieriger ist als der Bereich. Ich dachte, es gäbe eine Art Regel, aber ich konnte sie nicht lösen.

Der Punkt dieses Problems ist

1. Beachten Sie, dass der Kreis $ A × N + B × d (N) $ linear ist

2. Beachten Sie, dass Dichotomie lineare Probleme lösen kann Ist.

3. ist selbsterklärend.

4. Sie müssen sich bewusst sein, dass aufsteigende sortierte Arrays gleichbedeutend mit linearen Funktionen sind

Ich habe 2 nicht verstanden.

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 Es kann gelöst werden, indem eine Route definiert und eine andere Farbe als die verwendete Farbe verwendet wird. Gierige Methode. TLE als ich versuchte die Farbanordnung zu machen und mit einer zweidimensionalen Liste suchte. Ist es ein Speicherproblem, weil es mit dem Wörterbuchtyp gelöst wurde? Es ist angedacht, dass. (Der große Kommentar in der Mitte sind die Überreste der zweidimensionalen Listenspezifikation)

from collections import deque
#Eingabe, Initialisierung
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)
 
 
#Speichern Sie die Knotenfarbe in besucht
# visited_edge = [[0] * N for _ in range(N)]
dict = {}
'''
#Farbe mit 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]))])