質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

解決済

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

teaspoooon
teaspoooon

総合スコア1

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

2回答

-4評価

1クリップ

396閲覧

投稿2022/08/10 13:41

編集2022/08/20 12:00

前提

使用言語 python

質問内容

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

python

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)

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

python

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

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

python

# スニペット(再利用可能なソースコード) 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)

実現したいこと

最後に

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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

slemntqe

2022/08/10 14:42

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

2022/08/10 15:40

meguru_bisect をどのように呼び出して判定するかにより、is_ok の中身の書き方も変わってきます。 meguru_bisect を呼び出す部分のソースも追加してください。
teaspoooon

2022/08/10 17:17

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

2022/08/10 17:32

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

2022/08/10 20:53 編集

全体ソースコードは、ここに書くのではなく、質問を編集して書き替えてください。 あと、そもそも binary_search の結果の判定方法が間違っているので、is_ok をどのように書いても正しい結果になることはありません。 今回の問題における、めぐる式二分探索の戻り値は、「ソート順を維持する場合に挿入される位置」を表します。 例えば、sが「1, 2, 4, 5」の時、「3」を探すと「2」が返ります。 2番目(数字の4)の位置の直前に「3」を入れると、ソート順が維持されるためです。 つまり、探した数字が戻り値の位置に存在するとは限らないということになります。 めぐる式については、以下のページが詳しいので、読んでみてください。 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜 https://qiita.com/drken/items/97e37dd6143e33a64c8c
teaspoooon

2022/08/11 05:55

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

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。