Atcoder Beginner Contest 281コード解説[A, B, C]
はじめに
本日はAtcoder Beginner Contest 281に参加してきました。
成績はAからCの3問正解で今回もDは解けませんでした・・・。解説を見てみると動的計画法を使っていましたので、そちらの学習をしていこうかなと決意したのがさっきのことです。
今回は自分が解けた3問を解説していこうと思います。
Atcoder Beginner Contest 281
試験期間じゃなくてもいつでも問題を解くことはできます。
A - Count Down
0からNまでの数字をカウントダウンで出力するだけです。
n = int(input()) for i in range(n, -1, -1): print(i)
B - Sandwich Number
与えられた文字列が、 2つの英大文字で6桁の数字が挟まれているかを判定します。ここでは以下の流れで判定します。
- 長さが全体で8
- 1番目（インデックスは0）が大文字
- 2番目から7番目の要素が数字で100000以上999999以下
- 8番目の要素が大文字
これらすべてを満たしているものがYesとなります。
s = input() flag = False if len(s) == 8: if s[0].isupper(): if s[1:7].isdigit(): if 100000 <= int(s[1:7]) <= 999999: if s[7].isupper(): print("Yes") flag = True if flag == False: print("No")
C - Circular Playlist
音楽がループ再生されている場所で、今の時間の曲と、その曲が始まってからの時間を答える問題です。まずはどの曲が流れているかについて考えます。
まず1ループにおいて、aの各曲が終わるまでに、ループ開始から数えてどれだけ時間がたっているかを計算します。これを累積和といいます。ある要素に対する累積和は、（ある要素）＋（前の要素の累積和）で計算できます。
（例）
#入力 180 240 120 #累積和 180 420 540
この累積和の最後の値が、１ループにかかる時間を意味しています。
1ループの時間がわかったところで、現在(T)が何番目のループが始まってからどれくらい経つかを考えていきましょう。（何番目のループなのかは今回のコードでは必要ありません。）
# 何番目のループか T// (1ループの時間) # そのループが始まってどのくらいか T % (1ループの時間)
これで求めることができます。
T % (1ループの時間)経過時に流れている曲は、累積和のリストに対して2分探索を行うことで実装しました。
#累積和 180 420 540 # T % (1ループの時間) に流れている曲が何曲目かを判断するために2分探索を用いる。今回の例では300の時を考える。 180 300 420 540 # どこに挿入されるかがわかると、今が何曲目か判断できる。今回は1曲目終了時と2曲目終了時の間にあるため、今は2曲目が流れていることがわかる。
今が何曲目かわかれば後はその曲が始まった時間と現在の時間を引けばよい。
import bisect n, t = map(int, input().split(" ")) a_list = list(map(int, input().split(" "))) a_list_ruisekiwa = [a_list[0]] for i in range(1, n): a_list_ruisekiwa.append(a_list[i] + a_list_ruisekiwa[-1]) one_loop = a_list_ruisekiwa[-1] idx = bisect.bisect(a_list_ruisekiwa, t%one_loop) ans = [] ans.append(idx + 1) if t % one_loop < a_list_ruisekiwa[0]: ans.append(t%one_loop) else: ans.append(t%one_loop - a_list_ruisekiwa[idx-1]) print(" ".join(map(str, ans)))
おわりに
次は絶対D問題を解く！！
