問題
解法
使用する考え方
- 二分探索法
- 貪欲法
二分探索法
ソートされた複数のデータの中からあるデータを探す際に、中央値よりも大きいか小さいかで探す範囲を絞っていく方法。
また、何番目のデータか探すだけではなく、何番目と何番目の間に入るかを調べることもできる。
先頭から見ていくよりもかなり速い。
先頭から調べて行った場合最悪5回かかるが、この方法ならば最悪でも3回で済む。 注意 平均値ではなく中央値と比較すること。例
1,2,4,8,16の数字の中から8の場所を見つける場合について考える。
list = [1,2,4,8,16]
lo = 0
hi = len(list)
search = 1
while hi - lo > 1:
mid = (lo+hi)//2
if list[mid] <= search:
lo = mid
else:
hi = mid
print(lo)
#3
データの数が大きくなって行った時に真価を発揮する。
例えば、1というデータの場所を探す際に、1回目に1と16の平均値で8.5と比較してしまった場合、2回目は1,2,4,8の中から探すことになってしまう。最終的に5回の確認が必要になる。
貪欲法
「このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法」らしい。
最初に聞いた時は意味がわからなかったし、今もよく分かってはいないが、例を見て自分の考えをまとめていく。
例
例として上がっていたのは以下の2つがあったのでこれらを見ていく。
なお以下の例は貪欲法で最適解が出るわけではないので注意する必要がある。
実際の問題での使い方
貪欲法は、羊羹をある基準の長さ以上切り分ける時、切り分けられるだけ切り分けた時いくつになるかを調べるのに使っている。切り分けた数がK+1個以上なればその基準の長さは答えになりうる。
そしてK+1個以上に切り分けられる長さの中で最大のものが答えであるため、それを調べるために二分探索法を使っている。
ソースコード
以下が実際に解答したソースコードになる。
check関数に引数として基準の長さを渡すことで、K+1個以上に切り分けられるかをチェックしている。
そしてその範囲を二分探索法で絞っている。
N,L = map(int,input().split())
K = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.append(L)
maxLen = L//(K+1)
minLen = 0
def check(halfLen):
cnt = 0
work_a = 0
for a in A:
if a - work_a < halfLen:
continue
else:
work_a = a
cnt += 1
if cnt >= K+1:
return True
else:
return False
while minLen != maxLen:
halfLen = ((minLen+maxLen)//2) + 1
if check(halfLen):
minLen = halfLen
else:
maxLen = halfLen -1
print(minLen)
最後に
プログラミングに関して
初めは一番小さい切れ目を順番になくしていけば良いのかなとか考えて実装してみましたが全然ダメで、
L = 6 , A1 = 2 , A2 = 3 , A3 = 4
というテストデータを自分で作ってすぐ詰んでしまい、解法を調べながらコードを書いていきました。
二分探索法は考え方自体は知っていて、例の数字を探す時のように単体で使ったこともありましたが、実際に他の考え方と組み合わせて使うのが初めてだったため、かなり手間取ってしまいました。ただ、かなりの頻度で使うと思うので今回自分なりに整理できてよかったと思います。
貪欲法は一見速くなさそうに見えたんですが、実際に使ってみると計算量自体はデータ量に比例するため使い方によっては計算量がそこまで多くならないのかなと思いました。
記事に関して
正直、記事はまだ書き慣れていなくて全く読みやすい記事にはなっていないと思います。
そこは他の人の記事を読んでどういう構成にしたらわかりやすいとか、学んでいけたらと思います。あと、ここをこうしたら読みやすくなる等あれば教えていただけると幸いです。
あと自分で読み返して気になったのが常体じゃなくて敬体の方が良いかなと思いました。常体だと事実を述べているっていうイメージがあるんですが、その割にはふんわりとした説明だったり曖昧な理解だったりが多すぎるかなと。
なので次回からは敬体でもう少し人に説明するような形で書けたらと思います。
以上、最後まで読んでいただきありがとうございます。