Python AtCoder入門 第４講 ループ - forとwhile

Python AtCoder入門 第4講 ループ — for と while 第3講までで、入力を受け取り、計算し、条件で分岐して、出力できるようになりました。 しかしまだ、プログラムは上から下へ1回通り抜けるだけです。 1

今回のテーマ ここで登場するのが、 ループ です。 同じ処理を何度でも繰り返せるようになると、100個でも10万個でもデータをまとめて扱えます。 2

ループは最大の武器 コンピュータの最大の武器は、圧倒的な計算スピードです。 その武器を実際に振るうための道具が、 ループ です。 A問題からB問題へ進む上で、最大の関門であり最大の武器でもあります。 3

この講のゴール この講では、次を身につけます。 for と range リストに対するループ enumerate zip while break カウント・フラグ・二重ループ 4

コードファイル名の方針 この講でも、コード例ごとにファイル名を付けます。 例： range_basic.py sum_1_to_n.py enumerate_max.py while_halve.py answer_4_1.py 手元では同じ名前で保存して実行してください。 5

4-1 forループとrange 決まった回数だけ繰り返したいときは、 for range() を組み合わせます。 6

決まった回数だけ繰り返す 同じ処理を N 回繰り返したいときは、次の形です。 for i in range(N): 繰り返したい処理 range(N) は、N個ぶんの値を作ります。 7

range_basic.py for i in range(3): print(i) 出力： 0 1 2 range(3) は 0, 1, 2 です。 8

range(3) は3を含まない 重要な点です。 range(3) は、 0, 1, 2 です。 3 は含みません。 9

「3まで」ではなく「3個ぶん」 range(3) は、 3まで ではありません。 3個ぶん です。 初心者が必ず一度は間違えるところです。 10

ループ変数は0から始まる for i in range(3): print(i) の i は、 0 1 2 と変化します。 Pythonでは、番号を0から数えるのが基本です。 11

rangeの3つの形 書き方 range(n) range(a, b) range(a, b, step) 意味 0からn-1 aからb-1 step刻み 例 range(5) range(2, 5) range(0,10,3) 値 0,1,2,3,4 2,3,4 0,3,6,9 12

終わりの値を含まない どの range でも共通して、 終わりの値を含みません。 たとえば、1からNまで回したいなら、 range(1, N + 1) です。 13

+1を忘れない 1からNまで回すときは、 range(1, N + 1) です。 range(1, N) だと、Nを含みません。 この + 1 の忘れは頻出ミスです。 14

ループ変数を使う ループ変数は、その回の値を持っています。 for i in range(1, 4): print(i * 10) 出力： 10 20 30 15

ループ変数を使わない ただN回繰り返したいだけなら、 for _ in range(N): A = int(input()) のように _ を使うことがあります。 16

_ の意味 は、 この変数は使いません という意思表示です。 値を使わず、回数だけ必要なときに使います。 _ 17

sum_1_to_n.py # Read an integer N = int(input()) # Sum up 1 to N total = 0 for i in range(1, N + 1): total += i print(total) 18

sum_1_to_n.py の実行例 入力例： 10 出力例： 55 1 + 2 + ... + 10 = 55 です。 19

入れ物はループの外で初期化する 合計を求めるときは、 total = 0 をループの外に書きます。 中に書くと、毎回リセットされてしまいます。 20

bad_sum.py N = int(input()) for i in range(1, N + 1): total = 0 total += i print(total) これは間違いです。 total が毎回0に戻ってしまいます。 21

reverse_step.py N = 5 # Count down from N to 1 for i in range(N, 0, -1): print(i, end=" ") print() # Every third number from 0 to 9 for i in range(0, 10, 3): print(i, end=" ") print() 22

reverse_step.py の出力 5 4 3 2 1 0 3 6 9 逆順でも、終わりの値は含みません。 range(N, 0, -1) では、 0 は出力されません。 23

end=" " の使い方 print(i, end=" ") は、改行せずに空白を付けて出力します。 最後の、 print() で改行しています。 24

4-2 リストに対するループ 次は、リストの中身を順に処理します。 ここでは、 要素を直接走査する enumerate zip を扱います。 25

要素を直接走査する リストの中身を順に見たいとき、インデックスを経由する必要はありません。 A = [3, 1, 4, 1, 5] for x in A: print(x) 26

list_loop.py A = [3, 1, 4, 1, 5] for x in A: print(x) 出力： 3 1 4 1 5 要素が順番に x に入ります。 27

中身だけ使うなら直接回す 次のようにも書けます。 for i in range(len(A)): print(A[i]) しかし、中身だけ使うなら、 for x in A: print(x) のほうが短く、間違いも減ります。 28

list_sum_max.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Compute the sum total = 0 for x in A: total += x # Compute the maximum best = A[0] for x in A: if x > best: best = x print(total, best) 29

list_sum_max.py の実行例 入力例： 5 3 1 4 1 5 出力例： 14 5 合計は 14 、最大値は 5 です。 30

sumやmaxの中身を理解する 実際には、 sum(A) max(A) を使えば1行で済みます。 ただし、最初は中で何が起きているかを自分で書くと応用が利きます。 31

最大値を更新する型 最大値を求めるときは、 best = A[0] for x in A: if x > best: best = x の形です。 暫定の最大値を持ち、大きい値が来たら更新します。 32

best = A[0] の理由 best = 0 とすると、すべての要素が負の場合に壊れます。 最初の要素で初期化するほうが安全です。 best = A[0] 33

enumerate インデックスと中身の両方が必要なときは、 enumerate() を使います。 34

enumerate_basic.py A = ["apple", "banana", "cherry"] for i, x in enumerate(A): print(i, x) 出力： 0 apple 1 banana 2 cherry 35

enumerateの役割 for i, x in enumerate(A): では、 にインデックス x に中身 が入ります。 range(len(A)) より読みやすくなります。 i 36

1始まりにする AtCoderの問題文では、番号が1始まりで書かれることが多いです。 その場合は、 enumerate(A, 1) と書きます。 37

enumerate_max.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Find the position of the maximum value (1-indexed) best = A[0] position = 1 for i, x in enumerate(A, 1): if x > best: best = x position = i print(position, best) 38

enumerate_max.py の実行例 入力例： 5 3 1 4 1 5 出力例： 5 5 最大値 5 は、1始まりで5番目です。 39

値と位置を同時に更新する 最大値と位置を扱うときは、 best = x position = i を同じ if の中で更新します。 値と位置がずれないようにするためです。 40

zip 2つのリストを同時に回したいときは、 zip() を使います。 例： 名前のリスト 点数のリスト を対応させる場合です。 41

zip_basic.py names = ["Sato", "Suzuki", "Takahashi"] scores = [80, 95, 72] for name, score in zip(names, scores): print(name, score) 出力： Sato 80 Suzuki 95 Takahashi 72 42

zipのメリット インデックスを書かずに、対応する要素を同時に取り出せます。 for name, score in zip(names, scores): 添字のずれによるバグを減らせます。 43

長さが違う場合 に長さが違うリストを渡した場合は、 短いほうに合わせて止まります。 余った要素は無視されます。 zip() 44

zip_passed.py # Read the number of students N = int(input()) # Read names and scores names = input().split() scores = list(map(int, input().split())) # Print the name of every student who passed for name, score in zip(names, scores): if score >= 60: print(name) 45

zip_passed.py の実行例 入力例： 3 Sato Suzuki Takahashi 80 45 72 出力例： Sato Takahashi 60点以上の生徒だけを出力しています。 46

名前は文字列のまま 名前のリストは文字列なので、 names = input().split() で十分です。 map(int, ...) は付けません。 47

4-3 whileループ は、回数が先に決まっているときに使います。 一方、 条件が成り立つ間ずっと繰り返す ときは while を使います。 for 48

whileの基本形 while 条件: 条件が True の間、繰り返す処理 条件が True の間、ブロックの中を繰り返します。 49

whileを使う場面 たとえば、 Nが1になるまで2で割り続ける のような処理です。 何回で終わるか、事前にはわかりません。 50

終了条件の設計 を使うときは、必ず確認します。 ループの中で、条件がFalseに近づいているか？ 近づいていなければ、無限ループになります。 while 51

infinite_loop_bad.py # Dangerous example while N > 1: print(N) このコードでは、 N が変化しません。 そのため、永久に終わりません。 AtCoderではTLEになります。 52

while_good.py # Good example while N > 1: N //= 2 このコードでは、 N が毎回小さくなります。 条件 N > 1 が、いつか False になります。 53

whileを書くときの確認 を書いたら、 この変数はどこで変化するのか？ を確認してください。 無限ループを防ぐための大切な習慣です。 while 54

while_halve.py # Read an integer N = int(input()) # Halve N until it becomes 1, and count the steps count = 0 while N > 1: N //= 2 count += 1 print(count) 55

while_halve.py の実行例 入力例： 10 出力例： 3 10 → 5 → 2 → 1 と3回で1になります。 56

N //= 2 N //= 2 は、 N = N // 2 と同じ意味です。 第2講で学んだ省略記法です。 57

break と continue ループの流れを途中で変える命令があります。 break ：ループを即座に抜ける continue ：その回の残りを飛ばして、次の回へ進む 58

break は、 見つかったらもう調べなくていい という場面で使います。 最後まで回さずに済むので、無駄な計算を減らせます。 break 59

first_negative.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Find the position of the first negative value (1-indexed) answer = -1 for i, x in enumerate(A, 1): if x < 0: answer = i break print(answer) 60

first_negative.py の実行例 入力例： 5 3 1 -4 1 -5 出力例： 3 最初の負の数は、1始まりで3番目です。 61

breakしないとどうなるか を書かないと、 後ろにある負の数で answer が上書きされます。 この例では、5番目の -5 で上書きされ、答えが 5 になってしまいます。 break 62

見つからない場合も決めておく このコードでは、最初に、 answer = -1 としています。 負の数が1つもなければ、 -1 がそのまま出力されます。 63

continue は、 その回の残りを飛ばして、次の回へ進む 命令です。 条件を満たさないものをスキップしたいときに使えます。 continue 64

continue_example.py A = [3, -1, 4, -5, 9] for x in A: if x < 0: continue print(x) 出力： 3 4 9 負の数の回だけ、 print を飛ばしています。 65

4-4 ループの頻出パターン ここからは、AtCoderでよく使う型を3つ紹介します。 この3つで、B問題のかなりの部分がカバーできます。 1. カウントパターン 2. フラグパターン 3. 二重ループによるペア列挙 66

① カウントパターン 条件を満たす要素が何個あるかを数えます。 count = 0 for x in A: if 条件: count += 1 print(count) 67

カウントの考え方 ループの外で、 count = 0 を用意します。 条件を満たすたびに、 count += 1 します。 68

count_scores.py # Read N and the list of N scores N = int(input()) A = list(map(int, input().split())) # Count the scores that are 60 or above count = 0 for x in A: if x >= 60: count += 1 print(count) 69

count_scores.py の実行例 入力例： 6 80 45 72 60 30 91 出力例： 4 80 , 72 , 60 , 91 の4つです。 70

以上とより大きい 「60点以上」なら、 x >= 60 です。 「60点より大きい」なら、 x > 60 です。 この取り違えはWAの原因になります。 71

② フラグパターン 条件を満たすものが1つでも存在するかを判定します。 数えるのではなく、 あるかないか だけを知りたい場合です。 72

フラグの型 found = False for x in A: if 条件: found = True break if found: print("Yes") else: print("No") 73

フラグの考え方 最初は、 found = False にしておきます。 見つかったら、 found = True にして break します。 74

flag_search.py # Read N, the list of N integers, and the target value N = int(input()) A = list(map(int, input().split())) X = int(input()) # Check whether X exists in A found = False for a in A: if a == X: found = True break if found: print("Yes") else: print("No") 75

flag_search.py の実行例 入力例： 5 3 1 4 1 5 4 出力例： Yes 4 がリストの中にあるので Yes です。 76

③ 二重ループによるペア列挙 N個の中から2個選ぶ組み合わせをすべて調べるときは、 ループの中にループを書きます。 これを二重ループと呼びます。 77

ペア列挙の型 for i in range(N): for j in range(i + 1, N): # A[i] と A[j] のペアについて処理 この形は丸ごと覚えてください。 78

なぜ i + 1 から始めるのか 内側のループを、 range(i + 1, N) にすると、 i<j を満たす組だけ調べられます。 79

よくあるミス for j in range(N): にすると、同じ要素同士や同じペアを2回調べます。 for j in range(i, N): でも、 i == j が含まれます。 80

同じペアを2回数えない から始めることで、 同じ要素同士を避ける (A1, A2) と (A2, A1) を二重に数えない ことができます。 i + 1 81

count_pairs.py # Read N, the list of N integers, and the target sum N = int(input()) A = list(map(int, input().split())) K = int(input()) # Count the pairs whose sum equals K count = 0 for i in range(N): for j in range(i + 1, N): if A[i] + A[j] == K: count += 1 print(count) 82

count_pairs.py の実行例 入力例： 4 1 2 3 4 5 出力例： 2 (1, 4) と (2, 3) の2組です。 83

二重ループの注意点 二重ループは繰り返し回数が一気に増えます。 N = 100 ：約5000回 N = 100000 ：約50億回 50億回はまず間に合いません。 84

制約を確認する 二重ループを書く前に、 問題文の制約でNの上限を確認する 習慣をつけましょう。 A・B問題では、制約を見るだけで方針が見えることがあります。 85

章末まとめ 決まった回数の繰り返しは、 for i in range(N): です。 range は終わりの値を含みません。 86

章末まとめ：range は 0 から N-1 1からNまでは range(1, N + 1) 逆順は range(N, 0, -1) ループ変数を使わないときは _ range(N) 87

章末まとめ：入れ物 合計やカウントの入れ物は、ループの外で初期化します。 total = 0 count = 0 中で初期化すると、毎回リセットされます。 88

章末まとめ：リストのループ リストの中身だけ必要なら、 for x in A: インデックスも必要なら、 for i, x in enumerate(A): を使います。 89

章末まとめ：enumerateとzip 1始まりで番号を振りたいときは、 enumerate(A, 1) 2つのリストを同時に回すなら、 zip(A, B) です。 90

章末まとめ：while 回数が決まっていないときは、 while 条件: を使います。 条件が False に近づいているか、必ず確認してください。 91

章末まとめ：breakとcontinue ：ループを抜ける continue ：その回の残りを飛ばす break は、見つかったらもう調べなくてよい場面で便利です。 break 92

章末まとめ：頻出パターン 頻出パターンは3つです。 1. カウント： count += 1 2. フラグ： found = True して break 3. 二重ループ：内側は range(i + 1, N) 93

練習問題 4-1 3と5の倍数の和 整数 N が与えられます。 1以上N以下の整数のうち、 3の倍数または5の倍数 であるものの総和を出力してください。 94

練習問題 4-1：入力と出力 入力： N 入力例： 15 出力例： 60 対象は 3, 5, 6, 9, 10, 12, 15 です。 95

answer_4_1.py # Read an integer N = int(input()) # Sum up multiples of 3 or 5 total = 0 for i in range(1, N + 1): if i % 3 == 0 or i % 5 == 0: total += i print(total) or を使います。 and ではありません。 96

練習問題 4-2 2つ選んだ積の最大値 N個の整数 A_1, A_2, ..., A_N が与えられます。 この中から異なる2つを選んだとき、 その積の最大値を出力してください。 97

練習問題 4-2：入力と出力 入力： N A_1 A_2 ... A_N 入力例： 5 3 1 4 1 5 出力例： 20 98

answer_4_2.py # Read N and the list of N integers N = int(input()) A = list(map(int, input().split())) # Try every pair and keep the largest product best = 0 for i in range(N): for j in range(i + 1, N): if A[i] * A[j] > best: best = A[i] * A[j] print(best) 99

answer_4_2.py の考え方 なので、二重ループで全ペアを調べても間に合います。 A_i >= 1 なので、積は必ず1以上です。 そのため、 best = 0 で初期化できます。 N <= 100 100

練習問題 4-3 何回で超えるか 整数 N が与えられます。 1から始めて2倍することを繰り返すとき、 N を初めて超えるのは何回目でしょうか。 101

練習問題 4-3：入力と出力 入力： N 入力例： 10 出力例： 4 1 → 2 → 4 → 8 → 16 なので、4回です。 102

answer_4_3.py # Read an integer N = int(input()) # Double x until it exceeds N x = 1 count = 0 while x <= N: x *= 2 count += 1 print(count) 103

answer_4_3.py の注意点 ループを続ける条件は、 x <= N です。 x < N だと、 x がちょうど N のときに止まってしまいます。 104

第4講まとめ この講では、 たくさんのデータをまとめて扱うためのループ を学びました。 for 、 while 、 enumerate 、 zip 、 break は、B問題で何度も使います。 105

次回予告 次の第5講からは第2部に入ります。 テーマは、 リスト です。 この講で先取りして使ってきたリストの操作を、一通り整理していきます。 106