この回のバチャをやりました。
A~Eの5完です。
20:00~だと思いこんでいたらバチャの開始時刻が21:00~だったので盛大にフライングしてしまいました。
まあ、みなさんが走り終わるまでに解説を書きたかったということでどうにか......
A. Beautiful String
Aからまあまあ重くありませんか？
?以外の部分に被りがあるかをチェックする
被りがなければ、前から順番に?を見ていって、
まだ埋めていない?をaだと思って?に入れれる文字を入れていきます。
B. Beautifl Numbers
beautifulのとき、要素
が全て
を満たす長さ
の連続部分列が存在します。
したがって、 beautifulであるかを調べるためには
1~nのインデックスを配列に保存し、
の
について
を調べれば良いです。（連続部分列になっているならその長さはに一致するので）
C. Beautiful Regional Contest
同じ数字同士は同じ賞を受賞しなければならないので分けて考える必要がありません。そこで、実装を楽にするためにRun Length 圧縮をします （しなくてもできますが、しないと実装が重くなります）。
金メダリストはAC数の一番多いグループだけで十分です。
次に、銀メダリストの数が金メダリストの数を超えるまでAC数の多いグループごとに追加していきます。
銅メダリストも同様です。
メダリストの数がn/2以下であれば、n/2を超えない範囲でメダルを与えるグループを追加していきます。
最後に、メダリストの合計数がn/2を越えていないかチェックします。
D. Beautiful Sequence
この問題の制約において、と
は隣に来る文字が確定しています。
なので、基本的には最初にと
を全て使って
配列と
を
となるように
作ります。
このとき1と2が足りなくなってしまったら答えはNOです。
次にと
の間を
で埋めます。
すると、配列は
となります。
ここで、と
の多い方はまだ残っている可能性があります。
しかし、どちらも挿入できる場所は両端の1箇所しかありません。
したがってもしくは
が2個以上余ってしまったら答えはNOです。
また、と
が両方
個もしくは
と
が両方0個のとき
のように並べることができます。
この場合も忘れずにチェックするとACすることができます。
僕はこのとき"YES"を出力し忘れて40分溶かして5ペナを吐きました。
E. Beautiful Mirrors
Aの次に簡単でした。
日目までにかかる期待値を
とすると、
日目にbeautifulと言われて
日目に進める期待値は
です。
これを計算していけば終わりです。
