AtCoderログ：0019 - ABC 081 B

問題：ABC 081 B - Shift only (AtCoder に登録したら次にやること 第03問)

問題文

黒板に $N$ 個の正の整数 $A_1,\ldots,A_N$ が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
・黒板に書かれている整数すべてを，$2$ で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．

制約

・$1 \le N \le 200$
・$1 \le A_i \le 10^9$

回答1 (AC)

まず整数型の配列 $a$ に整数列を受け取ります。そして整数列の全ての値が偶数であるかをチェックし、偶数ならば $2$ で割った値に置き換える、という操作を繰り返しました。割れる回数は変数 division に保存しています。整数列の全ての値が偶数であるかは変数 odd によって確認し、値が false ならば全て偶数、値が true ならば奇数が混じっていることをあらわすようにしています。

abc081b-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 division = 0, odd = false;
  while ( odd==false ){
    for ( int i=0; i<n; i++ ) {
      if ( a.at(i)%2==1 ) {  
        odd = true;
      }
    }
    if ( odd==false ){
      for ( int i=0; i<n; i++ ) {
        a.at(i) /= 2;
      }
      division += 1;
    }
  }

  cout << division << endl;
}

回答2 (AC)

回答1には無駄な for 文が多いので、2で割れるかを確認するループと実際に割るループをまたおめ、コードを簡略化してみました。

abc081b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, odd = false;
  cin >> n;
  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
    if ( a.at(i)%2==1 ) {  
      odd = true;
    }
  }

  int division = 0;
  while ( odd==false ){
    for ( int i=0; i<n; i++ ) {
      a.at(i) /= 2;
      if ( a.at(i)%2==1 ) {  
        odd = true;
      }
    }
    division += 1;
  }

  cout << division << endl;
}

回答3 (AC)

操作の意味を考えると、問題で聞かれているのは各整数が $2$ で割り切れる回数の最小値であることに気づきます。このアイディアをコーディングして以下のようになりました。

abc081b-3.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 division, dmin = INT_MAX;
  for ( int i=0; i<n; i++ ) {
    division = 0;
    while ( a.at(i)%2==0 ) {
      division += 1;
      a.at(i)  /= 2;
    }
    if ( division<dmin ) {
      dmin = division;
    }
  }

  cout << dmin << endl;
}

回答4 (AC)

回答3をながめると、整数の配列 a の値を保持する必要がないことに気づきます。つまり、各整数を受け取った時点で $2$ で割り切れる回数を求められれば十分です。コードは以下のように簡略化できました。

abc081b-4.cpp

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

  int a, division, dmin = INT_MAX;
  for ( int i=0; i<n; i++ ) {
    cin >> a;
    division = 0;
    while ( a%2==0 ) {
      division += 1;
      a        /= 2;
    }
    if ( division<dmin ) {
      dmin = division;
    }
  }

  cout << dmin << endl;
}

調べたこと

Atcoderに登録したら次にやること

回答1,2が紹介されていました。

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

回答1,2と回答3,4がそれぞれ紹介されていました。
ソースコードをながめたところ、最小値を求める関数 min が標準関数にあることを知りました。この関数を使えば dmin=min(dmin,*) と書けるので、if 文が不要となり見やすくなりますね。

学んだこと

• C++の標準ライブラリ (min, max)

リンク

• 前の記事 → AtCoderログ：0018 - ABC 082 B
• 次の記事 → AtCoderログ：0020 - ABC 068 B