0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

競プロ典型90問 001 - Yokan Party

Posted at

#問題
競プロ典型90問 001 Yokan Party

#解法
###使用する考え方

  • 二分探索法
  • 貪欲法

####二分探索法
ソートされた複数のデータの中からあるデータを探す際に、中央値よりも大きいか小さいかで探す範囲を絞っていく方法。
また、何番目のデータか探すだけではなく、何番目と何番目の間に入るかを調べることもできる。
先頭から見ていくよりもかなり速い。

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回目は0番目~4番目を調べるため、中央値である2番目の4との大小を比較する。
  2. 4より大きいので次は3番目~4番目の数字を調べる。
  3. 3番目と4番目の中央値である8との大小を比較する。
    • 統計学等で中央値という場合、データが偶数個の場合は中央の2つの平均を取る。
    • 今回は何番目と何番目の間にあるかを調べたいため、インデックスの3と4の平均の3.5を切り捨てて3番目の8との大小比較を行なっている。
  4. 8以下なので3番目~3番目の数字を調べる。
  5. 調べる数字が1つになったため8の場所が3番目で確定する。

先頭から調べて行った場合最悪5回かかるが、この方法ならば最悪でも3回で済む。
データの数が大きくなって行った時に真価を発揮する。

注意

平均値ではなく中央値と比較すること。
例えば、1というデータの場所を探す際に、1回目に1と16の平均値で8.5と比較してしまった場合、2回目は1,2,4,8の中から探すことになってしまう。最終的に5回の確認が必要になる。

####貪欲法
「このアルゴリズムは問題の要素を複数の部分問題に分割し、それぞれを独立に評価を行い、評価値の高い順に取り込んでいくことで解を得るという方法」らしい。
最初に聞いた時は意味がわからなかったし、今もよく分かってはいないが、例を見て自分の考えをまとめていく。

例として上がっていたのは以下の2つがあったのでこれらを見ていく。 なお以下の例は貪欲法で最適解が出るわけではないので注意する必要がある。
  1. ある金額を払う時に最小の貨幣で払うための組み合わせを求める問題
    • 評価値 = 1枚あたりの貨幣の価値
    • 日本の貨幣であれば1枚あたりの価値が高い1万円札を出せるだけ出して、次は5千円札、千円札・・・と続いていく。
  2. ナップサック問題
    • 評価値 = 重さあたりの価値[v/w]
    • 重さあたりの価値が高い順に、荷物を入れられるだけ入れていく。

####実際の問題での使い方
貪欲法は、羊羹をある基準の長さ以上切り分ける時、切り分けられるだけ切り分けた時いくつになるかを調べるのに使っている。切り分けた数が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

というテストデータを自分で作ってすぐ詰んでしまい、解法を調べながらコードを書いていきました。

二分探索法は考え方自体は知っていて、例の数字を探す時のように単体で使ったこともありましたが、実際に他の考え方と組み合わせて使うのが初めてだったため、かなり手間取ってしまいました。ただ、かなりの頻度で使うと思うので今回自分なりに整理できてよかったと思います。
貪欲法は一見速くなさそうに見えたんですが、実際に使ってみると計算量自体はデータ量に比例するため使い方によっては計算量がそこまで多くならないのかなと思いました。

###記事に関して
正直、記事はまだ書き慣れていなくて全く読みやすい記事にはなっていないと思います。
そこは他の人の記事を読んでどういう構成にしたらわかりやすいとか、学んでいけたらと思います。あと、ここをこうしたら読みやすくなる等あれば教えていただけると幸いです。
あと自分で読み返して気になったのが常体じゃなくて敬体の方が良いかなと思いました。常体だと事実を述べているっていうイメージがあるんですが、その割にはふんわりとした説明だったり曖昧な理解だったりが多すぎるかなと。
なので次回からは敬体でもう少し人に説明するような形で書けたらと思います。

以上、最後まで読んでいただきありがとうございます。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?