こんにちは
今回の学びは
・状態を考え、２連続という制約から、最後の文字はなにか？というDPへの発想に繋げられるか？が重要なポイント
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
この問題はめちゃめちゃ考えました。
そして自力では答えはでませんでした。３日間くらい考えたと思います。
最初は、入力で遅刻は２回以内ならOKという勘違いをしており、それも時間ロスにつながったので
問題文を正しく理解することは、とっても大事です！正しくは遅刻は２回連続以内であればOK!です。
の方の解説を何度も見てようやく分かりました。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
最初は、すんなりAとLにペナルティを数値化してナップサックで解けばいいのでは、と発想して
ふうに考えます
が
どうもうまくいかなさそう。
というか、今から考えるとドツボにハマっています。スプレッドシートを書くのに何時間かかっとんねん、と苦笑いです。
これだけ進まないと、ボツ案の兆しかもしれませんね。
といことで
選択の木を描きまくってイメージを定着させて、ひらめきを待ちます。
3^Nの木はおおきですねー
ってこの辺で
諦めてDISCUSS見ました。
で
彼の解説は秀逸です。
Let's say we have three arrays,
A[i] is the number of valid records that end with 'A' with length i
P[i] is the number of valid records that end with 'P' with length i
L[i] is the number of valid records that end with 'L' with length iLet's discuess P[i] first:
if the i day is 'P', then the i-1 day can be 'P' or 'A' or 'L'.
so P[i] = P[i-1]+A[i-1]+L[i-1]Then L[i]
if the i day is 'L', then i-1 day can be 'P' or 'A' or 'L', but when i-1 day is 'L', we need to avoid three are three consecutive L in the records, which means the i-2 day cannot be 'L', thus when i-1 day is 'L', the i-2 day can only be 'P' or A
so L[i] = P[i-1] + A[i-1] + P[i-2] + A[i-2]Then A[i], which is a little bit complex
Lが二連続という制約に初めて気がつく！？これは入力をしっかり抑えましょう。とう基本に反していますので反省すべき点でした。
と、それらしい価値関数と方策関数の設計は自分なりにしたのですが、
問題を解くことはできませんでした。
下のノートのように、最後の文字列が〇〇でかつ、報酬OKなレコード数、とう価値関数を３つ集めて初めてDPを作るのです！
これに関しては、もはや表（二次元表）ではない世界です！
だからこそ、理解できていないのです！
pseudocode（擬似コード）をかいてみますか。
最終的には、こういう疑似を丁寧にかける必要がある。
実際の実装はこちら
。。。
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
状態を考え、２連続という制約から、最後の文字はなにか？
というDPへの発想に繋げられるか？が重要なポイントと分析しています。
modをすべてのdpに入れないと n=100000の時にMemory Limit Exceededとなりました。
なんでだろう。。dpの配列サイズは変わらないのに、と思っていたのですが、これはdp[i][j]に入る値の大きさが大きすぎて
32bit,64bit pythonの場合それ以上、integerのサイズに上限がない形でも保持できてしまうためでした。
この辺はpythonのしくみでintergerが無限に表現できる、というところので説明でしています。（todoリンクをはろう）
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
最後が何で終わってできるOKなパターン数のDPの合計という
新しいDPにであいました。
まとめ
・状態を考え、２連続という制約から、最後の文字はなにか？というDPへの発想に繋げられるか？が重要なポイント
以上です