プログラミング

【競プロ精進日記】ABS編<4>

本記事は管理人が競技プログラミングを始めたため,その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。記事目次は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

AtCoder Beginners Selection

AtCoder Beginners Selectionの問題を1から解いていくシリーズです。使用言語はc++とpythonです。今回はABC081B – Shift onlyです。

c++

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int N = 0;
  cin >> N;
 // 結果を格納する変数
  int ans = 0;
 // while文を抜け出すフラグ
  bool judge;
  vector<int> A(N);
  judge = true;
  rep(i, N){
    cin >> A[i];
    if (A[i] % 2 == 1) judge=false;
  }
  if (judge == false){
    cout << 0 << endl;
    return 0;
  }
  else{
    while(true){
      ans++;
      rep(i, N){
        A[i] /= 2;
        if (A[i] % 2 == 1) judge=false;
      }
      if (judge==false) break;
    }
    cout << ans << endl;
    return 0;
  }

}

少しずつ難しくなってきました。今回はfor文を用いた全探索をしてみようという問題です。while文を利用するため,続行するか否かを表すjudgeフラグを用意してbreakする条件分岐を用意してあげる必要があります。

また,最初に全ての要素が割り切れるかどうかの判断をしてあげることで,Aの全ての要素が2で割り切れることは確定していますので,while文の中でansのインクリメント(+1)をwhile直後に置くことができます。

python

N = int(input())
A = list(map(int, input().split()))

judge = True
ans = 0

# 見通しをよくするために関数定義
def judge_div(A):
  if True in [A[i]%2==1 for i in range(len(A))]:
    return False
  else:
    return True

# もし奇数があればダメ
if judge_div(A)==False:
  print(ans)
  exit()

while judge==True:
 # 最初に全て偶数であることがかくてしているのでとりあえずansに1を加えられる
  ans += 1
  A = [A[i]/2 for i in range(N)]
  judge = judge_div(A)
  if judge==False:
    break

print(ans)

pythonでも方針は同様です。

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です