はじめに
今回も不参加につきあとから解いてます。
成績：不参加
A
for文で数を数えて1つおきに足していく。0-indexedなので偶数の時足すことになる。
A
n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
if i%2 == 0:
ans += A[i]
print(ans)
B
Tの1文字目からlen(U)文字目まで見て、この時のTの各文字がUと一致しているか?ならOK、ダメならTの2文字目からlen(U)+1文字目まで見て……というのをスタート地点がlen(T)-len(U)文字目に到達するまで繰り返す。
B
t = input()
u = input()
flag = False
for i in range(len(t)-len(u)+1):
for j in range(len(u)):
if t[i+j] != u[j] and t[i+j] != '?':
break
else:
flag = True
if flag:
print('Yes')
else:
print('No')
250点ですと言われればまあ確かにという難易度かも。
C
各ユーザーが閲覧を許可されているページのリストと、全ページの閲覧が許可されているユーザーのリストを作る。
3種類目のクエリが入力されたらXがYの閲覧を許可されているか、あるいはXが全ページの閲覧を許可されていればYesを出力する。
C
n,m,q = map(int,input().split())
see = [set() for _ in range(n)] #i番目のユーザーが見られるページのポジティブリスト
approve = set() #全部のページを見られる人のリスト
for _ in range(q):
query = input().split()
if query[0] == '1':
see[int(query[1])-1].add(int(query[2]))
elif query[0] == '2':
approve.add(int(query[1]))
else:
if int(query[1]) in approve:
print('Yes')
elif int(query[2]) in see[int(query[1])-1]:
print('Yes')
else:
print('No')
setを知っていれば解ける問題な気がする。
ABCは回数にちなんだ問題を出してきがちだが403のエラーは頭になかった。別に403という数字そのものは関係ない問題だが……
D
DFSとDPの合わせ技みたいなことをやるのかと思った。Aの中で最も小さい数字からスタートしてAの中にある限りDずつ数字を増やしていき、どれを削除するのかをDPで選んでいく……みたいな。サンプルは合ったが提出してみると全然違った。
D_WA
n,d = map(int,input().split())
A = list(map(int,input().split()))
if d == 0:
print(n - len(set(A)))
exit()
A = sorted(A)
dict = {}
for a in A:
if a not in dict:
dict[a] = 1
else:
dict[a] += 1
jokyo = []
visited = [False]*(A[-1]) #既に訪れた頂点のリスト
for dict_key in dict:
start = dict_key
if visited[start-1]:
continue
todo = [start] #今後探索予定である頂点のリスト
while len(todo) > 0:
v = todo.pop() #todoの末尾にある頂点をこれから探索するのでvに代入して消去する
if visited[v-1] == False:
visited[v-1] = True #もしこれまでにvを訪れていなければ訪れたことを記録。
if v+d in dict and v+d-1 < n and visited[v+d-1] == False:
jokyo.append((v,v+d))
todo.append(v+d)
if len(jokyo) == 0: #消すべきものがない場合は0
print(0)
exit()
#このjokyoを使ってdpする。
inf = float('inf')
dp = [[inf,inf] for _ in range(len(jokyo))]
dp[0][0] = dict[jokyo[0][0]]
dp[0][1] = dict[jokyo[0][1]]
for i in range(1,len(jokyo)):
if jokyo[i][0] == jokyo[i-1][1]:
dp[i][0] = min(dp[i-1][0]+dict[jokyo[i][0]], dp[i-1][1])
else:
dp[i][0] = min(dp[i-1][0], dp[i-1][1]) +dict[jokyo[i][0]]
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) +dict[jokyo[i][1]]
print(min(dp[-1][0],dp[-1][1]))
諦めて解説を読んで後日やり直してみることとする。
(2025/5/1追記)
解説を読み、提出ファイルをいろいろ見てみた。方針としては割と似たようなことをやっているが、数列の要素をDで割った余りで分割してそのかたまりごとにDPをやるという方針がしっくり来た。確かにDFSでやるよりもエラーが減りそうだ。DPの組み方は大体同じなのであまりに関する考察不足といったところか。
D_AC
n,d = map(int,input().split())
A = list(map(int,input().split()))
if d == 0:
print(n - len(set(A)))
exit()
A = sorted(A)
dict = {}
for a in A:
if a not in dict:
dict[a] = 1
else:
dict[a] += 1
amari = [[] for _ in range(d)] #余りごとにAの要素を分類
for dict_key in dict:
amari[dict_key%d].append(dict_key)
ans = 0
inf = float('inf')
for am in amari:
if len(am) <= 1:
continue
am = sorted(am)
dp = [[inf,inf] for _ in range(len(am))]
dp[0][0] = dict[am[0]]
dp[0][1] = 0
for i in range(1,len(am)):
dp[i][0] = min(dp[i-1][0],dp[i-1][1]) + dict[am[i]]
if am[i] - d == am[i-1]:
dp[i][1] = dp[i-1][0]
else:
dp[i][1] = min(dp[i-1][0],dp[i-1][1])
ans += min(dp[-1][0],dp[-1][1])
print(ans)