ABC340をPythonで解いてみました。
自分なりの解き方・考え方を書いていければと思っています！！
目次
ABC340 A - 「Arithmetic Progression」
Diff : 9
考え方
初項が$A$、末項が$B$、公差が$D$である等差数列を1行で出力します。
例えば初項3、末項9、公差2(サンプル1）だとすると、
3 5 7 9
となります。つまり、
A A+D A+2*D A+3*D A+4*D ... B
というふうに初項$A$に公差$D$を順々に足していき、末項$B$になったら止めるようにします。
(等差数列が存在する入力のみが与えられることが保証されているので、末項$B$は必ず現れます)
Pythonだと
for 繰り返し変数 in range(初項, 末項 + 1, 公差):
処理
のように$range$を用いると、初項から末項までの項が1つ1つ取り出せます。
実際の実装例は以下の通りです。
コード
A, B, D = map(int, input().split())
res = []
for i in range(A, B + 1, D):
res.append(i)
print(*res)
ABC334 B - 「Append」
Diff : 43
考え方
クエリ処理の問題で、処理内容は配列$A$に値の追加と検索の2つ。
追加は配列を用意して$append$で追加していけばよいので、特に問題なし。
検索は配列$A$の後ろから$k$番目の値を求める処理。Pythonでは配列$A$の最後尾から1番目, 2番目, 3番目,... の値は $A[-1]$, $A[-2]$, $A[-3]$と表すことができるため、最後尾から$k$番目の値は$A[k]$で表せます。驚きの計算量$O(1)$である。
クエリの数も$Q \leq 100$なので特に高速化する必要はありません。
(※自分の中で「クエリ問題 = 高速化」というイメージがあるので念の為)
以上のことを実装したのが以下のコードです。
コード
Q = int(input())
A = []
for i in range(Q):
q, x = map(int, input().split())
if q == 1:
A.append(x)
elif q == 2:
print(A[-x])
ABC340 C - 「Divide and Divide」
Diff : 528
考え方
実は本番中に解けなかった
ある値$K$があったとき、コスト$K$を支払って、$2$で割った数値の小数点以下を切り捨てた数$k1$と切り上げた数$k2$を作成します。
[K] ---> [k1, k2]
cost : 0 ---> K
$k1$でも同じように、コスト$k1$を支払い、$2$で割った数値の小数点以下を切り捨てた数$k3$と$k4$を作成、$k2$も同様に...というふうに処理を行っていきます。
[k1, k2] ---> [k3, k4, k2]
cost : K ---> K + k1
最終的に作成した数がすべて$1$になるまで続けたときのコストの合計を出力します。(どの順番で処理しても最終的なコストは同じになる…はず)
このとき、$K$の合計コストは作成した数値$k1$と$k2$の合計コストを足した値、$k1$は$k3$と$k4$の合計コストを足した値...と考えることができる。
K <-- K は [K + k1 + k2]
/ \
k1 k1 <-- k1 は [k3 + k4]、 k2 は [k5 + k6]
/ \ / \
k3 k4 k5 k6
これは、自分で作成した数のコストによって自分の合計コストが決まるということで、一番最後に作成した値から作成元に向かって順番に合計コストが決まっていくことがわかる。これは再帰で実装することができます。
再帰で実装した場合、二分木と同じ数だけ調べないといけないので、深さが$log_2 K$となり、調査する値は$2^{log_2 K}$となります。
与えられる値の最大値は$N \leq 10^{17}$となので、二分木の深さは$log_2 10^{17} = 56.47277761$となり、調査する値は$2^{56} = 72,057,594,037,927,936$となり、実行すると$TLE$になってしまいます。
そこで、一度呼び出した結果を保存しておいて、次に呼び出されたときは結果のみを返すようにします。(このような方法を メモ化 といいます)
(メモ化でどれだけ計算量が減るかはちょっとわからなかったので誰か教えて下さい…)
以上のことを実装したのが以下のコードです。
コード
N = int(input())
import math
import sys
sys.setrecursionlimit(1000000)
half = dict()
half[1] = 0
def rec(i):
if i in half:
return half[i]
res = 0
if i % 2 == 0:
res = rec(i // 2) * 2
else:
res = rec(i // 2)
res += rec((i + 1) // 2)
half[i] = i + res
return half[i]
rec(N)
print(half[N])
解けなかった理由
間違ったコード
N = int(input())
import math
import sys
sys.setrecursionlimit(1000000)
half = dict()
half[1] = 0
def rec(i):
if i in half:
return half[i]
res1 = rec(math.floor(i / 2))
res2 = rec(math.ceil(i / 2))
half[i] = i + res1 + res2
return half[i]
rec(N)
print(half[N])
切り上げを$math.ceil$で、切り捨てを$math.floor$で実装しましたが、double型で15桁を超えた数を切り上げ・切り捨て計算する場合、誤差が生じるときがあるそうです。
($9999999999999999$を2で割った切り捨て切り上げ計算を$ceil$と$floor$で計算してみたら$[50000000000000000, 50000000000000000]$になりました)
サンプル3の$10^{17}$は通ったのでいけると思った自分が馬鹿でした…
ABC340 D - 「Super Takahashi Bros.」
Diff : 784
考え方
D問題が茶色っておかしくないですか
$N$個のステージから2つの使用許可が出ているということを言い換えると、$N$頂点$2*(N-1)$辺のグラフと考えることができます。各ステージでは一方向にしか許可が出ないので、有向グラフとなります。
頂点$0$から頂点$N-1$への最短距離を求める最短経路問題であり、さらに各辺には$0 \leq A{i},B{i} \leq 10^{9}$の重みが設定されています。この2つの条件から、ダイクストラ法 で解くことができるとわかります。
ステージの情報を読み込むとき、頂点$i$では頂点$i+1$の辺の重みを$Ai$、頂点$Xi-1$の辺の重みを$Bi$で登録します。(頂点$0$始まりでしているので、$Xi$は$1$を引く)
G = [[] for _ in range(N)]
for i in range(N -1):
Ai, Bi, Xi = map(int, input().split())
G[i].append((i + 1, Ai))
G[i].append((Xi - 1, Bi))
あとはこのグラフをダイクストラ法で実行すると、頂点$N-1$までの距離を求めることができます。
以上のことを実装したのが以下のコードです。
コード
N = int(input())
G = [[] for _ in range(N)]
for i in range(N -1):
Ai, Bi, Xi = map(int, input().split())
G[i].append((i + 1, Ai))
G[i].append((Xi - 1, Bi))
dist = [-1] * N
import heapq
Q = []
heapq.heappush(Q, (0, 0))
dist[0] = 0
done = [False] * N
# ダイクストラ法で各頂点への最短距離を求める
while len(Q) > 0:
d, i = heapq.heappop(Q)
if done[i]:
continue
done[i] = True
for j, c in G[i]:
if dist[j] == -1 or dist[j] > dist[i] + c:
dist[j] = dist[i] + c
heapq.heappush(Q, (dist[j], j))
print(dist[N - 1])