AGC046-C Shift
数え上げは言い換えの質
解法
0の前の1の数を並べて数列に変換する。
みたいな感じ
この数列と文字列は一対一対応をもち、この数列を , もとの文字列の0の数を
とすると、操作は
なる
を選び、
] に
加え、
] から
減じる、と言い換えられる。
この操作からできる数列を数えればいいので、累積和と、もとの数列との差の絶対値の総和を持っておけばDPできて、 になるが、間に合う。
感想
考察が終了してからDPに落とし込んだり、数列にして扱いやすくするのが苦手なので鍛えていきたい
