ABC194参戦記

忙しかったのと、やりたいことが多くて復習を兼ねたブログ記事を放置していましたが、今まで続けてきていることですし、自分の理解の定着を図るためにも簡単にではありますが、ABC194の参戦記を書いていきます。

茶色レートのPython3使用者です。

A – I Scream

言葉の定義を読み取れるか、条件にあった判定が出来るかを問われる問題。

判定する条件に使用する値は2つで、
乳固形分は、A+Bした値を使用して判定し、乳脂肪分はBを使用して判定すればOKです。

あとは、条件式を丁寧に書いていけばOKです。
条件式は、一番制約が厳しいものから順に書いていきます。
今回は、出力は数字で出力するように指定されているので、対応する数字を出力します。

# AtCoder Beginner Contest 194
# A - I Scream

a,b=map(int,input().split())

if a+b>=15 and b>=8:print(1)
elif a+b>=10 and b>=3:print(2)
elif a+b>=3:print(3)
else: print(4)

条件が緩いものを上に書くと、WAになります。

a,b=map(int,input().split())

if a+b>=15 and b>=8:print(1)
elif a+b>=3:print(3)            # ここを入れ替えるとWAになります。
elif a+b>=10 and b>=3:print(2)  # ここを入れ替えるとWAになります。
else: print(4)

B – Job Assignment

配列の操作と、二つの要素を組み合わせてデータを持っておくのに慣れる問題。
(今回は、各仕事を最速で終わらせることができるのは誰か。それは何分で終わるのか。を持っておく)

公式の回答は二重のfor文でしたが、私は以下のように考えました。

仕事Aを一番早く終わらせることができる人と、仕事Bを一番早く終わらせることができる人が、

・同じ場合
　⇒ABいずれかの仕事を2番目に終わらせる人より、同一人物がABどちらもやったほうが、
　　早い場合
　　　⇒仕事の早い人ひとりがAとBにかかる時間の合計
　　遅い場合
　　　⇒ABいずれかの仕事を2番目に早く終わる人が仕事にかかる時間

・違う場合
　⇒仕事Aと仕事Bの終わる遅いほうの時間

仕事が早い人の情報が重要なので、だれが各仕事を一番早く終わらせることが出来るかを保持しておきます。

# AtCoder Beginner Contest 194
# B - Job Assignment

n=int(input())

amin=[10**9+7,0] # Aを早く終わらせることができる人の情報[m,i]
bmin=[10**9+7,0] # Bを早く終わらせることができる人の情報[m,i]
a=[]
b=[]

for i in range (n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
    if amin[0]>A: # Aにかかる時間が短ければ更新
        amin=[A,i]
    if bmin[0]>B: # Bにかかる時間が短ければ更新
        bmin=[B,i]
a.sort()
b.sort()

if amin[1]==bmin[1]:
    print(min(amin[0]+bmin[0],max(a[0],b[1]),max(a[1],b[0])))
else:
    print(max(a[0],b[0]))

C – Squared Error

愚直に式変形が出来るかを問われる問題と、実装上は、累積和が利用できるかを問われる問題。
として解きました。
数学的な考察や、Aiが取る範囲が小さいことを利用した解法はわかりませんでした。

入力例の2,8,4を考えると

( 8 – 2 )² + ( 4 – 2 )² + ( 4 – 8 )² = ( 8² -2 × 8 × 2 + 2² ) + ( 4² – 2 × 4 × 2 + 2² ) + ( 4² – 2 × 4 × 8 + 8² )
　　　　　　　　　　　　　 = 64+4+16+4+16+64 – 2 × { ( 8 × 2 ) + ( 4 × 2) + ( 4 × 8 ) }
= 64+4+16+4+16+64 – 2 × { 2 × ( 8 + 4 ) +8 × (4) }
　　　　　　　　　　　　　 = 168 – 2 × ( 24 + 32 )
= 56

このように式を展開、括弧でくくると、以下のような性質があることの予想がつきます。
・配列の各要素が2乗する値として出てくるのはそれぞれN-1回なこと。
・-2×○○の部分は、配列の各要素かける、それ以降の要素の累積和であること。

少し大変ですが、入力例2 [ -5, 8, 9, -4, -3 ] でも試してみます。

(8-(-5))² + (9-(-5))² + ((-4)-(-5))² + ((-3)-(-5))² + (9-8)²
　+((-4)-8)²　　　　 + ((-3)-8)² + ((-4)-9)² + ((-3)-9)² + ((-3)-(-4))²

= 64-2･8･(-5)+25 + 81-2･9･(-5)+25 + 16-2･(-5)･(-4)+25 + 9-2･(-3)･(-5)+25 + 81-2･9･8+64
　+ 16-2･(-4)･8+64 + 9-2･(-3)･8+64 + 16-2･(-4)･9+81 + 9-2･(-3)･9+81 + 9-2･(-3)･(-4) +16
= 64+25+81+25+16+25+9+25+81+64+16+64+9+64+16+81+9+81+9+16
　-2{8･(-5)+9･(-5)+(-5)･(-4)+(-3)･(-5)+9･8+(-4)･8+(-3)･8+(-4)･9+(-3)･9+(-3)･(-4)}
=64×4+25×4+81×4+16×4+9×4
　-2{(-5)･(8+9+(-4)+(-3) +8･(9+(-4)+(-3) +9･((-4)+(-3)+(-4)･(-3))
=780-2(-50+16-63+12)
=950

上の予想が正しそうなことがわかりました。
この予想が外れた場合はまた考えることにして、配列の特定の要素以降の累積和を取得する方法について考えます。詳細はこのQuiteの記事が参考になると思いますが、事前に配列すべての累積和について求めておいて、特定の要素以降の累積和を求めたいときは、情報を得たい要素以前の値を引けば区間の累積和が瞬時に求まるイメージです。

あとはこれらをコードに落とし込めばOKです。
各要素について、答ようの変数ansに以下の2つの操作をします。
・2乗した値と(N-1)のかけた数字を足す。
・その要素以降の累積和の2倍を引く。

# AtCoder Beginner Contest 194
# C - Squared Error

N=int(input())
A=list(map(int,input().split()))
accumA=[0]
for i in range (N):
    accumA.append(accumA[-1]+A[i])

ans=0

for i in range (N):
    num=A[i]
    temp=num*num
    temp*=(N-1)
    ans+=temp
    m=num*(accumA[-1]-accumA[i+1])
    ans-=2*m

print(ans)