いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 552 student attendance ii

投稿日:

こんにちは

今回の学びは

状態を考え、2連続という制約から、最後の文字はなにか?というDPへの発想に繋げられるか?が重要なポイント

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

この問題はめちゃめちゃ考えました。

そして自力では答えはでませんでした。3日間くらい考えたと思います。

最初は、入力で遅刻は2回以内ならOKという勘違いをしており、それも時間ロスにつながったので

問題文を正しく理解することは、とっても大事です!正しくは遅刻は2回連続以内であればOK!です。

 

https://leetcode.com/problems/student-attendance-record-ii/discuss/431896/Java-solution-with-intuitive-explanation-(easy-to-understand)

の方の解説を何度も見てようやく分かりました。

 

実装前後でこれは毎回書きましょう。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 i

Let'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なレコード数、とう価値関数を3つ集めて初めてDPを作るのです!

これに関しては、もはや表(二次元表)ではない世界です!

だからこそ、理解できていないのです!

 

pseudocode(擬似コード)をかいてみますか。

 

最終的には、こういう疑似を丁寧にかける必要がある。

実際の実装はこちら

。。。

実装後です。timespace analysis (時間とスペースの分析)は ◯◯

状態を考え、2連続という制約から、最後の文字はなにか?

というDPへの発想に繋げられるか?が重要なポイントと分析しています。

 

modをすべてのdpに入れないと n=100000の時にMemory Limit Exceededとなりました。

なんでだろう。。dpの配列サイズは変わらないのに、と思っていたのですが、これはdp[i][j]に入る値の大きさが大きすぎて

32bit,64bit pythonの場合それ以上、integerのサイズに上限がない形でも保持できてしまうためでした。

この辺はpythonのしくみでintergerが無限に表現できる、というところので説明でしています。(todoリンクをはろう)

 

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

最後が何で終わってできるOKなパターン数のDPの合計という

新しいDPにであいました。

 

まとめ

状態を考え、2連続という制約から、最後の文字はなにか?というDPへの発想に繋げられるか?が重要なポイント

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.