AtCoder ABC194振り返り(灰コーダー AB2完:C保)

注意：この記事は競プロ初心者が茶色を目指すために復習や反省するだけの記事です。使用言語はPython3で現状のパフォーマンスは200-300程度です。
あくまで自分の備忘録ですが同レベルの方の新しい発見に繋がれば嬉しいです。

結果

A問題 正解
B問題 正解(ミスが多く再提出と時間がかかった)
C問題 やりたいことは分かったが計算量の面でTLEになり不正解

B問題

N人の人がそれぞれ仕事A,BをAi分Bi分で終わらせることができる。その時最短で終わる時間を求める問題。別の人が仕事をするならA,Bの長いほうが終わる時間になり同じ人が仕事をするならA,Bの和が終わる時間になる。

まず根本的な考え方のミスとしてAの時間最小値とBの時間最小値と同一人物の合計の最小値を求めそれらを比較したがそれだと不正解になることに気が付くのが遅かった。
例)
1.A1=4 B1=4
2.A2=8 B2=5

この時一人目に仕事を任せると4+4で8分となってしまう。そのうえ最小値で求めても4分と4分で答えが4分になるが実際A1とB2で5分が一番早く仕事が終わる。
2<N<1000の条件があったため総当たりで考えても計算量は全く問題なかったことに気が付くのが遅かった。

C問題

N個の整数が与えられる。各要素同士の2乗の和を求める。
やることは分かったのでやってみたらTLEになった。

C.py

#TLEになったコード
N=int(input())
num=input().split(" ")
all=0
for a in range(N):
    for b in range(a,N):
        if a!=b:
            all=all+(int(num[a])-int(num[b])**2
print(all)

与えられる数値に|A|<200という制約があったためそれを利用するらしい。
N<3×10^5なのでO(N^2)だと10^10を超え実行速度に問題が出るパターンがある。
しかし-200<A<200なら各要素の2乗のパターンは多く見積もって400×400で160000しかない。
(a-b)^2で求めようとしていたものを考え方を変え、S^2となるSの量を求める。
(雑な例だがS=1が2個,S=3が3個なら1*2+3*2=11となる)

C問題、かなり考えていますが今の理解はここまでなのでいったん保留にします。
他の過去のC問題などもこなしてから再考しようと思います。

身についたこと

・二つ以上の要素でN>10^5の可能性がある時計算量が多くなるためほかの面を利用する。
　今回のC問題の場合は要素数Nではなく要素の範囲-200<i<200を用いてfor文を回す。(C問題)
・全検索で10^10までの回数なら全検索もあり。(B問題)