AtCoderログ：0025 - ABC 102 B

問題：ABC 102 B - Maximum Difference

問題文

長さ $N$ の整数列 $A$ が与えられます。$A$ の（添字の）異なる $2$ 要素の差の絶対値の最大値を求めてください。

制約

・$2 \le N \le 100$
・$1 \le A_i \le 10^9$
・入力はすべて整数である。

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

• AtCoder に登録したら次にやること (第03問類題)

回答1 (AC)

整数列 a() を受け取った後、添え字の異なる全ての $2$ 要素の差の絶対値 abs(a.at(i)-a.at(j)) を計算し、その中から最大値を求めれば良いでしょう。
コードは以下のようになりました。

abc102b-1.cpp

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

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }

  int dmax = -1;
  for ( int i=0; i<n; i++ ){
    for ( int j=0; j<n; j++ ) {
      if ( i!=j ) {
        dmax = max( dmax, abs(a.at(i)-a.at(j)) );
      }
   }
  }

  cout << dmax << endl;
}

回答2 (AC)

回答1では配列の添字 $i,j$ をともに $1$ から $N$ まで(コードでは 0 から n-1 まで)変化させましたが、$|A_i-A_j|=|A_j-A_i|$ という対称性があるので、片方だけ計算すれば十分です。従って、$i<j$ という条件を設定しても問題ありません。
このアイディアによるコードは以下となります。

abc102b-2.cpp

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

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }

  int dmax = -1;
  for ( int i=0; i<n; i++ ){
    for ( int j=i+1; j<n; j++ ) {
      dmax = max( dmax, abs(a.at(i)-a.at(j)) );
   }
  }

  cout << dmax << endl;
}

計算量(絶対値を計算する回数)を調べてみると、回答1は $(N-1)^2=N^2-2N+1$回、回答2では$(N-1)+(N-2)+\cdots+1=\frac{(N-1)N}{2}=\frac{1}{2}N^2-\frac{1}{2}N$ 回となっており、どちらも $O(N^2)$ となっています。この問題では制約として $N \le 100$ となっているので、計算量的には問題ありません。

回答3 (AC)

AtCoder に登録したら次にやること 第03問 のコメントに「できれば for 文を 1 回だけ使って解いてみましょう」と描かれているので、それに挑戦します。回答1,2 は for 文を 3 回使用しているので、異なるアプローチが必要です。

そもそも「差の絶対値が最大」になるのは、数列の中で「絶対値が最大の値から絶対値が最小の値を引いたとき」ですが、この問題では数列の値はすべて正なので、これは「最大の値から最小の値を引いたとき」と言い換えることができます。つまりこの問題は、数列の中から最大値と最小値を求める問題なのです。このアイディアを使うと、以下のようなコードになりました。条件通り、for 文の使用は1回になっています。

abc102b-3.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, a, imin = INT_MAX, imax = -1;
  cin >> n;
  for (int i=0; i<n; i++) {
    cin >> a;
    imin = min( imin, a );
    imax = max( imax, a );
  }

  cout << imax-imin << endl;
}

調べたこと

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

回答3と同じ方針でした。今回のように最大値や最小値のとり得る値が決まっている場合には、初期値をとり得る値にするのが良いのですね。

学んだこと

• 最大値・最小値を求めるときの初期値の設定方法

リンク

• 前の記事 → AtCoderログ：0024 - ABC 210 C