AtCoder Beginner Contest 154 ／ Python ／スライスは遅いのか？！

• 初学者です。（ 2019 / 9 ～ 現在６ヵ月目 ）
• AtCoder の問題に Python で取り組んでいます。
• ABC で４問目（茶か緑）まで解けることを目標にしています。

完全に独学なのでコードは酷いと思います。

AtCoder やってる方、お気軽にコメントください。

残念ながら言い訳から入りたい。
直前まで昼寝をしてしまったために、頭が働かなかった。
終了する頃、目が覚めてきたのだが、手遅れだった。

今回も４問目まで簡単だったと思う、知ってる。
しかし、４問目が何かおかしなことになってる間に終了してしまった。

結果

遂に伸びなくなった、というか若干下がった。

あぁーあ。

それにしても、いつまで「暫定」なんだろうか。
５回、９回、次は１４回だって、いつ正式になれるんだ。


まあ、とにかく。

問題と解答と勉強

atcoder.jp

提出したコード

S, T = input().split()
A, B = map(int,input().split())
U = input()
 
if U == S:
    print(A - 1, B)
else:
    print(A, B - 1)

atcoder.jp

提出したコード

S = input()
print("x" * len(S))

どっちがって言う程のことでもないけど、
２問目の方が簡単よね、今回。

atcoder.jp

提出したコード

N = int(input())
 
A = set(map(int,input().split()))
 
if N == len(A):
    print("YES")
else:
    print("NO")

ここで寝ボケが出て。

N = int(input())のところ、
コピペでmap(int,input().split())を張り付けてて。

mapの返り値はイテレータオブジェクトだから
if N == len(A)で必ずFalseになっちゃうという、ね・・・。

わかってるっぽい発言で寝ボケを誤魔化してみた。
ここで WA を喰らわなかったらマイナスは無かったなぁ、多分。

atcoder.jp

提出したコード（ TLE になる）

N, K = map(int,input().split())
p = list(map(int,input().split()))

sum_p = []

for i in range(N - K + 1):
    sum_p.append(sum(p[i:i+K]))
    

ex = (max(sum_p)-K+2)/2

print(ex + K - 1)

隣接する K 個の合計を求めてリストに格納。

合計の最大値を選んで。

最大値から期待値を求める。


という流れで、最大値から一発で期待値を求めるところを、
如何にシンプルにするかという数学の計算を頑張っていたのだが。

何と、合計を求める段階がめちゃめちゃ遅くて TLE になるというオチ。



どうやらスライスがめちゃ遅いらしい。

何が悪いのかと思って合計の最大を出すところを変えてみたところ。

N, K = map(int,input().split())
p = list(map(int,input().split()))

sum_p = 0

for i in range(K):
    sum_p += p[i]

max_p = sum_p

for j in range(K,N):
    sum_p -= p[j - K]
    sum_p += p[j]
    max_p = max(max_p,sum_p)

ex = (max_p - K + 2)/2

print(ex + K - 1)

これなら通る。

スライスを止めて、前の１つ引いて後ろ１つ足す、を繰り返す。

そんで、下のは通らない。

N, K = map(int,input().split())
p = list(map(int,input().split()))

max_p = 0

for i in range(N - K + 1):
    max_p = max(sum(p[i:i+K]),max_p)

ex = (max_p - K + 2)/2

print(ex + K - 1)

スライスを残してアペンドを消してみた。

さらに、下のは通る。

アペンドを残してスライスだけ消してみた。

N, K = map(int,input().split())
p = list(map(int,input().split()))

sum_p = 0
sum_p_list =[]

for i in range(K):
    sum_p += p[i]

sum_p_list.append(sum_p)

for j in range(K,N):
    sum_p -= p[j - K]
    sum_p += p[j]
    sum_p_list.append(sum_p)
    

ex = (max(sum_p_list) - K + 2)/2

print(ex + K - 1)

スライス犯人説。

もうスライス使わん！！僕のレーティングを下げやがってからに、許さん！

サムが犯人の可能性もあるがサムだけ残したものが書けなかったので保釈。



ちなみに、変に嵌まっていた期待値は、別に合計値から求める必要がなかった。

N, K = map(int, input().split())
p = list(map(int, input().split()))

for i in range(N):
    p[i] = (1 + p[i]) / 2

sum_p = 0
for j in range(K):
    sum_p += p[j]

max_sum = sum_p

for h in range(K, N):
    sum_p -= p[h - K]
    sum_p += p[h]
    max_sum = max(max_sum, sum_p)

print(max_sum)

個別の期待値を先に求めて、

「隣接するＫ個の『期待値の合計』の最大」

を求める方が良かったらしい。



1 から P までの P 種類の目が等確率で出るサイコロの出目の期待値は (1 + P)/2

期待値：
　1 × 1/p + 2 × 1/p + 3 × 1/p + ・・・ + (p-1) × 1/p + p × 1/p
= ( 1 + 2 + 3 + ・・・ + (p-1) + p ) × 1/p
　　ここで、
　　1 + 2 + 3 + ・・・ + (p-1) + p = p(p + 1)/2　なので、
= p(p + 1)/2 × 1/p
= (p+1)/2

僕の作った謎公式の説明は割愛。

だって使う意味なかったし。



今考えていると、何に嵌まっていたのかわからない。

別にどこも難しくない奴らじゃないか。

ガッカリ・・・。






atcoder.jp

また動的計画法だってさ。

動的計画法好きやなぁ。

今回はションボリしてるから、やる気がしない。






atcoder.jp

リームー