AtCoder Beginner Contest 104 (ABC104) の解説です。
AtCoder Beginner Contest 104 旧版
AtCoder Beginner Contest 104 beta版
解けた問題だけ解説をしていきますー
要項
AtCoder Beginner Contest 104
rated 1200
8/5(日) 21:00 ~ 22:40 (100分)
100-200-300-400 (4問)
ペナルティ: 5分
方針
全完
A - Rated for Me
問題文にあるように、ならばABC、
ならばARC、それ以上ならばAGCを出力すれば良いです。
B - AcCepted
を
の
番目の文字とします。1番目から始まるものとします。
この時、まずはAです。
更に、から
までの間にCが1個あります。
そして、残りは全て小文字です。
この処理を行うには、から
までに存在したCの個数を数え、それが1個かつ
から
までに小文字が
個存在するか確認すれば良いです。
C - All Green
まず、コンプリートボーナスが存在しない時は高得点の問題から順に解くのが最適です。
では、コンプリートボーナスをどう考えれば良いでしょうか?
今回はが小さいので、どの得点をコンプリートしたか
で決め打ってしまいましょう。
そうすると残りはコンプリートボーナスが無いので解く問題数は上からで求められるので、全体で
で答えが求められます。
D - We Love ABC
まず、?は忘れてABC数を考えましょう。
そして、これは知っていると有利なのですが、こういう3個の問題では中央の文字、つまりBを決め打つと考えやすいことが多いです。
仮に、ある地点にBがあるとします。
この時、このBを含むABC数はの左側にあるAの個数を
、右側にあるCの個数を
として
になります。
つまり、の位置を決め打つと
でABC数が求められるので、全体で
で答えが導出できます。
では、?も加えて実際に何個になるか考えます。
まず、Bを決め打った時、左のAと右のCから取ると残りの?は全て任意の文字にできるので、?の個数を左側、右側
として
になります。
左の?と右のCから取ると、となりますね。反対側も同様です。
よって、答えが求まりました。
ここで、に関して毎回計算すると時間が足りないので、予め
まで途中でmodを取りながら計算して配列にでも入れておきましょう。(
なので
から順に求める)
また、左のAの個数、右のCの個数なども累積和という方法を用いて予め計算しておかないと計算時間が足りなくなります。
結果
oooo 4完(1000点) 1:31-6:41-30:19-72:38(2WA) / 82:38
134位
感想
C問題は自分の苦手な全探索系でしたが、なんとかACできて良かったです。
D問題に関しては中央を固定する発想は典型的(例:ABC077_C)なので、ここで覚えてしまいましょう!