AtCoderログ：0094 - ABC 074 B

問題

問題文

$xy$ 平面上に $N$ 個のボールがあります。このうち $i$ 番目のボールの位置は $(x_i,i)$ です。したがって、$N$ 本の直線 $y=1, y=2, ..., y=N$ の上にそれぞれ 1 個ずつボールがあることになります。
すぬけ君は、これらのボールを回収するために、タイプ A, B のロボットを $N$ 台ずつ用意しました。 さらに、タイプ A のロボットのうち $i$ 台目のものを位置 $(0,i)$ に、タイプ B のロボットのうち $i$ 台目のものを位置 $(K,i)$ に設置しました。 したがって、$N$ 本の直線 $y=1, y=2, ..., y=N$ の上にそれぞれ $1$ 台のタイプ A のロボットと、$1$ 台のタイプ B のロボットが設置されたことになります。
それぞれのタイプのロボットは起動されると以下のように動作します。
・タイプ A のロボットは、位置 $(0,a)$ で起動されると、直線 $y=a$ 上にあるボールの位置まで移動し、ボールを回収してもとの位置 $(0,a)$ に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。
・タイプ B のロボットは、位置 $(K,b)$ で起動されると、直線 $y=b$ 上にあるボールの位置まで移動し、ボールを回収してもとの位置 $(K,b)$ に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。
これら $2N$ 台のロボットのうちいくつかを起動してボールをすべて回収するとき、ロボットの移動距離の総和として考えられる値のうち最小のものを求めてください。

制約

・$1 \le N \le 100$
・$1 \le K \le 100$
・$0<x_i<K$
・入力値はすべて整数である。

収録されている問題セット

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #009

回答

回答1 (AC)

問題文が長く設定が少し複雑ですが、状況がのみこめればコーディングは単純です。要は、直線の上にボールが置いてあり、両端に置かれたロボットの近い方が回収する、ということです。この直線が $N$ 本あるので、その最短距離の合計を求めることになります。コードは以下のようになりました。ロボットはボールを回収した後、もとの位置に戻る必要があることに注意が必要です。

abc074b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
 
  vector<int> x(n);
  for ( int i=0; i<n; i++ ) {
    cin >> x.at(i);
  }

  int dmin = 0;
  for ( int i=0; i<n; i++ ) {
    dmin += min(2*x.at(i),2*(k-x.at(i)));
  }
  
  cout << dmin << endl;
}

回答1 (AC)

回答1を少しだけ改良します。回答1のコードを見返すと、vector 型変数 x は値を１回参照するだけなので、わざわざ保持する必要があります。そこで cin で読み込みした後に最短距離を調べることで、vector 型変数の使用は不要となります。コードは以下のようになりました。

abc074b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
 
  int x, dmin = 0;
  for ( int i=0; i<n; i++ ) {
    cin >> x;
      dmin = min(2*x,2*(k-x));
  }
  
  cout << dmin << endl;
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0093 - ABC 086 B
• 次の記事 → AtCoderログ：0095 - ABC 160 C