H - 1-9 Grid, C - 高橋君の給料, G - Longest Path

H - 1-9 Grid

O(N^2*11)
漸化式は、

i,j 現在の座標
i2,j2 前の座標
cost[i][j] = min(cost[i][j], cost[i2][j2] + abs(i-i2) + abs(j-j2))

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

# main
def main():
    N, M = list(map(int, input().split()))
    A = []

    for i in range(0, N):
        row = str(input())
        A.append(row)

    graph = []
    for i in range(0, 11):
        graph.append([])

    for i in range(0, N):
        for j in range(0, M):
            if A[i][j] == 'S':
                v = 0
            elif A[i][j] == 'G':
                v = 10
            else:
                v = int(A[i][j])
            graph[v].append([i,j])

    INF = 10**12
    cost = []
    for i in range(0, N):
        cost.append([INF] * M)

    si, sj = graph[0][0]
    cost[si][sj] = 0

    for n in range(1, 11):
        for i, j in graph[n]:
            for i2, j2 in graph[n-1]:
                cost[i][j] = min(cost[i][j], cost[i2][j2] + abs(i-i2) + abs(j-j2))

    gi, gj = graph[10][0]
    ans = cost[gi][gj]
    if ans==INF:
        ans = -1
    print(ans)

            
# エントリポイント
if __name__ == '__main__':
    main()

C - 高橋君の給料

漸化式は、

0 (N+1以上)
1 (部下が0人)

部下が存在する場合の給料
min_v = 10**10　
max_v = 0
v = f(i)
min_v = min(min_v, v)
max_v = max(max_v, v)
return max_v + min_v + 1

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

N = 0
child = []

def dfs(n):
    if n == N+1:
        return 0
    if len(child[n]) == 0:
        return 1

    min_v = 10**10
    max_v = 0
    for i in child[n]:
        v = dfs(i)
        min_v = min(min_v, v)
        max_v = max(max_v, v)
    
    return min_v + max_v + 1

# main
def main():
    global N, child
    N = int(input())

    for i in range(0, N):
        child.append([])

    for i in range(0, N-1):
        p = int(input())
        child[p-1].append(i+1)

    ans = dfs(0)
    print(ans)

# エントリポイント
if __name__ == '__main__':
    main()

G - Longest Path

O(N+M)

python

import sys
import math
import heapq
import itertools
from collections import deque
from functools import reduce

N = 0
graph = []
indeg = []
length = []
done = []

def dfs(n):
    global length, done
    if done[n]:
        return length[n]

    for i in graph[n]:
        length[n] = max(length[n], dfs(i) + 1)

    done[n] = True

    return length[n]

# main
def main():
    sys.setrecursionlimit(1000000)
    global N, graph, indeg, length, done
    N, M = list(map(int, input().split()))

    graph = []
    for i in range(0, N):
        graph.append([])
    indeg = [0] * N
    length = [0] * N
    done = [False] * N

    for i in range(0, M):
        x, y = list(map(int, input().split()))
        graph[x-1].append(y-1)
        indeg[y-1] += 1

    for i in range(0, N):
        dfs(i)

    print(max(length))

# エントリポイント
if __name__ == '__main__':
    main()