AtCoder World Tour Finals 2019 E eを解いたのでメモ
こんにちは。
AtCoder World Tour Finals 2019のE問題である「e」をACしたので、解説と違う解き方をした部分を書き残しておきます。（まあ本質は一緒だと思いますが）
問題はこれ↓
https://atcoder.jp/contests/wtf19-open/tasks/wtf19_e
大まかな考え方や流れは公式解説と同じなので省きます。なので先にそちらを見ないと何のこっちゃだと思います。
DP部分が解説を見てもよく分からなくて唸っていたら自分なりの方法で何とかできたのでそこの部分を紹介します。
公式解説のDPは
dp[i][j][k][l] = 「X_i=xのとき、sのi番目まで条件を満たす確率、ただしj,k,lに応じた条件も付く」
というものでした。（正確にはdp[i][j][k][l](x)ですが(x)は省略して書きます）
考えた結果、添え字がiのみでDPが組めたので、以下で説明します。
簡単のため、sの両端は’X’（すなわち人が座る）とします。
dp[i] = 「X_i=xのとき、sのi人目（左から数えてi番目の’X’）まで条件を満たす確率」
とします。（0-indexedです）
まず、dp[0]=e^(-x)です。
dp[i]からdp[i+1]を求める時には次のようにします。
i人目と(i+1)人目の間の空席が1または2でないと確率は0となることに注意して下さい。
間の空席が1の時
X-X
のようになっています。
それぞれの確率変数をX_j, X_{j+1}, X_{j+2}とおくと、あり得る大小関係は
X_j < X_{j+1} < X_{j+2}
X_j < X_{j+1} > X_{j+2}
X_j > X_{j+1} > X_{j+2}
の3つです。（X_j > X_{j+1} < X_{j+2} だとj+1番目の席に人が座ってしまいます）
よって、dp[i+1]は
「dp[i]を<<の順で積分したもの」、「dp[i]を<>の順で積分したもの」、「dp[i]を>>の順で積分したもの」
の和となります。
ただし、「<で積分」と言ったら f(x) を ∫[0 to x]f(y)dy に、「>で積分」と言ったら f(x) を ∫[x to 1]f(y)dy にする操作だと思って下さい。
間の空席が2の時
X--X
のようになっています。
それぞれの確率変数をX_j, X_{j+1}, X_{j+2}, X_{j+3}とおくと、あり得る大小関係は
X_j < X_{j+1} < X_{j+2} > X_{j+3}
X_j < X_{j+1} > X_{j+2} > X_{j+3}
の2つです。（X_j > X_{j+1} と仮定するとj席目に人が座るためにはj+2席目に人が座らなければならず、矛盾します。他も同様。）
よって、dp[i+1]は
「dp[i]を<<>の順で積分したもの」、「dp[i]を<>>の順で積分したもの」
の和となります。
これらが連なった時も上手くいってるのか？と思ってしまいますが、上記の大小関係を満たしていればいくつ連なっていても目標の席配置になることが分かります。
この遷移によってdp[k]（右端に座る人をk人目とした）を求め、それにe^(-x)をかけて0から1まで積分すれば答えが求まります。（私は部分積分を実装しました）
さて、先ほど両端に人が座ると仮定しましたが、そうでない場合はどうすればよいでしょうか？
実はうまく両端に文字を追加することで解決できます。
例えばs="X--X-"だったとします。
この時、s1="X--X-X"とs2="X--X--X"について問題を解き、それらを足すことで元のsに対する答えが求まります。
実装においては、先頭に付ける候補"X", "X-", "X--"と末尾に付ける候補"X", "-X", "--X"の組み合わせを全て試して足し合わせることで場合分けをなくすことができます。
実際の提出はこれ↓（見せる用に書いたわけではないので参考程度に…）
https://atcoder.jp/contests/wtf19-open/submissions/10927232
終わり
数式の、書き方が、分からない。
この下手な説明で理解できる人は普通に公式解説を理解できると思います。
