ALDS_1_D:Maximum Profit の不正解pythonコードの考察[AIZU ONLINE JUDGE]

記事内に広告が含まれています。

AIZU ONLINE JUDGEの「ALDS1_1_D 最大の利益」を解いたのですが、正解に至るまでいくつかの不正解コードを書いてしまいました。

なぜ自分のコードが不正解かを考えることは非常に重要だと思っています。

そこで本記事では、自分が書いた不正解コードのダメ理由を考察・整理したいと思います。

問題文

FX取引では、異なる国の通貨を交換することで為替差の利益を得ることができます。例えば、１ドル100円の時に 1000ドル買い、価格変動により 1ドル 108円になった時に売ると、(108円 − 100円) × 1000ドル = 8000円の利益を得ることができます。

ある通貨について、時刻 tt における価格 Rt (t=0,1,2,,,n−1)が入力として与えられるので、価格の差 Rj−Ri (ただし、j>i とする) の最大値を求めてください。

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/1/ALDS1_1_D

この問題文で求めたいことを数式で表すと、

$$ \mathrm{max}_{i<j} \ \ R_j – R_i$$

となる値を求めよと解釈できます。

不正解コード1: ２重for文

まずはfor文を２つ回すことで i, j を移動させ、条件に合う組み合わせを見つける方法です。

inf = float('INF')

n = int(input())
R = []
for i in range(n):
    inp = int(input())
    R.append(inp)

ans = -1 * inf
#※1
for i in range(n-1):
    for j  in range(i+1,n):
        ans = max(ans, R[j]-R[i])
print(ans)

このコードのよくないところは、ズバリ 計算量 です。二重for文のため、$O(n^2)$の計算量となって制限時間をオーバーしました。

不正解コード2: $\mathrm{i < j}$が満たされない

計算量を抑えたコードとして、以下のコードを書きました。

#※1 を変更
m = R[0]
for j in range(1,n):
    m = min(m, R[j])        #最小値を更新
    ans = max(ans, R[j]-m)  #差の最大値を更新 $ max_{i<j} R_j - R＿i$に相当
print(ans)

このコードの不正解なポイントは、i < j の条件を満たせていないという点です。答え ans の計算は、$ \mathrm{max} \ \ R_j – R_i$ の計算に相当します。

このコードの挙動を、 $R=[3,4,3,2]$ を例に見ていきます。

不正解コードの挙動

例として j=2 のブロックを見ます。

m は $0<= i <= 2$ のうちの最小値となります。この m を使って $R[2]-m$を計算すると、i < j の条件が満たされていません。

正解コード

不正解コードの m と ans の更新を逆にすれば正解になります。

#※1 を変更
m = R[0]
for j in range(1,n):
    ans = max(ans, R[j]-m)
    m = min(m, R[j])

このコードの挙動は以下のようになります。ansを計算する際、 mの範囲が j 未満であるため、問題文の条件を満たせていることがわかります。

正解コードの挙動

まとめ

AIZU ONLINE JUDGEの「ALDS1_1_D 最大の利益」の不正解コードが不正解である理由について考察しました。

Aizu Online Judge
onlinejudge.u-aizu.ac.jp

正解コードの解説記事はよく見ますが、不正解コードの考察はあまりない印象だったので、読んでいただいた方の助けになれば幸いです。

コメント