emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ 二分探索 問題 提出コード 解法 種類以下で問題の条件を満たすような文字列たちを作成できるか？という問題を考えると、ある境界が存在し、それ以下では作成不可能、それ以上では作成可能になります。よって、あるについて問題の条件を満たすかどうか、を見ながら二分探索を行えばよいです。 先頭の文字列から順に見ていったときに、次に作成する文字列は、作成できる文字列の中で辞書順最小のものを選んだ場合が一番得をします。 なので、今作成し終えた文字列の状態を見て、次に作成する辞書順最小の文字列が何か？というのがわかればよいです。 文字列をランレングス圧縮のようにして、 文字目までがという文字になっている という情報で書き換… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2020%2F07%2F09%2F121147" title="AGC029 C - Lexicographic constraints - ツバサの備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2020-07-09 12:11:47 rich https://emtubasa.hateblo.jp/entry/2020/07/09/121147 1.0 100%