AtCoder ABC 074 B – Collecting Balls (Easy Version) Python解説

スポンサーリンク

Collecting Balls (Easy Version)

xy 平面上に N 個のボールがあります。このうち i 番目のボールの位置は (x_i, i)です。
したがって、N 本の直線 y = 1y = 2y = N の上にそれぞれ 1 個ずつボールがあることになります。

すぬけ君は、これらのボールを回収するために、タイプ A, B のロボットを N 台ずつ用意しました。 
さらに、タイプ A のロボットのうち i 台目のものを位置 (0, i) に、タイプ B のロボットのうち i 台目のものを位置 (K, i) に設置しました。

 したがって、N 本の直線 y = 1y = 2y = N の上にそれぞれ 1 台のタイプ A のロボットと、1 台のタイプ B のロボットが設置されたことになります。

それぞれのタイプのロボットは起動されると以下のように動作します。

タイプ A のロボットは、位置 (0, a) で起動されると、直線 y = a 上にあるボールの位置まで移動し、ボールを回収してもとの位置 (0, a) に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。

タイプ B のロボットは、位置 (K, b) で起動されると、直線 y = b 上にあるボールの位置まで移動し、ボールを回収してもとの位置 (K, b) に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。

これら 2N 台のロボットのうちいくつかを起動してボールをすべて回収するとき、ロボットの移動距離の総和として考えられる値のうち最小のものを求めてください。

AtCoder Beginner Contest 074 「Collecting Balls (Easy Version)」

問題文を図に起こすと下記のようになるはず。

#入力例
1     #ボールの数
10    #Bのロボットの位置
2     #ボールの位置

oをボールとすると
(Aのロボットの位置) 0 -o------- 10 (Bのロボットの位置) 

ロボットAとロボットBのボールに近い方を起動し、移動距離(往復)を求める。上記の図だと、ボールの位置2に対してロボットAの位置が近く、移動距離はボールの位置までの移動と、もとの位置に戻る移動で合計4になります。

そしてこれがボールの数N回繰り返されるという問題です。問題の趣旨さえわかればプログラム自体はそんなに難しくはなさそうです。

n = int(input())
k = int(input())
x = list(map(int, input().split()))

sum = 0

for i in range(n):
    sum += min(x[i], k - x[i]) * 2
    
print(sum)

入力を受け取ったらfor文でボールの個数N回までループを回します。
そして、min関数でロボットAとボールの距離、ロボットBとボールの距離の小さい方を求め、これを往復分なので2倍しています。最後に移動距離の総和sumを出力して完了です。