どうもこんにちは！
今週のコンテストはCまで完答、振り返りもCまで。
DはTLEを解消できず。計算量削減のために、黒い点に到達可能かを探す点を先に洗いだして、その点が到達可能な点を事前に幅優先探索でリストアップ、あとはキューの指示時点で到達可能な点の色を見ればOKという実装をしたんですがこれでもTLE。同じ点を複数回探索する場合の計算量を削減できるんですが、1回しかない点しかない場合にTLEになると解消ができてないということでしょうね。
※ 2025/12/9 D追加しました
問題と公式の解説のリンク
問題は以下のリンクから。
A - Triangular Number -
問題
与えられたnに対して$\sum^{n}_{i=1}$を出力する問題。
考え方とコード
for文で計算して出力しました。
n = int(input())
ans = 0
for i in range(1,n+1):
ans += i
print(ans)
B - No-Divisible Range -
問題
整数列$A_i$が与えられます。l <= i <= rを満たす任意のiが$\sum^{r}_{i=l}$の約数ではない(l,r)の組の数を出力する問題。
考え方とコード
ひとまず(l,r)の組を作って$\sum^{r}{i=l}$を算出します。次に$\sum^{r}{i=l}$を$A_i$で割り切れたらその組を除外するとして有効な組み合わせの数を数えました。
n = int(input())
a = [int(x) for x in input().split()]
ans = 0
for i in range(n-1):
for j in range(i+1,n):
s = 0
judge = True
for k in range(i,j+1):
s += a[k]
for k in range(i,j+1):
if s % a[k] == 0:
judge = False
break
if judge:
ans += 1
print(ans)
C - Domino -
問題
数列で表されたドミノがあるとします。ドミノの数はn個で$A_i$の値はそのドミノを右に倒したときにさらに$A_i-1$個のドミノが倒れます。例えば$A_i$が2なら右隣のドミノが倒れ、3なら右にあるドミノが2個倒れるとなります。
この条件で一番左のドミノを倒したときに全部で何個のドミノが倒れるかを出力する問題。
考え方とコード
一番左を1番目としたときに、i番目のドミノが倒れたときに何番目まで倒れるかを1つずつ確認していくとしました。このとき、すでに確認したドミノで何番目まで倒れるかは保持しておき、最大の数を常に維持するようにします。例えば1番目のドミノで6番目まで倒れることが確定しているとき、2番目のドミノが3番目までしか倒れないなら無視、7番目まで倒れるなら最大の数を6から7に更新するというイメージです。
n = int(input())
a = [int(x) for x in input().split()]
i,m = 0, 0
while i <= m and i < n:
m = max(m,i+a[i]-1)
i += 1
print(min(n,m+1))
--- 2025/12/9追加 ---
D - Reachability Query 2 -
問題
n個の白色の頂点とm本の辺で構成する有向グラフが与えられます。あわせて与えられるクエリを処理するという問題。
与えられるクエリは以下の通り。
- 指定された頂点を黒色にする(クエリ1)
- 頂点から辺をたどって黒色の頂点に到達可能かを判定する(クエリ2)
なお頂点と辺、クエリの最大数はそれぞれ$3 × 10^5$です。自己辺と多重辺はありません。
考え方とコード
クエリ1のときにその点から幅優先探索で到達可能な点をリストアップ、クエリ2では指定の頂点がリスト内にあるかで判定するとします。この場合、すでに黒の頂点から到達可能な点のときは幅優先探索が不要なので、計算量を抑えることができます。
(すでに到達可能な点を黒にするとき、その点に到達可能な点は以前の幅優先探索でチェック済みのため)
なお黒の頂点から到達可能な点を探すにはグラフの辺の向きを反対にしたグラフを作ればよいです。
ちなみに、コンテスト中に以下のことをやりましたがTLEでした。
- 到達可能かを判定するクエリのたびに、到達可能な点を幅優先探索で確認
- 到達可能かを判定するクエリで指定される頂点から到達可能な点を事前にリスト化(ある点を複数回判定する場合だけ計算量を削減できる)
幅優先探索の回数を減らせなかったわけですね。自分の場合、黒色の点からすでに到達可能な点を黒色にするときは幅優先探索をしないというのが計算量削減のポイントでした。
from collections import deque
n,m = map(int,input().split())
g = [[] for _ in range(n)]
for _ in range(m):
u,v = map(int,input().split())
g[v-1].append(u-1)
Q = int(input())
r = set()
for i in range(Q):
idx,v = map(int,input().split())
if idx == 1:
if (v-1) not in r:
r.add(v-1)
q = deque()
q.append(v-1)
while q:
p = q.popleft()
for j in g[p]:
if j not in r:
r.add(j)
q.append(j)
else:
print("Yes" if (v-1) in r else "No")
--- 追加ここまで ---
ではでは。