hitoare https://blog.hatena.ne.jp/hitoare/ hitoare日記 https://hitoare.hatenablog.com/ 競技プログラミング AtCoder AGC 問題リンク 問題概要 \(0\)と\(1\)からなる文字列\(S\)が与えられる。 「\(1 \leqq i < j \leqq|S|\)かつ\(S_i=0,S_j=1\)となる\(i\)と\(j\)の組を選び、\(S_j\)を削除して\(S_i\)の直前に挿入する」という操作を考える。 この操作を0回以上\(K\)回以下繰り返して得られる文字列の総数は何通りか。 解法 操作で文字列がどのように変化するかを考える。 たとえば 0000011111 ↓ 0000101111 ↓ 0000110111 ↓ 1000011011 のように変化する。 この時「選んだ0の直前に挿入する」という条件は、「… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhitoare.hatenablog.com%2Fentry%2F2020%2F06%2F21%2F163638" title="C - Shift(AtCoder Grand Contest 046) - hitoare日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-06-21 16:36:38 rich https://hitoare.hatenablog.com/entry/2020/06/21/163638 1.0 100%