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

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

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

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

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

Python

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

Q&A

解決済

4回答

406閲覧

競技プログラミングの問題(Python)_時系列のある値の最大差分

super_tomato

総合スコア34

Python 2.7

Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

Python 3.x

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

Python

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

0グッド

0クリップ

投稿2018/02/03 09:07

下記のサイトの競技プログラミングの問題を解きました。
リンク内容
簡単に説明すると、ある通貨について、時刻 t における価格 Rt (t=0,1,2,,,n−1t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めてください。という問題です。
もしお時間があれば、この問題のプログラムを作成していただきぜひ参考にさせていただきたいです。
下記が僕が作成したプログラムです。多くの改善点があると思うので、改善するべきところを指摘していただくだけでも構いません。
また以下のテストケースを実行した時の実行時間は約32秒でした。ご参考までに。
テストケース

python

1# coding: UTF-8 2n = int(raw_input()) 3value_list = [] 4diff_indx1 = 0 5diff_indx2 = 0 6diff = None #変数の初期化 7for i in range(n): 8 value_list.append(int(raw_input())) 9 if i == 1:# diffの初期化 10 diff = value_list[1] - value_list[0] 11 diff_indx1 = 1 12 if value_list[i] >= value_list[diff_indx1]:#引かれる数の更新 13 diff2 = value_list[i] - value_list[diff_indx2] 14 if diff <= diff2: 15 diff = diff2 16 diff_indx1 = i 17 diff_indx2 = diff_indx2 18 if value_list[diff_indx2] > value_list[i]:#引く数の更新と引かれる数のリセット 19 diff_indx2 = i 20 diff_indx1 = i 21print diff

以上よろしくお願いします。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

Python

1n = int(input()) 2min_r, max_d = int(input()), - 10**9 3for _ in range(n - 1): 4 r = int(input()) 5 max_d = max(max_d, r - min_r) 6 min_r = min(min_r, r) 7print(max_d)

テスト結果

ある時の値Rxについて注目すると、Rx-Riが最大になるのは0からx-1までのiで最小のRiについてになります。つまり、最初からRxまでのうち最小の値が何であったがわかれば、Rxを対象とした場合の最大値がすぐにわかります。しかし、それまでの最大値よりもそれが大きいとは限りませんので、それとの比較も必要です。

まとめると、各ループで次を確認する必要があると言うことです。

  1. Rxがそれまで中の「最小のRi」についての差を求める。
  2. 上の差がこれまでの「最大の差」より大きいなら「最大の差」をその値に更新する。
  3. 次のループに備えて、Rxが「最小のRi」より小さいなら「最小のRi」をその値に更新する。

「最小のRi」がmin_rで、「最大の差」がmax_dです。最初は差分が取れないので単純にとって、min_rに入れて、初期値とします。また「最大の差」は-10**9より大きくないのでそれをmax_dの初期値にします。

計算量はO(n)です。min/max関数を使わずにif文で分岐するなど工夫すればもうちょっと速くなると思いますが、計算量をこれ以上小さくするのは無理だと思います。

投稿2018/02/03 12:10

raccy

総合スコア21733

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/02/03 12:56

コードがとても簡潔で参考になります!確かにif文で分岐すると早くなると思われますね。 僕の場合、if文で分岐することによって速くなっていますがコードが長くなっているので実際どっちのほうが良いのか...。トレードオフな感じがしますね。
mkgrei

2018/02/04 10:12

if文で書くと値入れ替えの部分は以下の2行(4行)で済みます。 のでコードは長くなりません。 b,r,sがそれぞれ何を取るべきなのかは考えてみるとわかります。 if b<r-s:b=r-s if s>r:s=r
guest

0

ベストアンサー

結局input()をコールするところが一番時間がかかるので、
sys.stdin.readline()を使うことによって高速化できます。

無駄にイテレータで書いてみました。

python

1import sys 2 3n = int(input()) 4nums = (int(sys.stdin.readline()) for _ in range(n)) 5 6class Answer(object): 7 def __init__(self, nums, n): 8 self._nums = nums 9 self.n = n 10 self.ma = next(self._nums) 11 self.ans = -1e10 12 def __iter__(self): 13 for i in range(self.n-1): 14 t = next(self._nums) 15 if (t - self.ma) > self.ans: 16 self.ans = t - self.ma 17 if t < self.ma: 18 self.ma = t 19 yield self.ans 20 21answer = Answer(nums, n) 22for item in answer: 23 pass 24print(item)

投稿2018/02/04 10:08

mkgrei

総合スコア8560

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

AOJの場合、他の人のソースコードは以下のリンクから見ることができます。
イメージ説明

投稿2018/02/03 12:24

SatoshiMashino

総合スコア210

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/02/03 12:56

そうですね!その機能も活用していますが、コード作成者とのコミュニケーションがとれないのでこちらのサイトも活用させていただいてます!
guest

0

numpy等を使うと速いのでしょうけど(そういえば使えないんでしたっけ?)、とりあえずモジュールなしで作ってみました。

最大値まで来たら最大値を更新する仕組みです。うまくパスできました。遅かったですけど…

python

1from sys import stdin 2 3N,*datas = [int(i) for i in stdin.readlines()] 4now_max = max(datas[1:]) 5max_index = datas.index(now_max) 6diff = now_max - datas[0] 7 8for i in range(1,N-1): 9 if i == max_index: 10 now_max = max(datas[i+1:]) 11 max_index = datas.index(now_max,i+1) 12 new_diff = now_max - datas[i] 13 if diff < new_diff: 14 diff = new_diff 15 16print(diff)

ところで、

diff_indx2 = diff_indx2

ここのところはミスでしょうか?

diff_indx2 = diff_indx1 … (※)

のような気がします。
(コード全体においてどういう処理に対応しているかは確認していないので、
こう書きたかったのですか?という意味で書きました。悪しからず。)

また、このままだとdiff_indx2の中身もiになってしまうので、

diff_indx1 = i

の前に(※)を持ってくる必要があると思います。

Python 3.6.1

投稿2018/02/03 11:13

編集2018/02/03 15:15
namnium1125

総合スコア2043

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/02/03 12:49

ご回答ありがとうございます! ”diff_indx2 = diff_indx2”はこのままで大丈夫だと思うのですがどうでしょう?ここの部分は引かれる数の更新なのでその部分だけを更新するので。
namnium1125

2018/02/03 13:25

うーんと、何もしないけど、明示的に書いているという意味でしょうか?
namnium1125

2018/02/03 14:40 編集

改めて自分のコードをいろいろとこねくり回していましたけど、やっぱりリストで取り込むと遅くなってしまいますね…改めてインデックスを取ってくる等、無駄が多くなってしまっています。 まぁ、悪い例としてお受け取りください(苦笑)
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問