どうもこんにちは！
今週のコンテストは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)
--以下 2025/5/11追加--
D -Escape Route -
H×Wマスのグリッドがあり、各マスに通路・壁・非常口のいずれかが設定されています。各通路マスから最短距離で非常口に向かう方向をマスに上書きするという問題。通路がある場合は必ず非常口にいけるとされています。(なお、すべてのマスが壁の場合や非常口が複数個ということもある)
あるマスから非常口までの最短距離は幅優先探索で求められるとまでは考えたんですが、そのときの方向指定の方法が考えつかず断念していました。解説によると、非常口のマスを起点として幅優先探索をして、そのマスに来る直前にいたマスの方向を通路マスに上書きすればよいとのこと。
解説はC++で書いていたので、勉強がてらPythonにしたのが以下です。このとき、キューを配列で実装したらTLEとなり、dequeでの実装が必要でした。調べてみると、リストの先頭のpopの計算量はO(N)、dequeで実装するとO(1)ですむとのこと。
from collections import deque
h,w = map(int,input().split())
s= []
for _ in range(h):
s.append(list(input()))
dx = [1,0,-1,0]
dy = [0,1,0,-1]
a = '^<v>'
q = deque()
# 非常口の特定
for i in range(h):
for j in range(w):
if s[i][j] == 'E':
q.append([i,j])
# 非常口からの幅優先探索
while len(q) > 0:
i,j = q.popleft()
for k in range(0,4):
ni = i + dx[k]
nj = j + dy[k]
if ni < 0 or ni >= h or nj < 0 or nj >= w or s[ni][nj] != '.':
continue
s[ni][nj] = a[k]
q.append([ni,nj])
# 出力
for i in s:
print("".join(i))
-- 追加ここまで --
おわりに
ひとまずCを解けたのはよかったです。Dは幅優先探索の応用かなとは思いましたが、アルゴリズムがまとめられず断念。
ところで、順位表に各問題の最速回答者が出ていますが、A~Cはそれぞれ30秒程度で解いているみたいですね。過去に解いた同様の問題のソースコードを引っ張り出してくる時間という感じなんでしょうか。
ではでは。