競技プログラミング めぐる式二分探索

Question

前提

使用言語 python

質問内容

pythonで競技プログラミングの勉強をしています.
AOJの二分探索の問題https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_Bを以下のソースコードを使用して解いたのですが

def i_input(): return int(input())
def i_map(): return map(int, input().split())


# listにitemがあったらTrue, なければFalseを返す
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return True
        elif guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return False


n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0
for i in t:  # tの要素がsに含まれているか確認
    if binary_search(s, i):
        count += 1
print(count)

めぐる式二分探索を使って解けずに困っています.(どのように判定式を記述すれば良いか分からない)

def is_ok(mid):
    """
    二分探索中の判定
    :param mid:
    """
    # ここの条件式をどう書けばよいかわかりません
    pass


def meguru_bisect(ng, ok):

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

全体のソースコード(修正・追加箇所)

# スニペット（再利用可能なソースコード）
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def is_ok(key):
    # ここの部分の判定方法がわかりません.

    if s[key] == i:
        return True
    else:
        return False



def binary_search(ng, ok):
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ng

n = i_input()
s = list(i_map())
q = i_input()
t = i_map()

count = 0
for i in t:
    #　ngがリストの右端までいくとtの要素(i)を含んでいないと判定
    if binary_search(-1, n) != n:
        count += 1

print(count)

実現したいこと

• めぐる式二分探索を使用してhttps://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_Bを解く.

最後に

初めての質問 & Markdown記法なので至らない点があると思いますがよろしくお願いします.

Comments

[slemntqe]

あなたの悩んでいる部分がまさに競技プログラミングの醍醐味なんじゃないでしょうか。どうやってアルゴリズムをコードに落として期待する結果を得るかを考えるのが醍醐味じゃないんですか？それを質問するとは一体どういうことでしょうか。

[actorbug]

meguru_bisect をどのように呼び出して判定するかにより、is_ok の中身の書き方も変わってきます。

meguru_bisect を呼び出す部分のソースも追加してください。

[teaspoooon]

slemntqeさん
返信ありがとうございます。
ご不快な思いをさせて申し訳ございません.
おっしゃる通り、分からない部分を悩んでそれを解決できた時の達成感。それが競技プログラミングの醍醐味の一つだと思います.
いつもは、質問せず"どうやったらこの問題を解けるのか"を考えて取り組んでおります。（2日以上考えたこともあります）
しかし、何日も考えても分からずに結果的に放置してしまうことが増えていました。
そこで、拙い質問の仕方ですが今回質問させていただきました。
ご容赦いただけますと幸いです。

[teaspoooon]

atcorbugさん
返信ありがとうございます。
全体ソースコード

def i_input(): return int(input())
def i_map(): return map(int, input().split())

def is_ok(key):
# ここの部分の判定方法がわかりません.

if s[key] == i:
return True
else:
return False

def binary_search(ng, ok):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
return ng

n = i_input()
s = list(i_map())
q = i_input()
t = i_map()

count = 0
for i in t:
#　ngがリストの右端までいくとtの要素(i)を含んでいないと判定
if binary_search(-1, n) != n:
count += 1
print(count)

コードの追加方法など不備がございましたら、ご指摘お願い致しします

[actorbug]

全体ソースコードは、ここに書くのではなく、質問を編集して書き替えてください。

あと、そもそも binary_search の結果の判定方法が間違っているので、is_ok をどのように書いても正しい結果になることはありません。

今回の問題における、めぐる式二分探索の戻り値は、「ソート順を維持する場合に挿入される位置」を表します。
例えば、sが「1, 2, 4, 5」の時、「3」を探すと「2」が返ります。
2番目(数字の4)の位置の直前に「3」を入れると、ソート順が維持されるためです。
つまり、探した数字が戻り値の位置に存在するとは限らないということになります。

めぐる式については、以下のページが詳しいので、読んでみてください。

二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜
https://qiita.com/drken/items/97e37dd6143e33a64c8c

[teaspoooon]

actorbugさん
返信ありがとうございます。
質問を編集し全体のソースコードを追加しました。
また、解説ありがとうございます。actorbugさんの解説の紹介してくださった記事をもとにめぐる式二分探索法について勉強し直してみます。

Answer 1

meguru_bisectを「リストsのx番目の要素が今回調べたい値以上となるような最小のインデックス値xを探す関数」として実装してみてはどうでしょう。
(pythonのbisectライブラリに含まれるbisect_leftと同じことをするイメージ)

def i_input(): return int(input())
def i_map(): return map(int, input().split())

def is_ok(mid):
    return s[mid] >= i          # i は for i in t: での i

def meguru_bisect(ng, ok):
    # リストsの中で s[x] >= i となるような最小のインデックス値xを探す
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0
for i in t:
    res = meguru_bisect(-1, n)
    if res != n and s[res] == i:
        count += 1
print(count)

Comments

[teaspoooon]

dljfab さん
回答ありがとうございます。
詳しい解説&コメントとても分かりやすかったです。
特に「bisect_leftと同じことをするイメージ」は理解の助けになりました。
回答を元にもう一度、二分探索について勉強します。

Answer 2

def i_input(): return int(input())
def i_map(): return map(int, input().split())

def is_ok(index, key):
    return s[index] >= key


def meguru_bisect(key,m):
    ng = -1
    ok = m
    while (abs(ok - ng) > 1) :
        mid = (ok + ng) // 2
        if is_ok(mid, key):
            ok = mid
        else:
            ng = mid

    return ok

n = i_input()
s = list(i_map())
q = i_input()
t = list(i_map())

count = 0

for i in t:
    #一致する数があるか
    res = meguru_bisect(i, n)
    if res != n and s[res] == i:
        count += 1
print(count)

Comments

[退会済みユーザー]

t[]にs[]の最大値よりも大きな値が含まれる場合、meguru_bisectはnを返すので s[meguru_bisect(i, n)] はIndexErrorになりますよ。

[teaspoooon]

cm67809733さん
回答ありがとうございます。
ご指摘の通り、二分探索についてまだ完全に理解できず、探り探り取り組んでいる状況です。
cm67809733さんの回答を参考にもう一度取り組んでみます。