競技プログラミング

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

プログラミング

こんにちは!サトシ(@satoshi365_blog)です!

 

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

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

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

 

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

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

3問目「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 の使い方

実は、1問目に使った 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’ と5回出力できます。

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

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

  1. i に 0 を代入
  2. i < 5 が True だから while の中に入る
  3. ‘Hello’ と出力する
  4. i に 1 を足す
  5. while i < 5: に戻る
  6. i < 5 が True だから while の中に入る
  7. …(これを i = 5 になるまで繰り返す)
  8. i < 5 がFalseだから、while の中に入らずに終わる

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

 

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

 

for の使い方

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

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

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

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

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

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

とりあえずは「for i in range(5):」と書くと、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’ と5回出力されます。

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

 

リスト内包表記の使い方

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

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

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

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

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

 

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

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

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] と出力します

 

3問目「Shift only」の解説

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

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

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

 

問題文

 

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

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

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

制約
・1 ≤ N ≤ 200
・1 ≤ Ai ≤ 109

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

N
AA2 … AN

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

ABC081B – Shift onlyより引用

 

入力例と出力例

入力例

3
4 8 12

出力例

2

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

1回目は「2、4、6」、2回目は「1、2、3」です。
1と3は割れないから、ここで終わりということです。

 

解答例

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)

解説

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

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

 

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

 

N を受け取ります。

n = int(input())

 

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

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

 

全ての数を2で何回割ったかを数えるために、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余る数字」だけがリストになります。例えば、[1, 5] のようになるということです。

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

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

 

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

a = [i/2 for i in a]

 

全ての数字を2で割ったので、ans(何回全ての数を2で割ったか)に1を足します。

ans += 1

 

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

 

最後に、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)

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

まとめ

もし分からない点などありましたら、気軽にTwitterなどでご質問ください^^

少しでも参考になれば嬉しいです!

COMMENT

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