ABC408-D を Python で解いた

ABC408 D - Flip to Gather
https://atcoder.jp/contests/abc408/tasks/abc408_d

本番中に DP で解こうとして結局解けませんでしたが、後から思いついて AC できました。公式解説とは違う解法なので解説記事にしてみました。

## コンテスト中の自分の動き
C までは楽に終わりましたが D で手が止まりました。過去に類題があったなと思い記憶を頼りに「逆立ち」で調べたところ ABC124-D (https://atcoder.jp/contests/abc124/tasks/abc124_d) が見つかりました。でもちょっと違いますね。DPかなと思いつつやはり思いつきません。

いったん諦めて E に取りかかりましたがこちらも DFS バックトラックを書いてはみたものの TLE。D と心中するつもりで戻ってきました。引き続き DP の方針で考えていると頭にある 0 の連続は消しても問題ないことがわかり、必ず 1 始まりにできることに気づきました。するといろいろと見えてきました。ランレングス圧縮して 0 が何個、1 が何個という風にまとめます。それらをそれぞれまとめて 0 にする、または 1 にするようにしていけばいい感じに DP が組めそうです。

DP 配列ですが、ランレングス圧縮されたやつの i 個目までが条件を満たすようにし、i 個目が j であるような状態にするための操作回数の最小値を$ dp[i][j] $に格納するようにしました。遷移は j の値が
* 1 -> 1
* 1 -> 0
* 0 -> 0

の 3 通りです。1 始まりなので 0 -> 1 の遷移はありません。一度 0 になったらもう 1 にしてはいけません。

あとは手計算で合うことを確認し、実装したのですが一部サンプルが合いません。考えた結果、DP の過程でそれまでの 1 を全て 0 にしてきた場合のみ、一度だけ 0 -> 1 の遷移ができることがわかりました。残り 10 分でどうにかできることではなかったので諦めました。結果パフォーマンス 851 になりレートが大暴落、再び 1100 を切りました。まあ仕方ないですね。

## コンテスト後
まず大人しく公式解説を読みました。完全に数学ですね。こういう考察で解けると気持ちよさそうですが、そうそう思いつけるものでもなさそうです。いったん理解したのでこれは置いといて、自分の DP 解法でも解ける気がしてきたので考えて実装しました。すると AC することができました。

アイデアとしては、一度 1 -> 0 の遷移を経験したらそのことを DP 配列に記録しておき、その場合は再度 1 にはならないようにするというものです。

## 考察
そもそも DP のことを考える前から気づいていたことがあります。問題文の条件を満たすような 0, 1 の並べ方には次の 5 通りがあります。

* 11111111
* 00000000
* 00001111
* 11110000
* 000011110000

全てに共通することとして "10" が 1 個までしかないということがいえます。いったん 1 から 0 になったらもう 1 には戻れません。この考え方と、後で思いついた前述の DP とを組み合わせて正解できる DP に辿り着きました。

ちなみに最初は「"10" が複数あるときにどの "10" を 1 つだけ残すか、それとも全て無くすか」という方針で調べられないかと考えていました。"00" に変えるのか "11" に変えるのかが確定しなかったり、変えた結果新たな "10" が生まれたりでややこしくなったのでこれは没になりました。この時点ではランレングス圧縮は思いついていませんでしたが、ランレングス圧縮した後の "10" を考えればまた違ったのかも？

## 実装
まずランレングス圧縮しておきます。文字列 S が 0, 1 の塊になります。これでこんな風にできますね。

![ABC408-D解説_01.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3876620/6abe1897-daed-4f0f-bcc0-c662479600f8.png)


i 個目の塊までが条件を満たすようにし、i 個目が j であり、さらに 1 -> 0 の遷移が起きた回数が k （0 回または 1 回）である状態にするための操作回数の最小値を $ dp[i][j][k] $ に格納するようにします。j と k は 0 か 1 なので配列のサイズは大丈夫です。

### k = 0 のとき
j = 0 から j = 0 に遷移する場合、i+1 個目が 0 ならそのままでいいです。1 なら 0 にしないといけないのでその個数分加算します。

j = 0 から j = 1 に遷移する場合はその逆ですね。

同様に
* j = 1 から j = 0
* j = 1 から j = 1 

もやっていきます。ここで j = 1 から j = 0 に遷移した場合のみ k を 1 にします。

### k = 1 のとき
一度 1 から 0 の遷移を経験してしまうともう 1 には戻れません。遷移のパターンは限られます。

* j = 0 から j = 0 
* j = 1 から j = 0 

の遷移のみになります。

以上 6 通りの遷移があり、それぞれについて if 文で 2 つに分岐するので非常にコードが長くなります。見間違いそうですね。ですが、なんとか正解にたどり着けました。


```python
def run_lengh_encoding(string):
  result = []
  for i in range(len(string)):
    if result == [] or result[-1][0] != string[i]:
      result.append([string[i], 1])
    else:
      result[-1][1] += 1
  return result

ans = []
INF = 10**20
T = int(input())
for _ in range(T):
  N = int(input())
  S = input()
  RS = run_lengh_encoding(S)
  if len(RS) <= 2:
    ans.append(0)
  else:
    RS = [[-1, 0]] + RS
    # dp[i][j][k] := i 個目までが条件を満たした状態にして、i個目の値が j, それまでに発生した 1->0 の遷移回数が k とする。
    dp = [[[INF for _ in range(2)] for _ in range(2)] for _ in range(len(RS))]
    dp[0][0][0], dp[0][0][1], dp[0][1][0], dp[0][1][1] = 0, 0, 0, 0
    for i in range(0, len(RS)-1):
      string, number = RS[i+1][0], RS[i+1][1]
      
      k = 0
      # j=0 -> j=0        
      if string == "0":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][0][k])
      elif string == "1":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][0][k] + number)
      # j=0 -> j=1
      if string == "0":
        dp[i+1][1][k] = min(dp[i+1][1][k], dp[i][0][k] + number)
      elif string == "1":
        dp[i+1][1][k] = min(dp[i+1][1][k], dp[i][0][k])
      # j=1 -> j=0 このパターンのみ k=0 から k=1 への遷移になる。
      if string == "0":
        dp[i+1][0][1] = min(dp[i+1][0][1], dp[i][1][0])
      elif string == "1":
        dp[i+1][0][1] = min(dp[i+1][0][1], dp[i][1][0] + number)
      # j=1 -> j=1
      if string == "0":
        dp[i+1][1][k] = min(dp[i+1][1][k], dp[i][1][k] + number)
      elif string == "1":
        dp[i+1][1][k] = min(dp[i+1][1][k], dp[i][1][k])

      k = 1 # 一度 1-> 0 が起こったら以後は全て0にしないといけない
      # j=0 -> j=0        
      if string == "0":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][0][k])
      elif string == "1":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][0][k] + number)
      # j=1 -> j=0   
      if string == "0":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][1][k])
      elif string == "1":
        dp[i+1][0][k] = min(dp[i+1][0][k], dp[i][1][k] + number)
      
    tmp_ans = INF
    for i in range(2):
      for j in range(2):
        tmp_ans = min(tmp_ans, dp[-1][i][j])
    ans.append(tmp_ans)

for an in ans:
  print(an)
```

## まとめ
本番中にもこのやり方がほんの少し頭をよぎったのですが、DP に状態を持たせるなんてややこしそうだと思い敬遠してしまっていました。こういうのも解き慣れないといけません。余談ですがこういう DP を耳 DP というそうです。典型 90 問はある程度見たはずなのに頭から完全に抜け落ちていました。DP は奥が深いですね。