【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【３問目】

こんにちは！サトシ（@satoshi365_blog）です！

この記事では、「AtCoderに登録して最初に解くべき１０問（AtCoder Beginners Selection）」の３問目「Shift only」をめちゃくちゃ分かりやすく解説していきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

それでは、「Shift only」の解説をしていきます！

【競プロ】最初に解くべき過去問１０問をPythonで分かりやすく解説します！【AtCoder】こんにちは！サトシ（@satoshi365_blog）です！この記事では、「競技プログラミング（AtCoder）に登録し...

タップできる目次

３問目「Shift only」で身につくスキル
３問目「Shift only」の解説
まとめ

３問目「Shift only」で身につくスキル

この問題では、こんなスキルが身につきます。

身につくスキル

ブール型
代入演算子の使い方
比較演算子の使い方
while の使い方
for の使い方
breakの使い方
リスト内包表記の使い方
list() の使い方
if の使い方

先に、これがどのようなスキルなのかを説明します。

ブール型

ブール型とは、○ と × のことです。
○ のことを True、× のことを False と書きます。

これから説明する、比較演算子や、while、for で使います。

代入演算子の使い方

代入演算子を使うと、計算を短く書けます。

例えば、代入演算子を使わないで a を 2 倍するには、このように書かないといけません。

a = a * 2

でも、代入演算子を使うと、このように書けます。

a *= 2

他にも、このような代入演算子があります。

a += 2	a = a + 2
a -= 2	a = a – 2
a /= 2	a = a / 2
a %= 2	a = a % 2

他にもたくさんの比較演算子があるので、調べてみてください＾＾

比較演算子の使い方

比較演算子を使うと、文字列や数値を比較できます。

例えば、2 > 1 のように正しい時には、Trueを出力します。
1 > 2 のように正しくない時には、False を出力します。

print(2 > 1) #True と出力されます
print(1 > 2) #False と出力されます

他にも、このような比較演算子があります。

a == b	a が b と同じ
a != b	a が b と同じじゃない
a >= b	a が b 以上
a <= b	a が b 以下

他にもたくさんの比較演算子があるので、調べてみてください＾＾

if の使い方

実は、１問目に使った if にもブール型を使っています。

「もし a が 10 だったら Yes を出力する」には、このように書くと言いました。

if a == 10:
  print('Yes')

実は、if は「if のあとが True か Falseか」を見ているのです。
※もし a が 10 であれば、a == 10 が True になります。

つまり、こう書けば絶対に if の中身が実行されるプログラムになります。

if True:
  print('Yes')

また、実はリストも True として使えます。
他にも True や False の代わりとして使えるものがあるので、書いておきます。

[1, 2, 3]	True
[]	False
‘123’	True
”	False

while の使い方

while を使うと、同じ処理を繰り返すことができます。

例えば、このように書くと、’Hello’ と５回出力できます。

i = 0
while i < 5:
  print('Hello')
  i += 1

このプログラムがどのように動くのか、説明していきます。

i に 0 を代入
i < 5 が True だから while の中に入る
‘Hello’ と出力する
i に 1 を足す
while i < 5: に戻る
i < 5 が True だから while の中に入る
…（これを i = 5 になるまで繰り返す）
i < 5 がFalseだから、while の中に入らずに終わる

i < 5 が正しい間、つまり True である間、動き続けます。

なので、「while True:」と書くと、永遠に繰り返すことができます。

for の使い方

for を使うと、同じ処理を繰り返すことができます。

例えば、このように書くと、’Hello’ と５回出力できます。

for i in range(5):
  print('Hello')

このプログラムがどのように動くのか、説明していきます。

i に 0 を代入
‘Hello’ と出力する
for i in range(5): に戻る
i に 1 を代入
…（これを、i = 4 になるまで繰り返す）

※range(5) では、０から４の range型のデータを作ります。

とりあえずは「for i in range(5):」と書くと、５回繰り返せると覚えておきましょう。

また、for は range() だけじゃなくて、リストにも使えます。

例えば、このように書くと、「1」、「3」、「1」、「7」と出力できます。

for i in [1, 3, 1, 7]:
  print(i)

# 1 と出力
# 3 と出力
# 1 と出力
# 7 と出力

break の使い方

break を使うと、for や while の途中で抜け出すことができます。

例えば、このように使います。

i = 0
while True:
  if i = 5:
    break
  print('Hello')
  i += 1

この例では、’Hello’ と５回出力されます。

「if i = 5:」で、i が５だった時に、「break」を使って while から抜け出しています。

リスト内包表記の使い方

リスト内包表記を使うと、リストを短いプログラムで書けます。

例えば、[0, 2, 4, 6, 8] というリストを作るには、このように書きます。

list = [i * 2 for i in range(5)]

このプログラムがどのように動くのか、説明していきます。

i に 0 を代入
i * 2 をリストに入れる
for i in range(5): に戻る
i に 1 を代入
i * 2 をリストに入れる
…（これを、i = 4 になるまで繰り返す）

また、リスト内包表記は、if を使うこともできます。

例えば、２で割れる数だけをリストにしたいときは、このように書きます。

list = [i for i in range(10) if (i % 2) == 0]   #[0, 2, 4, 6, 8]

list() の使い方

list() を使うと、リスト型でないデータをリスト型にすることができます。

例えば、’test’ を文字列にするには、このように書きます。

print(list('test'))   #['t', 'e', 's', 't'] と出力します

今回の問題「Shift only」では、map 型をリスト型に変えます。

print(list(map(int, ['1', '2', '3'])))   #[1, 2, 3] と出力します

３問目「Shift only」の解説

この順番で解説していきます。

問題文
入力例と出力例
解答例
解説

それでは見ていきましょう。

問題文

問題文
黒板に N個の正の整数 A₁, …, A_N が書かれています。
すぬけ君は、黒板に書かれている整数がすべて偶数であるとき、次の操作を行うことができます。

・黒板に書かれている整数すべてを、2 で割ったものに置き換える。

すぬけ君は最大で何回操作を行うことができるか求めてください。

制約
・1 ≤ N ≤ 200
・1 ≤ A_i ≤ 10⁹

入力
入力は以下の形式で標準入力から与えられる。

N
A₁A₂ … A_N

出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ。

ABC081B – Shift onlyより引用

入力例と出力例

入力例

3
4 8 12

出力例

３つの数を２で２回割れるから、答えは２になります。

１回目は「２、４、６」、２回目は「１、２、３」です。
１と３は割れないから、ここで終わりということです。

解答例

n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
  if [i for i in a if i % 2 == 1]:
    break
  a = [i/2 for i in a]
  ans += 1
print(ans)

解説

やっていることは簡単なのですが、「綺麗にプログラムする」となると難しいです。

「全ての数を２で割る」ことを while で繰り返して、割れない数ができたときに break するように書いています。

では、コードを詳しく解説していきます。

N を受け取ります。

n = int(input())

そして、全ての数をリストにして a に入れます。

a = list(map(int, input().split()))

全ての数を２で何回割ったかを数えるために、ans を作っておきます。

ans = 0

ここから、繰り返しに入ります。
while True: と書いているので、if の中の break が実行されるまで繰り返します。

while True:
  if [i for i in a if i % 2 == 1]:
    break
  a = [i/2 for i in a]
  ans += 1

この while の中を詳しく見ていきます。

まずは、全ての数が 2 で割れるかを確かめます。

  if [i for i in a if i % 2 == 1]:
    break

[i for i in a if i % 2 == 1] と書くと、「割ると１余る数字」だけがリストになります。例えば、[1, 5] のようになるということです。

そして、if はリストに中身が１つでもあれば True と判断するので、break することになります。

つまり、「割ると１余る数字」があれば、ここで while から抜ける、ということです。

このプログラムが動いているということは、全ての数字が２で割れるということです。
なので、全ての数字を２で割っていきます。

a = [i/2 for i in a]

全ての数字を２で割ったので、ans（何回全ての数を２で割ったか）に１を足します。

ans += 1

以上を、全ての数が２で割れなくなるまで繰り返します。

最後に、ans を出力します。

print(ans)

まとめとして、もう一度プログラムを確認してみましょう。

n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
  if [i for i in a if i % 2 == 1]:
    break
  a = [i/2 for i in a]
  ans += 1
print(ans)

これで、「全ての数を２で何回割れるか」を求めることができました。