Codeforces Round #581 (Div. 2)D-Kirk and a Binary String
問題概要
長さNの01からなる文字列がs与えられる。次の条件を満たすの文字列tを見つけたい。
- 長さがN
- 任意の
について、
のLISと
のLISの長さが同じ
- tに含まれる0の数が上二つの条件を満たす中で最大
メモ1
まず、先頭と末尾以外の文字について、文字を変更できるパターンを考える。
- 000->010:後ろ2文字を取ってきたときに不適
- 001->011:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
- 010->000:後ろ2文字を取ってきたときに不適
- 011->001:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
- 100->110:後ろ2文字を取ってきたときに不適
- 101->111:3文字を取ってきたときに不適
- 110->100:先頭2文字を取ってきたときに不適
- 111->101:先頭2文字を取ってきたときに不適
また、一気に複数文字変更することを考えたときに、0.....0、1.....1以外の塊を変更させるのは、01若しくは10の部分を取ってきたときに不適であることがわかるため、複数文字変更のパターンは0.....0->1.....1か1.....1->0.....0だが、それらは1文字変更を何回か繰り返したものとみなせるので1文字変更のみを考える。また、001->011と011->001は逆操作であり、0の数を最大化したいことを考えるとあり得る操作は011->001のみになる。
メモ2
文字列sの先頭に0を、末尾に1を付けて考えてよい。これは、新たな先頭を含んだ文字列は常にLISの長さが1長くなり、新たな末尾を含んだ文字列は常にLISの長さが1長くなるからである。これによって、もとのsのすべての要素が、前の要素も後ろの要素も持つようになり、メモ1の内容を適用できる。
メモ3
s全体で考えたときにi文字目を1->0と変更できない場合は、あるl,rを選んだ時に、
か
のどちらかは空ではない
となるようなl,rが存在する場合である。
二つ目の条件はよく見ると左右に分割することができることが分かる。両辺が等しくないときは左側、右側のどちらかが等しくないことが必要だからである。
また、これと、1を0に変えることより左側の条件は
-
右側の条件は
と表せる。
メモ4
左から貪欲に変更していくことができると非常にうれしいので、貪欲で良いことを証明したい。
まず左側の条件を考える。既に左側の1を0に変更していた場合、の末尾が0という条件のLISの長さは常に長くなるが、
のLISの長さは長くなる、変わらない、短くなるのどれもあり得るため、変更できない条件を見ると左側の変更によって、右側の変更を妨げない、もしくは促進する。
右側の条件を考えると、影響がないため、左側の変更によって、右側の変更を妨げない。
よって、左から貪欲に変更していくことが可能である。
なお、右側から変更していくと妨げる場合があるので注意である。
解法
今見ている文字の左側の0で終わる部分文字列のLISと1で終わる部分文字列のLISの長さの差、右側の0で始まる部分文字列のLISと1で始まる部分文字列のLISの長さの差が求められれば良い。文字が2種類なのですべて持っておきながらLISの長さを求めることが可能である。
実際にACした提出
