ABC374 D問題の解説（Python）

はじめに

この記事では、ABC374のD問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC374　D – Laser Marking

問題

問題

xy 平面に対し、レーザを照射しながら線分を印字する印字機があります。

• 印字開始時、レーザ照射位置は座標 (0, 0) にある。
• 線分を印字する際は、以下の流れに従う。
  • まず、レーザ照射位置を線分の端点のうちどちらか1つに移動させる。
  • その後、レーザ照射位置のある端点からもう一方の端点まで、レーザを照射しながらレーザ照射位置を一直線に移動させる。
• レーザを照射していない時、レーザ照射位置は1秒あたり速度Sで任意の方向に移動できる。
• レーザを照射している時、レーザ照射位置は1秒あたり速度Tで印字中の線分に沿って移動できる。

この印字機で N 本の線分を印字したいです。
そのうち \(i\) 本目の線分は、座標 \((A_i, B_i)\)と座標 \((C_i, D_i)\) を結びます。

全ての線分を印字完了するまでにかかる最小の時間は何秒かを求める問題です。

制約

• \(1 \leqq N \leqq 6 \)
• \(1 \leqq T \leqq S \leqq 1000\)
• \(-1000 \leqq A_i, B_i, C_i, D_i \leqq 1000 \)
• \((A_i, B_i)≠ (C_i, D_i)\)

思考の筋道

Nが6以下なので、どの順番で線分を印字するか全通り試すことができます。また、それぞれの線分について、どちらの端点から開始するかの選択もありますが、それも含めて全通り試すことができます。

あとは実装していくのみですが、実装がやや大変です。

順列全探索とbit全探索を組み合わせましょう。

• 順列全探索による繰り返し処理で、6つの線分の印字する順番を指定
  • bit全探索による繰り返し処理で、各線分の印字の向きを指定
    • 各線分の繰り返し処理
      • 今いる点（start）から次の線分の開始点（goal）まで速度Sで移動する
      • 線分内を速度Tで移動する
      • 線分の終了点を新たなstartとする

求めた時間がこれまでの最小値より小さくなるか、調べていけばOKです！

コード

from itertools import permutations
import math

def calTime(p1, p2, speed):
    return math.hypot(p2[0] - p1[0], p2[1] - p1[1]) / speed

N, S, T = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]

min = 2 ** 31 - 1

for order in permutations(range(N)):
  for i in range(2 ** N):
    muki = [(i >> j) & 1 for j in range(N)]
    time = 0
    start = [0, 0]
    for k in range(N):
      if muki[k] == 0:
        goal = [l[order[k]][0], l[order[k]][1]]
      else:
        goal = [l[order[k]][2], l[order[k]][3]]
      time += calTime(start, goal, S)
      time += calTime([l[order[k]][0], l[order[k]][1]], [l[order[k]][2], l[order[k]][3]], T)
      if muki[k] == 0:
        start = [l[order[k]][2], l[order[k]][3]]
      else:
        start = [l[order[k]][0], l[order[k]][1]]
    if time < min:
      min = time

print(min)

以上、ABC374のD問題の解説でした！

では、またね。

リンク