どうもこんにちは！
今週のコンテストはA～Cを完答。Cの完答はひさびさ。
問題
問題は以下のリンクから。完答できたCまでを振り返ります。
A - Is it rated? -
レーティングとDivの値が与えられるので、ABCのRated対象かを判定する問題。Divが1ならレーティングが1600以上2399以下のとき、2なら1200以上2399以下のときにそれぞれRated対象となります。
シンプルに、与えられたレーティングとDivの値を比較しました。
r,x = map(int,input().split())
if (1600 <= r < 3000 and x == 1) or (1200 <= r < 2400 and x == 2):
print("Yes")
else:
print("No")
B - Not All -
与えられる整数列Aと正整数Mが与えられ、Aの末尾を0回以上削除していきます。Aの中に1以上M以下の整数のうち含まれない整数が出てくるには何回削除が必要かを出力する問題。例えばAが1 2 3 2でMが3だったとき、Aの末尾の削除が1回だとまだ1,2,3すべて含まれますが、2回削除したら3がAから無くなるので答えは2回となります。なお、Aに含まれる整数は1からMまでで、M+1以上の値が含まれることはないです。また、最初から1以上M以下の整数のいずれかがAに含まれていない場合もあります。
さて、Aの中に1以上M以下の整数がすべて含まれている場合、Aの集合はM個です。なので、Aの末尾から1個ずつ削除して、Aの集合の数がm-1個となったときの削除回数が答えとなります。
n,m = map(int,input().split())
s = [int(x) for x in input().split()]
ans = 0
while len(set(s)) == m:
s.pop()
ans += 1
print(ans)
C -Sum of Product -
与えられた長さNの整数列Aの$\sum_{1<=i<j<=N} A_i × A_j$の値を出力するという問題。例えばAが1 2 3 だとすると、1×2+1×3+2×3で答えは11となります。数列の最大項数は$3 × 10^5$個で、計算量を考えないといけないC問題の定番ですね。
計算量を考えなければ2重ループで足しこんでいけばよいですが、おそらくTLEになります。計算を整理すると$A_1 × (A_2+A_3+…+A_n)+ A_2×(A_3+A_4+…+A_n)+…+A_{n-1}×A_n$となるので、累積和を使って、例えば$A_1×(A_1+A_2+A_3+…+A_n-A_1)$という感じで計算して足し合わせればよいとなります。
n = int(input())
s = [int(x) for x in input().split()]
# 累積和の配列を作る
psum = [0]
for i in range(len(s)):
tmp = psum[i] + s[i]
psum.append(tmp)
# 累積和を使って求める値を計算する
# 累積和の配列の末尾が数列すべての合計、そこからAiまでの合計を引いてAiを掛け算
ans = 0
for i in range(len(s)-1):
ans += s[i] * (psum[len(psum)-1]-psum[i+1])
print(ans)
おわりに
ひとまずCを解けたのはよかったです。Dは幅優先探索の応用かなとは思いましたが、アルゴリズムがまとめられず断念。
ところで、順位表に各問題の最速回答者が出ていますが、A~Cはそれぞれ30秒程度で解いているみたいですね。過去に解いた同様の問題のソースコードを引っ張り出してくる時間という感じなんでしょうか。
ではでは。