2章 Getting Started – Maximum Profit

蛇太郎は、AOJの問題「Getting Started – Maximum Profit」に挑戦した。

この問題は、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』の2章でも取り上げられている。

問題ページの解説を読んだところ、『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』に書かれてあるのとまったく同じだった。

本に載っているグラフが端折られているものの、問題ページの説明だけでも特にわかりにくいということはない。

蛇太郎は、Emacsを起動しPythonで問題解決のためのスクリプトを書き始めた。

不合格プログラム

蛇太郎は、数分程度で作り上げたプログラムを、自信を持って投稿した。

(最初のプログラム) maximum_profit.py

import sys

# 最大値を求める。
def get_max(data):
    now_max = None
    for i in range(0, len(data)-1):
        start_val = data[i]
        for j in range(i+1, len(data)):
            if now_max is None or data[j]-start_val > now_max:
                now_max = data[j] - start_val
    return now_max

# 入力データの読み込み
data = []
line_num = int(sys.stdin.readline().rstrip())
while True:
    input_data = sys.stdin.readline()
    if not input_data:
        break
    input_data = int(input_data.rstrip())
    data.append(input_data)

result = get_max(data)
print(result)

しかし、このプログラムでは入力行数が多い時に時間がかかり過ぎてしまい、タイムアウトで不合格になってしまった。

修正プログラム

すっかり自信を失くしてしまった蛇太郎だったが、このままではいけないと思い、泣きべそをかきながら問題ページの解説を読んだ。

問題はただちに判明した。
蛇太郎が作ったプログラムは、変数iとjの二重ループになっているため、入力データ数が多いと処理時間が膨大になってしまう。

解説には、一重ループで処理するアルゴリズムが書かれてあったので、蛇太郎はそれを理解した上で余分なコードも削除し、プログラムを修正した。

import sys

line_num = int(sys.stdin.readline().rstrip())
maxv = -2000000000
minv = int(sys.stdin.readline().rstrip())

for i in range(1, line_num):
    rt = int(sys.stdin.readline())
    if rt - minv > maxv:
        maxv = rt - minv
    if rt < minv:
        minv = rt

print(maxv)

タイムアウトになったデータでテストすると、今度は一瞬で処理が完了。
もう一度プログラムを提出すると、3〜4秒後に審査が終わり「Accepted」と表示された。

参考文献

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

Pythonプログラミング物語 © 2016 Frontier Theme