AtCoder Beginner Contest 265のA~D問題を解いたので、解くときに考えていることなどを書いていきます。
緑コーダー以下くらいの方の参考になればと思います。
A: Apple
1個X円のりんごと3個Y円のりんごをN個買うのに必要な最低の値段を求める問題です。
ポイントはりんごを3個セットで買った方がお得になるかどうかですね。
りんごを3個セットで買った方がお得になるなら、可能な限り3個セットを買って残りをバラで買う方が安くつきますし、りんごをバラで買った方がお得ならN個のりんごをバラで買うと安くなります。
これを実装するためには、3個セットと1個を3個買う場合の場合分けと、可能な限りりんごを買う場合にはNを3で割った商とあまり（商が3個セットを買う個数、あまりが1個ずつ買う個数に相当します）が求められれば良いです。
場合分けはif文、商とあまりを求めるには 「//」 演算子と「%」演算子を使うとできます！
コードは以下になります。
x,y,n = map(int,input().split())
if y > x * 3:
# 全部バラで買う方がお得
ans = n * x
else:
# 3個セットをぎりぎりまで買う
ans = (n // 3) * y + (n % 3) * x
print(ans)
B: Explore
一列に並んだ部屋があり、持ち時間を消費して次の部屋に移動することができます。
このとき最後までたどり着けるかを判定する問題です。
途中にはボーナス部屋があって、そこに入ると持ち時間を回復することもできます。
この問題は配列のインデックスに気を付けながら、単純に頭からシミュレーションしていけば解けそうですね。
こんな感じのコードで通りました。
n,m,t = map(int,input().split())
A = list(map(int,input().split()))
bonus = dict()
for _ in range(m):
x,y = map(int,input().split())
bonus[x-1] = y
idx = 0
ok = True
time = t
while idx < n-1:
if time <= A[idx]:
ok = False
break
time -= A[idx]
if idx+1 in bonus:
time += bonus[idx+1]
idx+=1
print('Yes' if ok else 'No')
ボーナス部屋かどうかを高速に判定できるように辞書型に入れてみましたが、解説にあるように配列に入れるのも実装が楽になりそうです。
C: Belt Conveyor
マス目に上下左右の動き先が書かれているので、それに従って移動したときに動けなくなったときの座標、もしくは無限に移動するかの判定を行う問題です。
無限に移動するか？の判定ですが、これは同じマス目に2回以上到達するかで判断できます。
なぜなら、一回通ったところをもう一度通ると、それ以降は同じ動きを繰り返すことになってしまうからです。
あとは動けなくなるか同じマス目に２度到達するまで繰り返せばよいです。
最悪の計算量はマス目をすべて探索するパターンが最悪ですが、せいぜい500*500=250000=2.5*10^5なので間に合いそうです。
h, w = map(int,input().split())
grid = []
for _ in range(h):
row = input()
grid.append(row)
arrived = [[0]*w for _ in range(h)]
x = 0
y = 0
ok = True
while True:
next = grid[x][y]
if next == 'U':
if not x == 0:
x -=1
else:
break
if next == 'D':
if not x == h-1:
x += 1
else:
break
if next == 'L':
if not y == 0:
y-=1
else:
break
if next == 'R':
if not y == w-1:
y+=1
else:
break
if arrived[x][y]==1:
ok = False
break
arrived[x][y]=1
if ok:
print(f'{x+1} {y+1}')
else:
print('-1')
相変わらずインデックスがずれているので注意が必要です。
Pythonは文字列に対してそのままスライスできるのが良いですね。
D: Iroha and Haiku (New ABC Edition)
3つの部分和がP,Q,Rになるかという問題です。（ただし、Pの区間＜Qの区間＜Rの区間）
とりあえず、部分和を使う問題なのであらかじめ累積和を求めておくとよいですね。
累積和があると何ができるようになるかというと、尺取り法と組み合わせて区間の和がP, Q, Rとなる区間をすべて求めることができます。
すると、区間の和がPとなるある区間に対して、その次に大きい区間の和がQとなる区間は２分法で求めることができます。
さらに、その次に大きい区間の和がRとなる区間も同様に２分法で求めることができます。
あとは、区間の和がPとなるある区間を決めて、区間の和がQ, Rとなる区間が存在するかを判定していけば解けるはずです。
計算量は累積和がO(N)、尺取り法*3でO(N)、最後の判定がO(N logN)なので多分間に合うと思います。
コードは以下のようになりました。
import bisect
import itertools
n,p,q,r = map(int,input().split())
A = list(map(int,input().split()))
# 累積和求める
accum = [0] + list(itertools.accumulate(A))
# 区間和がP,Q,Rとなる区間を保存
P_pair = []
P_pairidx = []
right_p = 0
sum_p = 0
for left_p in range(n):
while right_p < n and accum[right_p] - accum[left_p] < p:
right_p+=1
if accum[right_p] - accum[left_p] == p:
P_pair.append((left_p, right_p))
P_pairidx.append(left_p)
if left_p == right_p:
right_p += 1
Q_pair = []
Q_pairidx = []
right_q = 0
sum_q = 0
for left_q in range(n):
while right_q < n and accum[right_q] - accum[left_q] < q:
right_q+=1
if accum[right_q] - accum[left_q] == q:
Q_pair.append((left_q, right_q))
Q_pairidx.append(left_q)
if left_q == right_q:
right_q += 1
R_pair = []
R_pairidx = []
right_r = 0
sum_r = 0
for left_r in range(n):
while right_r < n and accum[right_r] - accum[left_r] < r:
right_r+=1
if accum[right_r] - accum[left_r] == r:
R_pair.append((left_r, right_r))
R_pairidx.append(left_r)
if left_r == right_r:
right_r += 1
# 区間和がPとなるある区間に対して、区間和がQ, Rとなる区間があるか判定
ok = False
for ppair in P_pair:
idx_q = bisect.bisect_left(Q_pairidx, ppair[1])
if idx_q >= len(Q_pair):
break
qpair = Q_pair[idx_q]
idx_r = bisect.bisect_left(R_pairidx, qpair[1])
if idx_r >= len(R_pair):
break
rpair = R_pair[idx_r]
if ppair[1] <= qpair[0] and qpair[1] <= rpair[0]:
ok = True
break
print('Yes' if ok else 'No')
本当は、尺取り法を使って一発で求めたかったのですが、3つの区間を同時に動かすやり方がわからなかったので、苦肉の策として尺取り法→２分法としました。
解説には尺取り法のみで解いていく方法が紹介されていましたが、ちょっとまだよくわかっていないので勉強が必要です。
まとめ
今回はA~C問題は早めに解くことができましたが、D問題に時間をとられてしまいました。
複数個同時にする尺取り法など、少し発展させたアルゴリズムとかも組めるようになりたいですねー
ただ、理想的な解放のコードが組めなくても、制約から２分法とかで解くんだろうなと思って考えていたら無事に解くことができたので、ちょっとは成長しているのかなと思います。
それでは。
コメント