AtCoder Beginner Contest 158 備忘録

AtCoder Beginner Contest 158の備忘録です。

問題はこちら↓

AtCoder Beginner Contest 158 - AtCoder

ちなみに今回はABCDの4完でした。

・A問題:Station and Bus

入力 s が3文字で与えられるので、全て同じ文字なら”Yes"、1つでも違えば”No"を出力するだけです。

解答例(Python)
https://atcoder.jp/contests/abc158/submissions/10646590

・B問題:Count Balls

整数 n,a,b が与えられ、a個の青いボールを並べてb個の赤いボールを並べる操作を10^100回繰り返した時、先頭からn個目までに青いボールが何個あるかを求める。高橋くんは非常に根気強いですね。私だったら発狂しています。
青いボールと赤いボールを1回ずつ置いた時のボールの数は a+b 個なので、まずはこれがn個までに何回置けるかを求める。〝n//(a+b)〟これに a を掛けたものがこれまでに置いた青いボールの数になる。
あとは足りない分と a のうち小さい方を足して出力します。

解答例(Python)
https://atcoder.jp/contests/abc158/submissions/10646659

・C問題:Tax Increase

消費税額 a,b から元の価格を求める問題です。aは税率8%、bは10%です。
a,bから元の価格になり得る値を調べ、その範囲を全探索すればいいです。
ここで注意しないといけないのは消費税額は小数点以下切り捨てという点です。
つまり2.0円も2.9円も同じ2円になるわけです。なので念のため範囲の上限を+1した値まで調べる。
まず最低価格は
 min(a//0.08,b//0.1)
となり、最高価格は
max((a+1)//0.08,(b+1)//0.08
になる。
あとはこの範囲でループを回して i*0.08==a,i*0.1==b になる最も小さい値を、見つからなければ -1 を出力する。

解答例(Python)
https://atcoder.jp/contests/abc158/submissions/10646556

・D問題:String Formation

初期文字列 s が与えられ q 個のクエリを処理した後の文字列を求めます。
10^100回繰り返す根気があるなら自分でやってくれと思わなくもないです。
さて、各クエリではまず t が与えられます。t=1の時文字列を反転させます。
t=2の時はさらに f,c が与えられ、f=1の時文字列の先頭にcを加えます。
f=2の時文字列の末尾にcを加えます。
愚直に行おうとすると文字列の反転で O(len(s))、先頭への追加で O(len(s)) かかってしまい間に合いません。
そこでcollections.dequeを利用します。先頭、末尾への追加をO(1) で行えます。
注意する点は反転させると追加する位置が逆になることです。なので現在の状態を管理しておく必要があります。同様に出力する時も最終的な向きによって出力する順番が逆になります。

解答例(Python)
https://atcoder.jp/contests/abc158/submissions/10647452