A - Arithmetic Progression
リンク:A - Arithmetic Progression (atcoder.jp)
概要:初項A、末項B、公差Dの等差数列を半角スペース区切りで出力してね
A問題らしいシンプルな文法を問う問題です。
pythonではrange(初項、末項+1、間隔)で簡単に記述できます。
提出リンク:提出 #50139788 - 鹿島建設プログラミングコンテスト2024(AtCoder Beginner Contest 340)
#ABC340 A - Arithmetic Progression
A, B, D = map(int,input().split())
ans = [i for i in range(A, B+1,D)]
print(*ans, sep = ' ')
B - Append
概要:リストに数字を追加したり指定した番号の数字を出力したりしてね
クエリという言葉でぎょっとするかもしれませんが単純なリスト操作ができれば問題無く解けます。
Q回与えられるクエリの1個目をflagの頭文字f、2個目をnumberの頭文字nとして記載しています。
fが1のときはリストAに数字nを後ろから追加、fが2のときはリストAの最後尾から数えてn番目を出力します。
pythonではリストの最後尾をA[-n]として取得できます。
あるいはA[len(A)-n]でも同じことができます。
提出リンク:提出 #50148194 - 鹿島建設プログラミングコンテスト2024(AtCoder Beginner Contest 340)
Q = int(input())
A = []
for i in range(Q):
f, n = map(int,input().split())
if f == 1 :
A.append(n)
if f == 2:
print(A[-n])
C - Divide and Divide
リンク:C - Divide and Divide (atcoder.jp)
概要:数字Nを2で割って2つの整数(上界、下界)にします。操作を行うたびにN円を支払います。すべての数字が1になるまで行ったときの出費を計算してね
制約がなので計算量O(N)だとTLEになります。
よくわからんけど愚直に2で割ってコストをカウントして全部の数字が1になるまで繰り返せばええやろと書いたコードが下記になります。
from collections import deque
N = int(input())
q = deque([p])
count = 0
while q:
cnt = q.popleft()
count += cnt
if cnt % 2 == 0:
d = p = cnt//2
else:
d = cnt//2
p = cnt//2 + 1
if d >= 2:
q.append(d)
if p >= 2:
q.append(p)
print(count)
テストケース実行して入出力例2まではあったので喜んでいたら入出力例3で一生計算が終わらなくて絶望しました。(この時点で制約について気づいていない)
同じ数字を何度も計算するのでメモ化すれば計算量落とせるな、一個前の数字で次に計算するべき数字が決まるから再帰が使えそうだな、まで頭が回りましたがメモ化も再帰も書いたことがなかったのでここで終了しました。
D - Super Takahashi Bros.
リンク:D - Super Takahashi Bros. (atcoder.jp)
概要:重み付きグラフで最短経路を出してね
ダイクストラ法するだけのボーナスタイムです。
ただ私がダイクストラ法書いたことなかったので残念ながら・・・
結果
ただのタイピング速度みたいなA,B問題を5分ちょいで書いただけのコンテストになりました。メモ化再帰やダイクストラ法を勉強するいい機会になり学びが多かったのでヨシ!とします。