記事の対象読者 鉄則本を読んでいる人へ
みなさん、競技プログラミングに励んでいますか？
いま、競技プログラミングを上達させるための一冊といえば、競技プログラミングの鉄則ですよね！！
しかし、初心者の皆さん、この本を使いこなせていますか？？
わたし自身、最初はこの本の理解に時間がかかりました。
そこで、
- ちょっと苦手意識がある
- 得意とはいえない
と感じているみなさんに役立てるように、鉄則本の勉強メモを記事化します！！！！
競技プログラミングに苦手意識がある人でも理解しやすいように、この記事では、以下の観点にそって鉄則本の要点を紹介します。
- 問題が伝えたい考え方
- 実装上の注意
- 習熟したい基礎
もちろん、鉄則本を読んでいる人向けの内容です。
今回扱うテーマは、二分探索です。
言語は、Python を使用します。
鉄則本の内容を染み込ませるために、ぜひこの記事を活用してみてください。
それでは、さっそく内容に移りましょう。
ほんとうの初心者さんはこちら
ちなみに、競技プログラミング初心者は、こちらの記事がおすすめです。
鉄則本の作者さんの記事です。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】
A11、B11 二分探索の基礎
この問題が伝えたい考え方
- 二分探索という考え方
- 二分探索を使うには、配列がソートされている必要がある。
実装上の注意点
-
while文が終了する条件を左端、右端を使いどのように表現するべきか。今回の例では、全ての範囲を探索し終わる条件はLがRを超えること。よって、L > Rになったら終了。 - 左端、右端を更新する方法
習熟したい基礎
-
bisectモジュールの使い方 -
bisect_leftとbisect_rightの違い -
bisect_leftは、指定した値を挿入する最も左側の位置を返します。既存の値がある場合、その値の前に挿入されます。bisect_rightは、指定した値を挿入する最も右側の位置を返します。既存の値がある場合、その値の後に挿入されます。どちらの関数を使用するかは、挿入位置の左側または右側に挿入したいかどうかに依存します。
A12 答えで二分探索
この問題が伝えたい考え方
- 答えは〇〇以下か、以上か、などの問いを投げることで、答えの範囲を二分探索で絞り込んでいく。
実装上の注意点
-
while文が終了する条件を左端、右端を使いどのように表現するべきか。今回の例では、答えはa秒以上、a秒以下ということがわかればOK。よって、L >= Rになったら終了。 - 左端、右端を更新する方法
B12 方程式の解を二分探索で求める
この問題が伝えたい考え方
- 答えは〇〇以下か、以上か、などの問いを投げることで、答えの範囲を二分探索で絞り込んでいく。
- 単調増加または単調減少である関数の解を求めるためにも有効。
実装上の注意点
- 探索が終了する条件を左端、右端を使いどのように表現するべきか。今回の例では、条件より、左端、右端を推定できる。その幅を、問題の条件より、
0.001以下まで縮める必要がある。よって、繰り返し回数の目安を見積もることができる。繰り返す回数が推定できれば、for文でOK。 - 左端、右端を更新する方法
習熟したい基礎
- 小数と整数の混合計算の結果は小数になります。これは、Pythonが計算結果の精度を維持するためです。
A13 しゃくとり法
この問題が伝えたい考え方
- しゃくとり法は、連続する部分配列の和や長さ、特定の条件を満たす部分配列を効率的に見つけるためのアルゴリズムです。
- 二次元の表を作れば、しゃくとり法や二分探索が使えそうなことに気がつける。
- ただし、しゃくとり法を使わずに、二分探索を使っても解ける。
- 以下のコードのように、二分探索もしゃくとり法も使わない方法もある。しかし、計算量の観点から一部の例ではTLEになってしまう。しゃくとり法での
Riの更新回数は、N-1以下だけですむため高速。
N, K = map(int, input().split())
A = list(map(int, input().split()))
R = [None] * (N - 1)
for i in range(0, N - 1):
for j in range(i + 1, N):
if A[j] - A[i] > K:
R[i] = j
break
elif j == N - 1:
R[i] = j+ 1
break
ans = 0
for i in range(0, N-1):
ans += R[i] - (i + 1)
print(ans)
実装上の注意点
-
R[i] + 1が N 以上になる場合にIndexErrorが発生します。つまり、配列の範囲外にアクセスしようとしているためです。よって、while文の条件に、インデックスエラーにならないための条件を追加する必要があります。
B13
この問題が伝えたい考え方
- あらかじめ累積和を作っておくと、L番目からR番目までの合計価格を高速に求められる。
A14 半分全列挙
この問題が伝えたい考え方
- 全体を半分に分割し、それぞれに対して全探索を行う。その結果を組み合わせる。
実装上の注意点
- Qに対して二分探索を実行するので、先にQをソートしておく。
- インデックスエラーに注意する。
習熟したい基礎
Q.sort()-
A = list(map(int, input().split()))複数の入力値をまとめてリストにする。
B14
この問題が伝えたい考え方
- 部分和をビット全探索で求める
習熟したい基礎
- リストのスライス
- ビット全探索の実装 くどいですが、コメントに説明を追加しています。
# 「配列 A にあるカードからいくつか選んだときの合計」として考えられるものを列挙
# ビット全探索を使う
def Enumerate(A): # 関数 Enumerate を定義します。引数はリスト A です。
SumList = [] # 合計値を保存するための空のリスト SumList を作成します。
for i in range(2 ** len(A)): # 0 から 2^len(A) - 1 までの数値をループします。
sum = 0 # 現在の部分集合の合計値を 0 に初期化します。
for j in range(len(A)): # リスト A の各要素をループします。
wari = (2 ** j) # 2 の j 乗を計算します。これで j 番目のビットを確認します。
if (i // wari) % 2 == 1: # i を wari で割った商を 2 で割った余りが 1 ならビットが立っています。
sum += A[j] # ビットが立っている場合、A[j] を現在の合計値に追加します。
SumList.append(sum) # この部分集合の合計値を SumList に追加します。
return SumList # 全ての部分集合の合計値を含むリスト SumList を返します。
参考記事
・二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
おわりに
今回は、二分探索のみまとめました。今後、他のテーマについても記事化していこうと思います。ぜひ活用してみてください。