Pythonで解くAtCoder(エイシング プログラミング コンテスト 2020:A)
こんにちは、クルトンです！
この記事では
AtCoderの「エイシング プログラミング コンテスト 2020」のA問題をPythonを使って解説します。
問題のリンクを載せておきます。
この問題を解くのに必要な知識
- 1行に複数の数字の入力があるときの受け取り方
- for文
まず1行に複数の数字の入力があるときの受け取り方を説明します。
1行に複数の数字の入力があるときの受け取り方
map(int,input().split())
を使います。
今回の場合は
L, R, d = map(int,input().split())
とすることで入力を受け取れます。
簡単な解法
数えるための変数cntを用意し、L以上R以下の整数をfor文ですべて調べて、dの倍数であればcntを1増やすという方法です。
ここでrange関数の使い方を軽く復習しておきましょう。
range関数の使い方
range関数は引数の数によって働きが変わります。
今回は引数が二つの時について解説します。
引数が二つの時
コード
list(range(4, 7)) # range(a, b)
出力結果
[4,5,6]
このように、range関数の中に二つの数字a, bを入れると、aからb-1までの数字が連番が生成されます。(aからbまでではないので注意！)
これをfor文と組み合わせると
コード
for i in range(4, 7): print(i)
出力結果
4 5 6
というように、ひとつずつ要素を取り出すことができます。
なのでrange(L, R+1)とfor文で、LからRまでの要素を取り出し、一つずつ倍数判定をすることで答えを求めることができます。
以下にサンプルコードを載せておきます
少し難しい解法
1以上N以下の整数のうちdの倍数であるものの個数は、Nをdで割った商に等しいです。…①
証明
1以上N以下の整数のうちdの倍数であるものの個数をk個とする。
このとき
d, 2d, 3d, ..., kd
が1からNまでの中にあるので
kd ≤ N < (k+1)d
となる。
上の式を変換すると
N/d - 1 < k ≤ N/d
となる。よってkはNをdで割った商に等しい。//
また、「L以上R以下の整数のうち、dの倍数であるようなものの個数」は、「1以上R以下の整数のうちdの倍数であるようなものの個数」から「1以上L-1以下の整数のうちdの倍数であるようなものの個数」に等しいので、
①を用いて
答えは
[R/d] - [(L-1)/d]
となります。（"[]"はガウス記号という少数以下を切り捨てる記号です。）
以下にサンプルコードを載せておきます
まとめ
今回は
- for文とrange関数を使って調べる
- 1以上N以下の整数のうちdの倍数であるものの個数は、Nをdで割った商に等しいことを利用する
という問題でした。
もし入力の受け取り方が分からなかった人は、それだけでもいいので覚えておきましょう！
ではまたお会いしましょう！さようなら～
