手動DPでOMC021Cを倒す

はじめに

皆さんこんにちは。OMC水のミカン小僧と申します。今回は、OMC021Cを通して、OMCの組み合わせ分野において度々使われる手動DPというテクニックを解説していきたいと思います。
この記事にはOMC021Cのネタバレが多分に含まれます。注意してお読みください。

手動DPとは？

「DP」とは、「動的計画法」という競技プログラミングのテクニックのことを指します。下の記事が分かりやすかったのでDPがよくわからない…という方はご覧ください。
うさぎでもわかるアルゴリズム　動的計画法 | 工業大学生ももやまのうさぎ塾 (momoyama-usagi.com)
OMCではコンピュータが使えないので、その代わりに自分の手でやろう、というのが手動DPです。

早速やってみよう！

OMC021Cは、以下のような問題です。
OnlineMathContest | For All Solvers
コインを10回投げ, 一度も表または裏が3回以上連続して出ない確率を求めるというものですね。これは私がまだ緑の時に2回挑戦して2回敗北した思い出の問題です。では早速手動DPをしていきましょう。分数が出てくるのは嫌なので、確率ではなく場合の数を求めます。
まずは下のような表を作ります。

DP表

ここで上の数字はコインを何回投げたか、表・裏というのは最後に投げた時のコインの向きを表します。
ではマスに数字を書き込んでいきましょう。
ここで下の表のように、1の下、表の右には1回コインを投げて、最後に投げたコインが表向きで、3回連続で同じ向きが出ることがないものの場合の数を書き込みます。これは当然1個だけですね。
以下、1の下、表の右のマス目のことを(1、表)と表します。

投げる回数が3回未満の時は、向きについて考えなくてよいのでそのまま書きましょう。

3回投げるときは、表表表と裏裏裏の2パターンがダメなので、表と裏からそれぞれ1ずつ引いてあげましょう。

さて、ここからが本題です。
まず、4回目に初めて3回連続になる場合の数のみを考えます。
最後に出たのが表のとき、コインの出方が？表表表となったら表が3連続出てしまいます。ここで、「初めて」3回連続になる必要があるので、？に入るのは1回コインを投げて、最後に投げたコインが裏向きで、3回連続で同じ向きが出ることがないものの場合の数となります。これは(1、裏)と一致しますね！
さて、3回コインを投げて、3回連続で同じ向きになることがない場合の数は$${3+3=6}$$ですね。この次に表を出すことをを考えると、4回コインを投げて、最後に投げたコインが表向きで、少なくとも3回目までは3回連続で同じ向きが出ることがないものの場合の数が6であることが分かります。これから4回目に初めて3回連続表になる場合を引けば、求めたい場合の数が得られるので、（4、表）には$${6-1=5}$$が入るわけです。
これを一般化すると、4以上の自然数Nについて
(N、表)に入る数は(N-1、表) + (N-1、裏) - (N-3、裏)
(N、裏)に入る数は(N-1、表) + (N-1、裏) - (N-3、表)
が言えます。
そこで、残りの表を埋めると次のようになります。

求める場合の数は(10、表) + (10、裏) = 178で、
$${\frac{178}{2^{10}} = \frac{89}{512}}$$より、$${89+512=601}$$と解答するとCAを得ます。

終わりに

今回はこの問題を手動DPで解きましたが、そのほかにもいろんな方法で解くことができる良問です。新しい方法を見つけたら、ぜひコメント欄で教えてください！
解説記事を書くのは初めてだったので、読み苦しいところが多々あったかもしれません。内容に対しての意見・感想などがございましたら、コメント欄やX(@perfect8128)のDMにお知らせください。
ここまでお読みいただきありがとうございました！