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

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

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

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

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

解決済

Python 競技プログラミング 処理高速化 二分探索

toririn_blue
toririn_blue

総合スコア2

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

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

3回答

0評価

4クリップ

1620閲覧

投稿2022/05/19 15:30

編集2022/05/28 08:23

Python 競技プログラミング 処理高速化 二分探索

環境

最近,趣味で競技プログラミングを始めた者です.個人的に使用経験のあるPythonを使っています.
今回のコードの実行環境はatcoderのPython(3.8.2)です.
私がコードの下書きに使っているのは,Google Colabになります.
実行環境でPyPy3(7.3.0)も選べるので利用してみましたが,実行時間はほぼ変わりませんでした.

問題

atcoder内のアルゴリズムと数学 演習問題集の,009 - Brute Force 2の問題になります.
もしかしたら,著作権的な問題があるかもしれませんので,お手数をおかけしますが問題は写しません.

リンク先より確認いただければ,幸いです.

質問

Pythonの処理を高速化する方法として,

  1. 標準入力においてinput()ではなく,sys.stdin.readlineを使用する
  2. 全探索ではなく二分探索を行う
  3. リストlist()ではなく,集合set()を使う

この3点がウェブを調べていてわかりました.1と2の高速化手段を組み合わせたコードと,1と3高速化手段を組み合わせたコードを実装できましたが,満点の条件である実行時間で1000msが切れませんでした.どちらのコードでも1100ms強の実行時間がかかってしまいました.

現状,私ではこれ以上の高速化できないため,他の高速化手段について知りたいと思い,質問しました.

また,Pythonでは,ほぼこれ以上速くならないのであれば,仕方ないので先の問題に進もうと思います.
ちなみに,この問題の元の書籍を購入して読みましたが,基本のコードがC++であるため,参考にはなりませんでした.また,この本の付録的なGithubの参考コードのPythonには,この問題のコードは存在しないようです.

お力添えのほど,よろしくお願いいたします.

1と2の高速化手段を組み合わせたコード

Python

import itertools import sys import bisect input = sys.stdin.readline a, b = map(int, input().split()) c = input().split() c = [int(t) for t in c] s = [] for n in range(a,0,-1): for combi in itertools.combinations(c, n): s.append(sum(combi)) s.sort() n = bisect.bisect_left(s, b) bisect.insort_left(s,b) if s[n] == s[n+1]: print("Yes") else: print("No")
1と3高速化手段を組み合わせたコード

Python

import itertools import sys input = sys.stdin.readline a, b = map(int, input().split()) c = input().split() c = [int(t) for t in c] s = set() for n in range(a,0,-1): for combi in itertools.combinations(c, n): s.add(sum(combi)) if b in s: print("Yes") else: print("No")

ベストアンサーと解決済みコード

本業が忙しく,また動的計画法というものを知らなかったので,解答の理解に時間がかかってしまいました.
kazuma-sさん,lehshellさん,actorbugさん,ご回答いただきありがとうございました.
今回は解決だけでなく,学習につながる解説をしていただいたactorbugさんをベストアンサーとさせていただきます.
actorbugさんが投稿していただいたコードを解釈してみましたので,掲載しておきます.実行時間(63msほど)でした.
私としては,納得できましたが何か間違い等にお気づきの方はコメントいただけると幸いです.

解決済みコードとその解釈

Python

a, b = map(int, input().split()) # aがカードの枚数, bが判定値(判定基準) c = map(int, input().split()) # cがカードの数値リスト dp = [True] + [False] * b # dpのノードを作る.最初がtrueなのは, 判定する初期位置の設定? for n in c: # カードの数値を取り出す. for i in range(b - n, -1, -1): # 判定値から,リストの数字を引く.そこから, 値を大きい方から-1ずつ取り出す.indexの0まで if dp[i]: # dpのリスト内の値は,真偽値なので帰ってくるのは"True" or "False"だから, Trueの場合は dp[i + n] = True # Trueは値としては1だから,dpリスト内の1+(取り出した数値n)をTrueにする. 判定する位置の移動? print("Yes" if dp[-1] else "No") # リストのindexがTrueならその数値をカードの合計で作れる.最後が判定値なので,"Yes",Falseなら"No"

良い質問の評価を上げる

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

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

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

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

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

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

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

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

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

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

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

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

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

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

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