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

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

ただいまの
回答率

90.50%

  • Python

    12175questions

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

  • Python 3.x

    10183questions

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

  • Python 2.7

    1468questions

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

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

解決済

回答 4

投稿

  • 評価
  • クリップ 0
  • VIEW 375

super_tomato

score 26

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

# coding: UTF-8
n = int(raw_input())
value_list = []
diff_indx1 = 0
diff_indx2 = 0
diff = None #変数の初期化
for i in range(n):
    value_list.append(int(raw_input()))
    if i == 1:# diffの初期化
        diff = value_list[1] - value_list[0]
        diff_indx1 = 1
    if value_list[i] >= value_list[diff_indx1]:#引かれる数の更新
        diff2 = value_list[i] - value_list[diff_indx2]
        if diff <= diff2:
            diff = diff2
            diff_indx1 = i
            diff_indx2 = diff_indx2
    if value_list[diff_indx2] > value_list[i]:#引く数の更新と引かれる数のリセット
        diff_indx2 = i
        diff_indx1 = i
print diff


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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

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

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

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

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

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

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+4

n = int(input())
min_r, max_d = int(input()), - 10**9
for _ in range(n - 1):
    r = int(input())
    max_d = max(max_d, r - min_r)
    min_r = min(min_r, r)
print(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 21:56

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

    キャンセル

  • 2018/02/04 19:12

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

    if b<r-s:b=r-s
    if s>r:s=r

    キャンセル

checkベストアンサー

+2

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

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

import sys

n = int(input())
nums = (int(sys.stdin.readline()) for _ in range(n))

class Answer(object):
    def __init__(self, nums, n):
        self._nums = nums
        self.n = n
        self.ma = next(self._nums)
        self.ans = -1e10
    def __iter__(self):
        for i in range(self.n-1):
            t = next(self._nums)
            if (t - self.ma) > self.ans:
                self.ans = t - self.ma
            if t < self.ma:
                self.ma = t
            yield self.ans

answer = Answer(nums, n)
for item in answer:
    pass
print(item)

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

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

from sys import stdin

N,*datas = [int(i) for i in stdin.readlines()]
now_max = max(datas[1:])
max_index = datas.index(now_max)
diff = now_max - datas[0]

for i in range(1,N-1):
    if i == max_index:
        now_max = max(datas[i+1:])
        max_index = datas.index(now_max,i+1)
    new_diff = now_max - datas[i]
    if diff < new_diff:
        diff = new_diff

print(diff)

ところで、

diff_indx2 = diff_indx2

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

diff_indx2 = diff_indx1 … (※)

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

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

diff_indx1 = i

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

Python 3.6.1

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/02/03 21:49

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

    キャンセル

  • 2018/02/03 22:25

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

    キャンセル

  • 2018/02/03 23:22 編集

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

    まぁ、悪い例としてお受け取りください(苦笑)

    キャンセル

+1

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/02/03 21:56

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

    キャンセル

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

  • Python

    12175questions

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

  • Python 3.x

    10183questions

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

  • Python 2.7

    1468questions

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