Euler.net – 327- Rooms of Doom 解き方

3つの部屋は1列で自動ドアによって互いに繋がっています。 各ドアは、セキュリティ・カードにより操作されます。部屋に入るとドアが自動的に閉じ、そのセキュリティカードを再度使用することはできません。開始時、カードの数に制限を分配しますが、各部屋(出発室にも)には、スキャナが含まれており、最大3つのカードしかを持てる。各部屋には、セキュリティカードの任意の数を格納することができるボックスがあります。 単に一度部屋1を通過しようとした場合は、部屋3に入ると、あなたはすべてのカードを3枚使用しているだろうと永遠にその部屋に閉じ込められたことになります。 ただし、収納ボックスを利用する場合は、エスケープが可能です。たとえば、あなたは、あなたの最初のカードを使用して、部屋1を入力収納ボックス内の1つのカードを配置し、出発室に戻ってまた3枚のカードを得る。あなたは部屋1に入って、ボックスにあるカード1枚を得る。これで、再びカードを3枚持っていると、残りの3つのドアを通って移動することができるようになります。この方法では、合計で6セキュリティカードを使用して、すべての3つの部屋を通って移動することができます。 これは、3枚が持てるカードを最大値だとすると、123枚のカードを使ったら、6室を通って移動することが可能です。 Cは、任意の時点で実施することができるカードの最大数とします。 Rが通過する部屋の数とします。 M(C、R)は、いつでもCカードの最大値まで運ぶのR部屋を通過する必要なカードの最小数とします。 例えば、M(3,6)=123、M(4,6)= 23 そして、ΣM(C、6)= 3≤C≤4のための146。 ΣM(C、10)= 3≤C≤10のための10382。 3≤C≤40のためΣM(C、30)は? こんな問題です。 この問題はDP(Dynamic Programming)問題です。 簡単に例でM(4,6)から考えます。説明をため出発室は部屋0、1番目の部屋は部屋1などで言います。もし部屋1のボックスに部屋2〜最後の部屋まで行けるカードがあったら私たちはまた部屋0にもどらなくてもいいです。部屋2〜最後の部屋まで行くため必要なカードの数はM(4,6-1)です。(部屋1を無視するので部屋の数が1減る) M(4,6) = M(4,5) + (カードM(4,5)枚を部屋1に移すために必要なカードの数) + 1 です。(移す事が終わった後で最後の1は部屋0から部屋1まで行くため) (カードM(4,5)枚を部屋1に移すために必要なカードの数) は 簡単に計算ができます。 もしカードを最大N枚を持てるとすると、1回にカードはN-2枚移す事ができます。(2個は部屋に移動するため使うので)また実はカードをM(4,5)枚じゃなくてM(4,5)-(c-1)枚だけ移ったらいいです。(M(4,5)-(3)] / [2])回動くとカードは全部移れます。でも回数は自然数だけなのでceilを使います。ex) 3.7回 → 4回 M(4,6) = M(4,6) + 1 + 2*ceil([M(4,5)-(3)] / [2]) です。 M(c, r) = M(c,r-1) + 1  + 2*ceil([M(c,r-1)] – (c-1)] / [c-2]) です。 もし…

Euler.net – 287- Quadtree encoding 解き方

問題 quadtree encodingは(0 1)ビットのシーケンスとして2^N×2^N白黒画像を記述することができます。これらの配列は、このように左から右読みます 1番目のbitはcomplete 2^Nx2^N領域によって 「0」の時は、分割を表し: 2nの地域×2nの電流は、2N-1×2N-1次元の4つのサブ領域に分割され 次のビットは、左上、右上、左下と右下のサブ領域の説明含まれています。 「10」は、現在の領域は全部黒。 「11」は、現在の領域は全部白。 正の整数Nの場合は、以下の方式に2Nの画像×2NとしてDNを定義します。 座標を持つ画素は、X = 0、Y = 0は、左下から (X – 2^(N-1))^2 +(y – 2^(N-1))^2≤2^(2N-2)時は黒以外は白です D24を説明する最小の配列の長さは何ですか?   こんな問題です。 一応上の式が表すimageが何かわかるため これを実行します。numが3や4、5ぐらいで実行するとこの式が円ぽっいです。または(x-r)^2+(y-r)^2=r^2 この式を中学校の時みたごとがありますよね。円の中心が(r,r)半径がrの円の式です。rが2^(N-1)だと思うとこの式が円と思えます。一応この2つの方法でこの式が円とするごとがわかったらあとは簡単です。(違うかも) 上のcodeをnumが12ぐらいで実行すると時間がめっちゃかかります。大略しても4000×4000の配列をまたずっと計算するごとは無理です。24は絶大無理。この問題はこれを計算する問題じゃないと思います。そうするとうちがわかった「円」を使います。 簡単にするため円を4つの部分で分ける。左上から時計回りで1、2、3、4で呼ぶ。1だけ見るとこんな感じになります。この部分は白は全部左上で黒は全部右下にあります。これを見ると1の中ではもし一番左上が白なら全部白になるし、一番右下が黒なら全部黒になる事をわかります。例を見ると もしこんなimageがあるとします。最初は左上(1)を見ると黒じゃないし右下(4)を見ても白じゃないです。そうするとこのimageを4つで分けると左と右のimageと他の2個のimageが出ます。左のimageを見ると右下(4)が白なので全部白、右のimageは左上(1)が黒なので全部黒になる事を分かれます。これを利用するとこの問題はdivide conquer を利用して解けることをわかります。 divide_1は1の部分のimageをcompressする関数です。 divide_1(0,0,pow(2,num-1),pow(2,num-1))をすると1部分だけのcompress結果が出ます。これを利用してdivide_2,3,4を作ると結果が出ます。でもまだ計算量が多いので減るため この部分を追加、colorは変形します。 また私たちがわかりたいのは長さなので divide部分を変えます。 これを追加すると結果が出ます。(361sかかりました) このぐらいやっても早くないですが、もうちょっと出来るからって思ってやると def up(x): return int(round(x + 0.5)) def down(x): return int(round(x – 0.5)) で変えます。floatよりはintが早いです。361s → 357s 4秒減りました。 def…