AtCoder Beginner Contest 104

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

問題文にあるように、 $0 \leq R < 1200$ ならばABC、 $1200 \leq R < 2800$ ならばARC、それ以上ならばAGCを出力すれば良いです。

$S_i$ を $S$ の $i$ 番目の文字とします。1番目から始まるものとします。
この時、まず $S_1$ はAです。
更に、 $S_2$ から $S_{|S|-1}$ までの間にCが1個あります。
そして、残りは全て小文字です。
この処理を行うには、 $S_2$ から $S_{|S|-1}$ までに存在したCの個数を数え、それが1個かつ $S_2$ から $S_{|S|}$ までに小文字が $|S|-2$ 個存在するか確認すれば良いです。

C - All Green

まず、コンプリートボーナスが存在しない時は高得点の問題から順に解くのが最適です。
では、コンプリートボーナスをどう考えれば良いでしょうか？
今回は $D$ が小さいので、どの得点をコンプリートしたか $O(2^D)$ で決め打ってしまいましょう。
そうすると残りはコンプリートボーナスが無いので解く問題数は上から $O(D)$ で求められるので、全体で $O(D2^D)$ で答えが求められます。

D - We Love ABC

まず、?は忘れてABC数を考えましょう。
そして、これは知っていると有利なのですが、こういう3個の問題では中央の文字、つまりBを決め打つと考えやすいことが多いです。
仮に、ある地点 $T_j$ にBがあるとします。
この時、このBを含むABC数は $T_j$ の左側にあるAの個数を $x$ 、右側にあるCの個数を $y$ として $xy$ になります。
つまり、 $B$ の位置を決め打つと $O(1)$ でABC数が求められるので、全体で $O(|S|)$ で答えが導出できます。
では、?も加えて実際に何個になるか考えます。
まず、Bを決め打った時、左のAと右のCから取ると残りの?は全て任意の文字にできるので、?の個数を左側 $z_1$ 、右側 $z_2$ として $xy3^{z_1+z_2}$ になります。
左の?と右のCから取ると、 $z_1y3^{z_1+z_2-1}$ となりますね。反対側も同様です。
よって、答えが求まりました。
ここで、 $3^z$ に関して毎回計算すると時間が足りないので、予め $3^{10^5}$ まで途中でmodを取りながら計算して配列にでも入れておきましょう。( $3^z \mod 10^9+7 = 3^{z-1} \cdot 3 \mod 10^9 + 7$ なので $3^0$ から順に求める)
また、左のAの個数、右のCの個数なども累積和という方法を用いて予め計算しておかないと計算時間が足りなくなります。