「そんな方法どうやって思いつくの？」(ABC D問題、paizaSC A~S問題レベル)

※主にAtCoder Beginner Contestの**D問題**やpaizaスキルチェックの**A~S問題**で引っかかる人向けです。また、具体的なコードはほぼ書いていません。

競プロ始めたての友人にとある問題を解説しようと思った時の話をメモ書き。
毎度そうなのだけど、こういうのって考え方そのものを思いつく人と思いつかない人の間では結構な差がありそうですよね。思いつかない人にとっては、模範解答を見ても「何を考えてたらこんなこと思いつくの？」みたいな感じになって、仮にまねっこで書けたとしても次回また同じことに陥りがちで。

ある1問を例に、思いついている人の頭の中を軽く整理してできるだけわかりやすく書いてみます。
#まずは問題を読んでみよう
>###問題文
>長さ $d$ の机の中心に紙テープを貼り付けます。紙テープは両面が赤と青に塗り分けられています。
>紙テープには一列に $P_1$ から $P_n$ まで $n$ 個の点が打ってあり、点 $P_0$ は机の中心に貼り付けてあり、点 $P_n$ は紙テープの反対側の端にあります。また点 $P_i$ は点 $P_{i-1}$ から長さ $A_i$ だけ中心から離れた位置にあります。
>この紙テープを点が打たれている位置で折り返していくことを考えます。ただし、以下の条件を守るものとします。
>>・紙テープは点が打たれている位置でしか折り返すことができないが、点が打たれている位置で折り返すかどうかは任意である (折り返さなくてもよい)。
>>・紙テープの一部が机からはみ出してはいけない (机の端ちょうどの位置では折り返すことができる。つまり、紙テープ全体は中心から長さ $d$ までの位置に存在することができる)。

>以上の条件を満たす折り返し方をしたとき、点 $i-1$ と $i$ の間にある区間で、赤い面が表になっている全ての $i$ を1通り求めてください( $2\leq i \leq n$ )。赤い面が実際に見えているかどうかは考慮しないものとします。
>###制約
>$1 \leq d \leq 200$
>$1 \leq n \leq 2 \times 10^5$
>$1 \leq A_n \leq 2d$
>入力は全て整数
>###入力
>入力は以下の形式で標準入力から与えられる。
>$d\quad n$
>$A_2\quad A_3\quad ...\quad A_n$
>###出力
>全ての $i$ の積を、$mod(10^9 + 7)$ で出力してください。問題文に合う折り返し方がない時は $-1$ を、1度も折らずに条件を満たすことができる場合は $0$ を出力してください。条件に合う折り返し方が複数ある場合は、そのうちの1通りについて出力してください。

※元の問題がどれだかわからないように問題文は大幅に改変しています。改変したことで偽解法とか生まれてたらすいません。

どうでしょう？難しそうですか？
では始めましょう。**以下、「そのレベルは脱してるよ」と思ったらどんどん読み飛ばしてください。**引っかかっているレベルの所から読み始めてもらえればいいかなと思います。

#答えに辿り着けないタイプの思考2例
>どういう折り返し方ならはみ出ることなく折り曲げることができるか？を考える。

いかにも。それが言語化できればなんか書けそうですもんね。でもこれはおそらく上手くいきません。
##(失敗例)
**・ひたすら次の点ができるだけ机の中心に近くなるように折り返す。**
これは容易に反例が挙げられます。
>2 4
>1 1 4

$P_2$ を折り返してしまうと $P_3$ が机の中心に来てしまうので、ここを折り返しても折り返さなくても $P_4$ が机の外に出てしまいます。
うーん、残念！

※このケースの正しい出力は
>6 または 4

です。


**・折り返さなくても次の点まではみ出さないなら折り返さない。できるだけ机の中心から遠くなるように折り返す。**
これは結構やりそうな間違いです。
>2 5
>1 1 2 4

意地悪ですが、**$P_2$ ですぐに折り返す必要がないにもかかわらず、ここを折り返さないと $P_4$ の位置が机の端に来ない**ので、 $P_5$ がはみ出てしまいます。これがこの考え方における最小の例外ケースなので、もし想像がつかなかったら実際にやってみるとわかりやすいでしょう。

※このケースの正しい出力は
>8 または 15

です。

#全探索しようとすると何が起こるか
とりあえずforループで全探索を考えたあなた。ちょっと待ってください。
**[計算量オーダー](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)**について知っておきましょう。AtCoderの解説ではおなじみの $O(n)$ ってやつです。これについてはいろんなサイトで解説がされていると思うので、そちらを参照してきてください。

この問題を全探索すると、各点で折り返すか折り返さないかの2通りを選ぶことになるので、**状態数が$2^n$通りある**ことになります。

よって点 $n$ 個に対して計算量オーダーは $O(2^n)$になります ($P_1$ はどっちでも一緒なので $O(2^{n-1})$ でもいいのですが、些細な差なのでここではどうでもいいです)。
制約を確認すると、$n$ は $2 \times 10^5$ まで取りうるということなので、このコードを実行したが最後、あなたのパソコンは永遠の眠りに就きます( ~~$2^{2 \times 10^5}$が[どれくらいの数か](https://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%8C%E3%83%BC%E3%82%B9%E3%81%AE%E7%9F%A2%E5%8D%B0%E8%A1%A8%E8%A8%98)なんて聞かないでください。この記事全部使っても表現できません~~)。

つまり**全探索は無理**です。ちょっと考えるくらいならいいですが、試そうとは思わないでください。

#全探索が無理なら、じゃあどうするか
なぜ全探索が無理なのか？から考えてみましょう。
前項で指摘した通りなのですが、**状態数が$2^n$通りある**から無理なのです。でも、本当にそうなのでしょうか？
こんな入力例を考えてみましょう。
>100 200000
>2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 50 150 50 150 50 150 ... 50 150 1 1 1 1 1 1 1 1 1

(ほんの少し考えるかもしれませんが)ちょっと考えるだけで確実に条件を満たす答えはあるし証明もそれほど難しくはないことがわかると思います。ですが機械に全探索でやらせるとやっぱり無理なんですね。

考えなきゃいけないのは、**そもそも本当に状態数はそんなに多くなきゃいけないのか**ってとこです。

この例では最初に2が20個出てきます ~~(わざわざ数えた人ごめんね)~~。では、$P_{21}$ までの間の状態数はどれだけあるかというと、$2^{20}$ ではないんですね。
だってよく考えてみてください。**$P_{21}$ までの全ての点を折り返すか折り返さないか決めたあと、$P_{21}$ が存在する可能性のある地点が何通りあると思いますか？**そもそも机の長さが$2d \quad (= 200)$ しかないのに？

実際にはこの時点で状態数はたかだか11通りしかありません(対称性を考慮しています)。具体的な数字はさておき、どれだけテストケースが意地悪にできていて、ある点 $P_i$ まで折り返すかどうかを決めた後で、 $P_i$ **が机の上のあらゆる位置にいることができたとしても、その時点での状態数は $(d+1)$ 通りしかない**のです。

出力は答えのうち1通りで良いと言われていますから、異なる折り返し方をして点 $P_i$ が中心から距離 $d'$ の位置にいることができる折り方が1000通りあったとしても、全てまとめて1通りとしてしまってよいわけです。これは $1 \leq i \leq n$ を満たす全ての $i$ に対して言えることです。

つまり、状態数は $(d+1)n$ 程度しかありません。
この解き方だと計算量オーダーは$O((d+1)n)$なので、

$max((2d+1)n) \approx 4 \times 10^7$

現実的に実行可能そうです。めでたしめでたし。
#以上を踏まえて具体的に書こう
入力例として以下の例を考えます。
>2 5
>1 1 2 4

$n-1$ 回だけ繰り返すforループを作ります。
$2d+1$ 個の要素を持つ配列を2つ用意し、最初に $d+1$ 番目の要素だけを $0$、他を $-1$ か何かにしておきます。
非負の整数が入っているところは $i$ 回目まで折り返したときに点が存在する折り方を示しています。
もう片方は移動後の配列としてとりあえず全部-1にしておきます。
>{-1, -1, 0, -1, -1}
>{-1, -1, -1, -1, -1}

内側で $2d+1$ 回のforループを作ります。ある点 $P_i$を折り返すか折り返さないかすると、距離 $A_i$ だけ点が動くことになりますから、そこが配列の内側であれば、その位置に $i$ か $i$ を乗算した数を代入します( $0 \times i$ となってしまう場合は $i$ を代入してください。また、 $10^9 + 7$ を超えた場合、かわりに剰余を代入します)。
移動後の配列を移動前の配列に全てコピーして、同じ操作を繰り返します。
>$i=1$ のとき、
>{-1, -1, **0**, -1, -1}
>{-1, **1**, -1, **0**, -1}
>
>$i=2$ のとき、
>{-1, **1**, -1, **0**, -1}
>{**2**, -1, **2**, -1, **0**}
>
>$i=3$ のとき、
>{**2**, -1, **2**, -1, **0**}
>{**6**, -1, **3**, -1, **2**}
>
>$i=4$ のとき、
>{**6**, -1, **3**, -1, **2**}
>{**8**, -1, -1, -1, **3**}
>
>$i=5$ のとき、
>{**8**, -1, -1, -1, **3**}
>{**15**, -1, -1, -1, **8**}

以上の操作が完了した時、配列に非負の整数が残っていればそれを1つ出力します。
非負の整数が1つも残っていなければ $-1$ を出力します。
あるいは、最大値を出力、でもいいでしょう。

ACだ！やったー！

※計算量オーダーが $(d+1)n$ だと言ったのに配列長 $2d+1$ の配列を用意したのは、絶対値での計算が面倒な人向けです。もちろん配列長 $d+1$ で書くこともできます。また、int型の配列では大規模データでオーバーフローするのでlong型を使ってください。

#参考
[動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集](https://qiita.com/drken/items/dc53c683d6de8aeacf5a)　@drken 様