ABC257 D: Jumping Takahashi2 サンプルコード（Python）

解説を見てACしたので投稿。解説以上の情報は無いので、サンプルコードとしています。

方針

答えXを決め打って制約を満たすかを判定し、制約の範囲を二分探索する。 ある頂点から別の頂点へのパスがあるかは、ワーシャルフロイド法で判定できる。

Code

from itertools import product


def binsearch_int(s, e, f):
    c_min = s
    c_max = e
    while c_min != c_max:
        p = (c_min + c_max + 1) // 2
        result = f(p)
        if result:
            c_min = p
        else:
            c_max = p - 1
    return c_min

def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def f(S):
    edges = [[None for j in range(N)] for i in range(N)]
    for i, j in product(range(N), range(N)):
        dist_ij = dist((nodes[i][0], nodes[i][1]), (nodes[j][0], nodes[j][1]))
        if dist_ij <= S * nodes[i][2]:
            edges[i][j] = 1
    # Use WF
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if edges[i][k] and edges[k][j]:
                    edges[i][j] = 1
    for i in range(N):
        for j in range(N):
            if edges[i][j] is None:
                break
        else: return False
    else: return True

N = int(input())
nodes = []
for _ in range(N):
    nodes.append(tuple(int(i) for i in input().split()))

print(binsearch_int(0, 4 * 10 ** 9 + 1, f) + 1)

その他コメント

• ワーシャルフロイドを使っている部分では、距離は必要ないのでパスが存在するなら1、無いならNoneとしている。このようにしてもワーシャルフロイドは問題なく動作する。
• 二分探索の最大値は、4 * 10 ** 9 + 1としておく必要がある。（最初2 * 10 ** 9 + 1としていてWAした。）ちなみに適当に10 ** 10とかしておいたらTLEした。世知辛い。
• 二分探索自体はコンテスト中でも思いついていたが、探索範囲10 ** 9とかだと間に合わないと勘違いしていた。logNってめっちゃ短いんですね。。。
• 二分探索部分は再利用できるように書いたので、またどこかで使う機会はありそう。