2022年8月21日開催のAtcoder Beginner Contest 265を、備忘的にギリ茶の私の回答と反省を日記的に残しておきます。
C問題までは順調に解けましたが、D問題をうまくTLEにならないように実装できませんでした。累積和を使うのはよくある問題かと思いますが、そこに帰着できず。。なかなか、学習しないなと悔しい回が続いている感じです。。
コンテンツ一覧
A - Apple
問題
果物屋さんでりんごが売られています。
あなたは次の操作を好きな順で好きなだけ繰り返すことができます。
- \(\ X \) 円を払ってりんごを \(\ 1 \) 個手に入れる。
- \(\ Y \) 円を払ってりんごを \(\ 3 \) 個手に入れる。
りんごをちょうど \(\ N \) 個手に入れるには最低何円必要ですか？
制約と入力形式
- $$ 1 \leq X \leq Y \leq 100 $$
- $$ 1 \leq N \leq 100 $$
- 入力される値はすべて整数
回答アプローチ
私の本番の回答としては、スマートではないですが、\(\ N \)個の買い方をすべて試し、その最小値を出力するやり方でやりました。
x,y,n = map(int,input().split())
L = []
for i in range(int(n/3)+1):
L.append(x*(n-3*i) + y*i)
print(min(L))公式解説では、なるべく単価が安い方で買って、あとは\(\ N \)個になるように買うとすれば最適解が得られるとしています。上記だとO(N)になってしまいますが、こちらはもちろんO(1)です。
x,y,n = map(int,input().split())
if 3*x <= y:print(x*n)
else:print(y*(n//3)+x*(n%3))B - Explore
問題
高橋君はゲームの中で洞窟を探索しています。
洞窟は \(\ N \) 個の部屋が一列に並んだ構造であり、入り口から順に部屋 \(\ 1,2,\ldots,N \) と番号がついています。
最初、高橋君は部屋 \(\ 1 \) におり、持ち時間 は\(\ T \)です。
各 \(\ 1 \leq i \leq N-1 \) について、持ち時間を\(\ A_i \) 消費することで、部屋\(\ i \)から部屋 \(\ i + 1 \) へ移動することができます。これ以外に部屋を移動する方法はありません。 また、持ち時間が\(\ 0 \)以下になるような移動は行うことができません。
洞窟内には\(\ M \)個のボーナス部屋があります。\(\ i \)番目のボーナス部屋は部屋 \(\ X_i \)であり、この部屋に到達すると持ち時間が\(\ Y_i \)増加します。
高橋君は部屋\(\ N \)にたどりつくことができますか？
制約と入力形式
- $$ 2 \leq N \leq 10^5 $$
- $$ 0 \leq M \leq N-2 $$
- $$ 1 \leq T \leq 10^9 $$
- $$ 1 \leq A_i \leq 10^9 $$
- $$ 1 < X_1 < \ldots < X_M <N $$
- $$ 1 \leq Y_i \leq 10^9 $$
- 入力に含まれる値は全て整数である
回答アプローチ
実際に部屋での消費時間をシュミレートして解いていきます。持ち時間が\(\ 0 \)になった瞬間ゲームオーバーという点に注意します。
また、ボーナスタイムはその部屋に到達した瞬間に付与されるため、予め各部屋での消費時間に反映させても問題ありません。仮に問題がその部屋の消費時間を消費された後にボーナスが付与される場合は、ボーナス付与前に持ち時間が０以下になる可能性があるため、予め反映させることができません。
n,m,t = map(int,input().split())
A = list(map(int,input().split()))
X,Y = [],[]
for _ in range(m):
x,y = map(int,input().split())
A[x-1] -= y
flag = True
for a in A:
t -= a
if t<=0:
flag = False
break
if flag:print("Yes")
else:print("No")C - Belt Conveyor
問題
縦\(\ H \)マス、横\(\ W \)マスのグリッドがあります。上から\(\ i \)行目、左から\(\ j \)列目のマスを\(\ (i,j) \)と表します。
\(\ (i,j) \)には文字\(\ G_{i,j} \)が書きこまれています。ここで\(\ G_{i,j} \) は U, D, L, R のいずれかです。
あなたは (1,1)(1,1) にいます。あなたは移動することができなくなるまで次の操作を繰り返します。
あなたは現在\(\ (i,j) \)にいるとする。
\(\ G_{i,j} \)が
Uであり、かつ\(\ i \neq 1\) ならば\(\ ( i-1,j \) へ移動する。\(\ G_{i,j} \)が
Dであり、かつ\(\ i \neq H\) ならば\(\ ( i+1,j \) へ移動する。\(\ G_{i,j} \)が
Lであり、かつ\(\ j \neq 1\) ならば\(\ ( i,j-1 \) へ移動する。\(\ G_{i,j} \) が
Rであり、かつ\(\ j \neq W\) ならば\(\ ( i,j+1 \) へ移動する。
それ以外の場合、あなたは移動することができない。
操作を終了した時点であなたがいるマスを出力してください。
ただし、あなたが操作を終了することなく無限に移動し続ける場合は -1 を出力してください。
制約と入力形式
- $$ 1 \leq H,W \leq 500 $$
- \(\ G_{i,j} \) は
U,D,L,Rのいずれかである。 - \(\ H,W \) は整数
回答アプローチ
ポケモンのジムにこういうようなギミックがあったような気がします。\(\ H \times W \) のマス目上にそれぞれ↑↓→←の指示があり、最終的にどのます上にいるかという問題。動けない指示がある場合が唯一の終了条件です。例えばマス目上の一番下の行で「↓」という指示がある場合は、それ以上下には行けないのでそのマスで終了となります。つまり、終了する場合は必ずマスの外周の何処かとなります。
逆に永遠にループする場合は、2回訪れるマスが発生した時です。各マスの指示は固定なので、2回目訪れるマスがあった瞬間、またそこに訪れることになります。
なので、各マスに訪れたか否かを記録することで永遠にループするか否かは判定できますが、マスのマックスはせいぜい \(\ 500 \times 500 \)なので、移動回数が\(\ H \times W \) 以上になったタイミングで無限ループと判定します。（移動回数が\(\ H \times W \) 以上になったら、2回以上訪れているマスが必ず存在するため）
h,w = map(int,input().split())
G = []
for _ in range(h):
G.append(list(input()))
C = {"U":[0,-1],"D":[0,1],"L":[1,-1],"R":[1,1]}
s = [1,1]
count = 0
while True:
count += 1
com = C[G[s[0]-1][s[1]-1]]
s[com[0]] += com[1]
if s[0]<1:
print(f"1 {s[1]}")
break
elif s[0]>h:
print(f"{h} {s[1]}")
break
elif s[1]<1:
print(f"{s[0]} 1")
break
elif s[1]>w:
print(f"{s[0]} {w}")
break
if count>(h*w+10):
print("-1")
breakD - Iroha and Haiku (New ABC Edition)
問題
長さ\(\ N \) の数列\(\ A = (A_0,A_1,\ldots,A_{N-1}) \)があります。
次の条件を全て満たす整数の組\(\ (x,y,z,w) \)が存在するか判定してください。
- $$ 0 \leq x < y < z < w \leq N $$
- $$ A_x + A_{x+1} + \ldots + A_{y-1} = P $$
- $$ A_y + A_{y+1} + \ldots + A_{z-1} = Q $$
- $$ A_z + A_{z+1} + \ldots + A_{w-1} = R $$
制約と入力形式
- $$ 3 \leq N \leq 2 \times 10^5$$
- $$ 1 \leq A_i \leq 10^9 $$
- $$ 1 \leq P,Q,R \leq 10^15 $$
- 入力に含まれる値は全て整数である
回答アプローチ
最初に累積和を求めて、始点の\(\ x \)で全探索をするというやり方が公式解説でした。
二分探索を行なって、合致する項があるかを探索するのですが、Pythonには良い感じの二分探索のツールがない模様。C++では「find」を使えば良いのですが。。Pythonにもbisectというものがあるのですが、こちらは、一致する項がない場合、探索する数値を入れるインデックスを返してしまうため、リスト内に値がない場合もインデックスを返してしまうため今回の問題では不便です。
なので、リスト内になければFlaseを返すような関数を自前で書く必要があります。
import itertools
n,p,q,r = map(int,input().split())
A = list(map(int,input().split()))
S = [0]+list(itertools.accumulate(A)) #累積和、０の項も必要なので追加
flag = False
def b_s(data,value,right): #binary_search
left = 0
right = right
while left <= right:
mid = (left + right) // 2
if data[mid] == value:return True
elif data[mid] < value:left = mid + 1
else:right = mid - 1
return False
for s in S:
if b_s(S,(s+p),n) and b_s(S,(s+p+q),n) and b_s(S,(s+p+q+r),n):
flag = True
break
if flag:print("Yes")
else:print("No")