線形探索を極める！〜Python実装版〜

#はじめに
プログラミングの勉強をするために競技プログラミング（AtCoder）を始めて2ヶ月の初心者、かつQiita初投稿です。
この記事は、@drkenさんが作成して下さった線形探索を極める！ 〜 for 文で色んなことができることを知る 〜という素晴らしい記事を自分なりに理解するためのものです。
また、Pythonでの実装例を載せることで私と似たような方々への参考になればと思い投稿します。
AtCoderの問題を例題としていくつか掲載しますので、ネタバレにご注意ください。
見苦しい点がありましたらご指導いただけますと大変に幸いです。

#条件を満たすものを探す

##ABC 060 B - Choose Integers

####問題文
あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。どんなに大きな整数を選んでもよいですし、整数を5000兆個選んでもよいです。 ただし、選ぶ数はすべてAの倍数でなくてはいけません。また、少なくとも1つは整数を選ばなくてはいけません。
そして総和をBで割ったあまりがCとなるようにしたいです。こうなるように整数を選ぶことが出来るか判定してください。
出来るならば YES、そうでないならば NO を出力してください。

####制約
1≦A≦100
1≦B≦100
0≦C<B

####数値例
A, B, C = 7,5,1
答え：YES
たとえば7,14を選ぶと総和は21となり、これを5で割ったあまりは1となります。

---

####解説
フラグ管理によって判定する典型例かと思います。
問題文に「総和をBで割ったあまりを求める」とありますが、Aの倍数の総和を割ることになりますので、つまりAの倍数をBで割れば余りが求められます。
よって計算量は最大100*100なので愚直に全探索します。

a, b, c = map(int, input().split())
ans = 'NO'              # 判定フラグの初期値をNOで保持する
for i in range(101):    # 入力の最大値100に倍数を掛けたいので100+1
    if a*i % b == c:    # 問題文の判定をifで実装
        ans = 'YES'     # if文の判定がTrueになれば回答をYESに変更
        print(ans)      # if文の判定がTrueになればYESを出力
        exit()          # どれか1つでも出力すればよいので判定Trueで停止
print(ans)              # if文の判定がFalseならば、初期値のままNOを出力

#条件を満たすものがどこにあるのかも一緒に知る
先程のコードにインデックスを設けて場所を判定します。
今回は入力Aの倍数を知ることを目的にします。
得られる結果は # YES 3 です。

a, b, c = map(int, input().split())
ans = 'NO'
idx = 0                 # 倍数を知るため初期値は0
for i in range(101):
    if a*i % b == c:
        ans = 'YES'
        idx = i         # if文の判定がTrueになる倍数を保持
        print(ans, idx) # if文の判定がTrueになればYESと倍数を出力
        exit()
print(ans, idx)         # if文の判定がFalseならば、初期値のままNOと0を出力

enumerateを用いて位置を知ることも可能です。
この場合はイテラブルオブジェクトを与える必要があるので、事前にリストを作成しました。
得られる結果は同じく # YES 3 です。

a, b, c = map(int, input().split())
multiple = [x for x in range(101)]
ans = 'NO'
for idx, i in enumerate(multiple):
    if a*i % b == c:
        ans = 'YES'
        print(ans, idx)
        exit()
print(ans, idx)

#最小値を求める、最大値を求める
Pythonではリストを作ってmin関数、max関数で求めればOKです。
なおlistで遅い場合にはsetを用いると爆速になるようです。
Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由

lst = [i for i in range(-5, 6)]
print(lst)       # [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]
print(min(lst))  # -5
print(max(lst))  # 5

#条件を満たすものを数え上げる

##ABC 081 B - Shift only

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

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

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

####制約

• 1≤N≤200
• 1≤Ai≤10^9

####数値例
N=3
A=16,12,24
答え：2

---

####解説
リストに含まれる値が全て偶数であるならば、回数1としてインクリメントします。
whileで実装する方が分かりやすい問題ですが、あえてforで実装してみます。
Aの最大値は10^9ですが、偶数である必要がありますので√10^9で最大31623回繰り返せば十分求まるかと思います（数学のセンスが無いので計算量予測は雑です）。
※AtCoderでACは確認済み

n = int(input())
a = list(map(int, input().split()))
cnt = 0                              # 数え上げを管理するフラグを立てる
for _ in range(31623):               # _で繰り返し実行のための空引数を用意する
    if all(i % 2 == 0 for i in a):   # リストaをiに渡し、かつallで全てが偶数か判定
        cnt += 1                     # 条件に合致するならcntに回数1をインクリメント
        a = [i//2 for i in a]        # リストaの要素を各々2で割りリストaに戻す
print(cnt)                           # インクリメントで数え上げた数値を出力する

while文での実装例です。
こちらの方がシンプルですね。

n = int(input())
a = list(map(int, input().split()))
cnt = 0

while all(i % 2 == 0 for i in a):
    cnt += 1
    a = [i//2 for i in a]
print(cnt)

##ABC 051 B - Sum of Three Integers
@darkenさんの記事には無い例題ですが、良問だと思いますので記します。
組み合わせの数を求める問題です。
forの多重ループの動きの理解、計算量の考察、条件文の範囲設定と競プロに必要なエッセンスが詰まった問題です。

####問題文
2つの整数K,Sが与えられます。
3つの変数X,Y,Zがあり、0≦X,Y,Z≦Kを満たす整数の値を取ります。
X+Y+Z=Sを満たす X,Y,Zへの値の割り当ては何通りありますか。

####制約

• 2≦K≦2500
• 0≦S≦3K
• K,Sは整数である。

####数値例
K, S=2, 2
答え：6

問題文の条件を満たすX,Y,Zの組は以下の6通りです。

• X=0,Y=0,Z=2
• X=0,Y=2,Z=0
• X=2,Y=0,Z=0
• X=0,Y=1,Z=1
• X=1,Y=0,Z=1
• X=1,Y=1,Z=0

---

####解説
X,Y,ZはそれぞれKの範囲内になります。
よって、k+1（最大2500）でX,Y,Zの3重ループを作成し、組み合わせの合計がSになれば回数1としてインクリメントします。

k, s = map(int, input().split())
ans = 0                       # 条件に合致する数をカウントするためのフラグを立てる
for x in range(k+1):          # kの範囲を全探索するためxのrange範囲はk+1
    for y in range(k+1):      # 同上
        for z in range(k+1):  # 同上
            if x+y+z == s:    # 問題文の条件を設定
                ans += 1      # ifの判定がTrueなら1をインクリメント
print(ans)                    # 条件に合致する数を出力

上の例では正しく答えが求まるものの、値が大きくなると実行時間が制約をオーバーします。
最大で2500^3=15625000000通りを試さなければいけませんので、到底間に合いません。
そのため計算量を減らす工夫が必要となってきます。

仮に2500^2であれば6250000通りとなりますので間に合いそうです。
よってループの数をひとつ減らすことを考えます。

X,Y,Zの組み合わせのうち、ZはXとYが決まればSから引いた値になります。
ただ、素直にその条件で実装すると組み合わせの数は9になってしまいます。

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if x+y+z == s:
            ans += 1
print(ans)

これは例えばX=2, Y=2であればZ=−2でなければS=2にならないためです。
よって、Zは0以上、かつKの範囲内である必要があります。
これを条件文に書き加えると答えは6になります。
ループをひとつ減らしつつ、正解を求めることが出来ました。

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k and x+y+z == s:
            ans += 1
print(ans)

#おわりに
数々の素晴らしい記事を書いて下さっている@drkenさん、諸先輩方、またプログラミングを楽しむ場を提供して下さっているAtCoderへ感謝を申し上げます。
最後まで読んで頂きありがとうございました。