一問一答十六週目 - 競プロ引退しました。

AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。

　写経AC。制約が緩いので全探索でよい。Tと等しくなる部分文字列Xを探し、存在していたら"?"部分をすべてaに変えればよい。

　写経AC。ABC127回目（？）あたりで同様の問題があったのでその練習。何とか自力でできるようになりたいな。

・貪欲にスコアが高くなるように全探索

・「各種最もおいしいネタ」と「そのほかのネタ」を分けて降順ソート

・累積和を利用して、ネタの種類が1～Kの時のスコアを調べて最大値を求める

　写経AC。 $B_i$ をキーとして、 $A_i$ と $C_i$ の個数を調べればよい。二分探索って便利なんだな。PyPyでないとTLEです。

　解説AC。一回目で失敗したとしても、それ以降の期待値はずっと変わらない。言われてみたらそりゃそうだ。

八十六回目

むすび

　寝坊した…AC。全探索やるだけ。ただし、汎用性を高めるにはbit探索がよさそう。

　YouTube の動画解説が楽しみになっている。