AtCoder Beginner Contest (ABC) 189 PythonでC問題解いてみた 解説あり
前回
こんにちは。メリーです。
家でごろごろしながらYoutubeを見るのってほんとに楽しいですよね。
背徳感すら感じる今日この頃です。
決して、昨日雀魂で四暗刻リーチまで行ったのに和了できなかったとか、ポイントが200くらい溶けたとかの現実逃避じゃないです！！決して！！
というわけで本日もAtCoder Beginner Contest (ABC) 189 C問題やって行きます。
前回の続きなので、A、B問題に興味のあるかたは上のリンクから。
言語はPython、提出はPyPy。
目次
C問題 虚飾編
問題文
お皿がいっぱいあって、その上にオレンジがあります。
オレンジをl番目からr番目までのお皿の上のオレンジをｘ個ずつ取ります。
最大で何個取れるでしょう？？
という問題ですね。
N <= 104なので、全探索で間に合いそうですね。
というわけで方針を
1. 全探索する（l,rを決定する）。
2. その区間の中でｘを変化させて合計値を出す。
3. その合計がansより大きかったらansを更新する。
というわけで実装
n = int(input())
a =list(map(int,input().split()))
ans = 0
for r in range(n):
for l in range(r+1):
a1 = a[l:r+1]
for x in range(min(a1),max(a1)+1):
sum_i = sum([i >= x for i in a1]) * x
ans = max(sum_i,ans)
print(ans)
というわけで結果は・・・・
:
:
:
:
:
:
:
:
:
:
:
はい、TLEでした。
まー、ループ回数多いもんね。このコードだと。
計算量はO(N2A)くらいだもんね。オーバーです。
この後のコードと見比べるとわかるけど、
a1 = a[l:r+1]
とか、
for x in range(min(a1),max(a1)+1):
sum_i = sum([i >= x for i in a1]) * x
ココらへんが遅い原因っぽい。
C問題 真相編
というわけで解説を見て組み直したコードがこちら。
n = int(input())
a =list(map(int,input().split()))
ans = 0
for l in range(n):
x = a[l]
for r in range(l,n):
x = min(x,a[r])
ans = max(x*(r-l+1),ans)
print(ans)
なお、Pythonは低速な言語なので、Pythonで提出しても通らない模様。
PyPyで提出しましょう。
というわけでホントの方針はこちら。
1. 全探索する。
2. 最初にl（左端）を固定してr（右端）を一つずつ広げていくイメージ。
3. その区間の最小の値をｘにする。
4. 合計値がansより大きかったらansを更新
という感じです。
左端を固定するのは、xの更新が早くなるため。
右端を固定して、左端を大きくしていくと、毎回xを探して更新しなければならない。
しかし、右端を更新していくと、前のxと新しく追加されたxを比較するだけで良いので処理が速くなる。
例： 入力例1の場合。
2 4 4 9 4 9
l = 0で固定する。
x = a[l] # x = 2
r = 0の場合、
x = min(x,a[r]) # x = min(2,2) = 2
r = 1の場合
x = min(x,a[r]) # x = min(2,4) = 4
のように、r=0の時のxと新しく追加された要素を比較するだけでよくなる。
逆に、rを先に固定してしまうと、
2 4 4 9 4 9
r = 4で固定した場合。
l = 0の場合
a1 = a[0:5] # a1 = [2,4,4,9]
x = min[a1] # x = 2
l = 1の場合
a1 = a[1:5] # a1 = [4,4,9]
x = min[a1] # x = 4 ここで探す処理が入る
のように、最小値が範囲から出て行った場合に再度リスト内で最小の値を探さなければならない。
まぁ、rを固定した場合でも、l=rの場合から逆順にｌを減らしていけば新しく追加される要素との比較だけで済むので、rを固定しなければならない宗派の人はそれでやるといいんじゃないですかね。
forループ回す度にlが減っていくので頭のなかぐちゃぐちゃになりそうですけど。
ansの更新も、このやり方ならxは範囲の中の最小値に決まるので、わざわざsumを使うまでもないですね。
前回までのansと今回の範囲での合計値の大きい方をansに更新するだけで済みますね。
というわけで今回はここまでです。
それでは。
前回
