女子大生まあるの「好きに言わせてっ!」

美味しいもの食べてる時が一番幸せ教

AtCoder ABC405 C問題解いてみた(Pythonだよ)

どうも、まあるです。

最近AtCoderを頑張っている後輩に触発されてABC問題当日には無理でしたが解いてみました。

pythonでしか解いたことない勢で、最適化とかアルゴリズムの知識皆無なのでいっつもCがTLEになるのですが今回は2回目に少し書き換えて見事ACできたのでまとめておこうと思います。

まず今回の問題がこちら↓。

atcoder.jp

簡単に説明すると、全てのペアの積の和を求めてねって問題ですね。

私が実装しようと思った考えが、サンプル問題で一個ずつ二つの数をかけて合計出してる説明を見た時に一つのかけられる数に対してかける数をまとめようという方法です。

例えば[3,5,6,2,1]とあったら最初のかけられる数を配列最初(0番目)の3として後ろ[3,5,6,2,1]部分を全て足して最後に3とかけちゃおうという作戦です。そして次はかけられる数をひとつずらした5としてその後ろ[3,5,6,2,1]をかける数と見てまとめて足して最後に5とかける。これを配列の最後から2番目まで続けて終了です。

式にすると{3*(5+6+2+1)}+{5*(6+2+1)}+{6*(2+1)}+(2*1)という計算方法です。

 

最初に書いたコードが以下になります。

from copy import copy
n = int(input())

multiplied = list(map(int, input().split()))
multipty = copy(multiplied)
ans=0
for i in range(n-1):
  multipty[i]=0
  a_2 = sum(multipty)
  a_1 = multiplied[0]*a_2
  ans+=a_1
  del multiplied[0]
print(ans)
    

見てわかるように無駄に配列二つ作ってますね笑

当初delを使うことにこだわってたのでfor文とのずれを解消するために二つ作ってました。かけられる数であるmultipliedの配列の0番目を指定して、かける数であるmultiplyの配列はかけられる数に使われる部分には0という値を再代入して、sum()で出すことでいらない数の合計を取得しないようにしました。

delは配列の最初を消して次のかけられる数が取得できるようにしているのですが、残念なことに一番目を消して全ての値を一個前に移動させることをするのでO(n)かかってしまうんですね〜〜

つまりfor文はひとつでもOが(n^2)かかっちゃう。これじゃあTLEだ。書いた直後は自信満々に出してて笑う笑

 

ということでじっと見てみると、あ、別に配列一つでいいぞと気づき、お、全ての値の合計値からかけられる数になる部分を毎回引いていけば一気に楽になるぞと書き換えられました。

n = int(input())
li = list(map(int, input().split()))
ans=0
total=sum(li)
for i in range(n-1):
  total -= li[i]
  ans+=li[i]*total
print(ans)

 

ということで俗にいう累積和の応用に近いのかなと思います。解説欄ではもっとすごい数学的最適化手法を使っていたのでそちらC++とかを使う人にはいいのかなと思います。

 

だとしても一発でTLEしないで行ける日は来るのか、、、センスとかもあるだろうな〜

 

ずっと思ってたけどAtCoder土曜日の夜9時ってお出かけ予定ある人には辛いよね。私毎週は参加できる気がしません(´・_・`)

時間変えてくれ〜〜と思うまあるでした。

 

まある