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ってめっちゃ短いんですね。。。
- 二分探索部分は再利用できるように書いたので、またどこかで使う機会はありそう。