CODEFESTIVAL QualB D問題

先週行われたCODEFESTIVAL 2017 QualB D問題 が解けなかったのですが、解説を読んでもちょっとわからなかったので、他の人のコードを見ながら自分なりに解法を考えていく過程を文章にしました。参考にしてくださる方がいたらうれしいです。

ちなみに私のコードはこちらです（お恥ずかしい）

Submission #1686548 - CODE FESTIVAL 2017 qual B | AtCoder

また今回の解答を考えるにあたっては、上級者の方のコードを参考にさせていただきましたが、Alex_2oo8 さんのコードが最も勉強になりました。感謝とともにクレジットいたします。

Submission #1666434 - CODE FESTIVAL 2017 qual B | AtCoder

問題文

1と0よりなる数列が与えられる。101 の並びを010 に変換することを繰り返すとき、最大何回この変換を行うことができるか？ 制約などは各自元ページで確認してください。

D: 101 to 010 - CODE FESTIVAL 2017 qual B | AtCoder

解説

問題を相互に影響しない部分問題に分割する

101 → 010 をここではスコア化と呼ぼう。 2セル以上続く0で隔てられたセルの配列は、一方のスコア化によって他方の配列が影響を受けないので、スコア化の順序を考える際は2つの配列は独立した問題と考えて良い。したがって、まず2セル以上連続する0を用いてセル配列全体をsplit する。split されて得られたパターンの列をS = \{s_i\} と表記する。  

部分問題の分析

最初の状態でスコア化できるパターンはどこ？

split された部分配列の要素は0を連続して持たない。つまり、0の両隣は1となり、かならず”101”のパターンを持つ。これは”010”に変換して得点が得られるパターンである(スコア化可能パターンと呼ぶ)。

1が連続した配列に注目すると、スコア化のやりかたが整理できる 

解説にもある通り、101111… (101{k})というパターンは、左端の101 をスコア化すると、010111… となり、ちょうどスコア化可能パターンが1つ右隣のセルにずれるようにして再び現れる。これを続けて0000…010 となるまで続けると、ちょうどk点を獲得することができる。これは左右を反転した…11101 (1{k}01)というパターンでも同様である。これを連続スコア化と呼ぶ。   いま、s_i を0 でsplit した配列を考える。得られた配列の要素は1が連続する配列(1-セグメントと呼ぶ)である。左からj番目の1-セグメントを\{a_{ij}\}、a_{ij}の配列の長さを要素とする配列を\{l_{ij}\} とし、いまi を固定しs = s_i と考えて、単に\{a_j\}, \{l_j\} と表記する。  

いかなるスコア化も行っていない状態では、s 中の全ての1-セグメントの左端もしくは右端はかならずスコア化可能パターンになっており、a_jを連続スコア化することによってl_j 点を獲得することができる。

  しかし、a_j は左端のスコア化可能パターンをa_{j-1} と、右端のスコア化可能パターンをa_{j+1} とそれぞれ共有しており、a_j がどのような方法でスコア化を行うかによって、a_{j-1}, a_{j+1} で可能なスコア化の手法が制限される。  

スコア化のやりかたと、隣接する1-セグメントへの影響

いまa_j を起点として考える。

l_j > 1 のとき

  1. a_j の左端のスコア化可能パターンをスコア化するとa_{j-1} の右端のスコア化可能パターンは消失する。また、a_{j-1} の’1’ を1つ消費するので、l_{j-1} が1減少する。
    1. そのままスコア化を続け、l_j 回のスコア化を行うと、a_j の右端とa_{j+1}の境界は…1001… となり、a_{j+1} の左端のスコア化可能パターンも消失する。
    2. l_j  - 1回のスコア化を行うと、a_j の右端とa_{j+1}の境界は…0101… となり、a_{j+1} の左端のスコア化可能パターンは温存される。スコア化の回数はl_j - 1 回より少なくてもa_{j+1} のスコア化可能パターンの状態は変わらないので、l_j - 1 より少ない回数のスコア化のことは考えなくても良い。
  2. 上記1, 2 について左端を右端に、a_{j+1} をa_{j-1} に置き換えても同様である。
  3. スコア化を行わない場合、両端のスコア化可能パターンが温存される。

 

l_j == 1 のとき

  1. 左端のスコア化可能パターンをスコア化すると、常に右端のスコア化パターンも消失する。l_{j-1} が1減少する。
  2. 上記で左端を右端に置き換えても同様である。
  3. スコア化を行わない場合、両端のスコア化可能パターンが温存される。

 

問題に適用する

いま、s を左から順に、手法を選びながらスコア化し、s全体のスコアを最大化することを考える。

a_1

まず、a_1 は左端にスコア化可能パターンを持たないので、

  1. 右端のスコア化可能パターンを用いて連続スコア化し、l_1 点を獲得する（と同時にl_2--）か、
  2. スコア化を行わずに右端のスコア化可能パターンを温存するか

の2択である。

a_2

  1. a_1 で1 を選んだ場合は
    1. 右端のスコア化可能パターンから連続スコア化し、l_2-1 点を獲得し、l_3--。
    2. スコア化を行わず、右端のスコア化可能パターンを温存する。
  2. a_1 で2 を選んだ場合は
    1. 右端のスコア化可能パターンから連続スコア化し、l_2 点を獲得、l_3--。
    2. スコア化を行わず、右端のスコア化可能パターンを温存する。
    3. 左端のスコア化可能パターンから連続スコア化し、
      1. l_2 点を獲得し、右端のスコア化可能パターンを失う。
      2. (l_2 > 1 のとき) l_2-1 点を獲得し、右端のスコア化パターンを温存する。  

以上のパターンの内、a_3 のスコア化手法に影響があるのはa_3 の左端のパターンであり、これで分類すると

  • a_3 の左端にスコア化パターンあり (1.2, 2.2, 2.3.2)
  • a_3 の左端にスコア化パターンがなく
    • l_3 が減少していない (2.3.1)
    • l_3 が減少している (1.1, 2.1)

それぞれのカテゴリーで最大になるスコアを保存し、a_3, a_4, a_5 ...についても同様に計算をしていけば、s全体で得られるスコアの最大値が求められる。