AtCoderログ：0114 - ABC 094 B

問題

問題文

$N+1$ 個のマスが左右に一列に並んでいます．これらのマスには，左のマスから順に $0,1,...,N$ の番号が付けられています．
あなたは，最初マス $X$ にいます． 隣り合うマスの間は自由に移動することができ，マス $0$ またはマス $N$ にたどり着くとゴールすることができます．ただし，$i=1,2,...,M$ について，マス $A_i$ には料金所があり，そのためマス $A_i$ に移動してくる際には $1$ のコストがかかります．なお，マス $0$，マス $X$，マス $N$ には料金所がないことが保証されます．
ゴールするまでにかかるコストの最小値を求めてください．

制約

・$1 \le N \le 100$
・$1 \le M \le 100$
・$1 \le X \le N−1$
・$1 \le A_1<A_2< \ldots <A_M \le N−1$
・$A_i \ne X$
・入力はすべて整数

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

• AtCoder Problems Boot camp for beginners Easy 100 [#019]

回答

回答1 (AC)

マス $0$ に移動してゴールする場合のコスト(cl)とマス $N+1$ に移動してゴールする場合のコスト(cr)をそれぞれ計算し、小さい方を答えとして出力すれば良いでしょう。コードは以下のようになりました。

abc094b-1.cpp

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

  int i = 0, cl = 0;
  while ( a.at(i)<x ) {
    cl += 1;
    i += 1;
  }

  int cr = 0;
  while ( i<m && a.at(i)<n ) {
    cr += 1;
    i += 1;
  }

  cout << min(cl,cr) << endl;
}

回答2 (AC)

累積和を使った別解です。配列 s[0]-s[N+1] において、料金所があれば1、なければ0を代入し、左から累積和を計算することで、答えが簡単に求められます。コードは以下のようになりました。

abc094b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, m, x;
  cin >> n >> m >> x;

  int t;
  vector<int> s(n,0);
  for ( int i=0; i<m; i++ ) {
    cin >> t;
    s.at(t) = 1;
  }

  for ( int i=1; i<n; i++ ) {
    s.at(i) += s.at(i-1);
  }

  cout << min(s.at(x),m-s.at(x)) << endl;
}

調べたこと

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

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

リンク

前後の記事

• 前の記事 → AtCoderログ：0113 - ABC 122 B
• 次の記事 → AtCoderログ：0115 - ABC 116 B