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が何かわかるため

스크린샷 2016-01-25 오후 6.17.28.png

これを実行します。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は絶大無理。この問題はこれを計算する問題じゃないと思います。そうするとうちがわかった「円」を使います。

20160125_183604.jpg

簡単にするため円を4つの部分で分ける。左上から時計回りで1、2、3、4で呼ぶ。1だけ見るとこんな感じになります。この部分は白は全部左上で黒は全部右下にあります。これを見ると1の中ではもし一番左上が白なら全部白になるし、一番右下が黒なら全部黒になる事をわかります。例を見ると20160125_184549.jpg

もしこんなimageがあるとします。最初は左上(1)を見ると黒じゃないし右下(4)を見ても白じゃないです。そうするとこのimageを4つで分けると左と右のimageと他の2個のimageが出ます。左のimageを見ると右下(4)が白なので全部白、右のimageは左上(1)が黒なので全部黒になる事を分かれます。これを利用するとこの問題はdivide conquer を利用して解けることをわかります。스크린샷 2016-01-25 오후 6.54.59.png

divide_1は1の部分のimageをcompressする関数です。

divide_1(0,0,pow(2,num-1),pow(2,num-1))をすると1部分だけのcompress結果が出ます。これを利用してdivide_2,3,4を作ると結果が出ます。でもまだ計算量が多いので減るため스크린샷 2016-01-25 오후 6.59.00.png

この部分を追加、colorは変形します。

また私たちがわかりたいのは長さなので

스크린샷 2016-01-25 오후 7.00.37.png

divide部分を変えます。

스크린샷 2016-01-25 오후 7.05.05.png

これを追加すると結果が出ます。(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 divide_1(start_x, start_y, end_x, end_y):
    if color(end_x, end_y) == 0:
        return 2
    elif color(start_x, start_y) == 1:
        return 2
    elif end_x-start_x == 1 and end_y-start_y == 1:
        return 9
    else:
        middle_x = (start_x + end_x) / 2
        middle_y = (start_y + end_y) / 2
        return 1 + divide_1(start_x, start_y, down(middle_x), down(middle_y)) \
               + divide_1(up(middle_x), start_y, end_x, down(middle_y)) \
               + divide_1(start_x, up(middle_y), down(middle_x), end_y) \
               + divide_1(up(middle_x), up(middle_y), end_x, end_y)

おお234sになりました。計算が一番よく出る部分は2×2の部分だと思って2×2の場合まで行くとその下は計算しなくて9をreturnしました(私たちはcompress配列をわかるためじゃなくてただ長さだけわかったらいいので)。

print 1 + ans_1 + 2*ans_2 + ans_4

2と3部分は一緒なのでこれができます。ans_3 == ans_2です。これをやると174s

ここで終わりです。これをCで変えると 1~2秒以内になると思います。もっといい方法を知ってる人はコメントで教えてください。

 

全体コードです

def binaray_pow(num):
    return 1 << num


r = binaray_pow(num - 1)
r_2 = binaray_pow(2 * num - 2)


def color(x, y):
    # return 1 if (pow(x-pow(2,num-1),2)+pow(y-pow(2,num-1),2) <= pow(2,2*num-2)) else 0
    return 1 if (pow(x - r, 2) + pow(y - r, 2) <= r_2) else 0


def up(x):
    return int(round(x + 0.5))


def down(x):
    return int(round(x - 0.5))


def divide_1(start_x, start_y, end_x, end_y):
    if color(end_x, end_y) == 0:
        return 2
    elif color(start_x, start_y) == 1:
        return 2
    elif end_x-start_x == 1 and end_y-start_y == 1:
        return 9
    else:
        middle_x = (start_x + end_x) / 2
        middle_y = (start_y + end_y) / 2
        return 1 + divide_1(start_x, start_y, down(middle_x), down(middle_y)) \
               + divide_1(up(middle_x), start_y, end_x, down(middle_y)) \
               + divide_1(start_x, up(middle_y), down(middle_x), end_y) \
               + divide_1(up(middle_x), up(middle_y), end_x, end_y)


def divide_2(start_x, start_y, end_x, end_y):
    if color(start_x, end_y) == 0:
        return 2
    elif color(end_x, start_y) == 1:
        return 2
    elif end_x-start_x == 1 and end_y-start_y == 1:
        return 9
    else:
        middle_x = (start_x + end_x) / 2
        middle_y = (start_y + end_y) / 2
        return 1 + divide_2(start_x, start_y, down(middle_x), down(middle_y)) + divide_2(up(middle_x), start_y, end_x,
                                                                                         down(middle_y)) \
               + divide_2(start_x, up(middle_y), down(middle_x), end_y) + divide_2(up(middle_x), up(middle_y), end_x,
                                                                                   end_y)


def divide_4(start_x, start_y, end_x, end_y):
    if color(start_x, start_y) == 0:
        return 2
    elif color(end_x, end_y) == 1:
        return 2
    elif end_x-start_x == 1 and end_y-start_y == 1:
        return 9
    else:
        middle_x = (start_x + end_x) / 2
        middle_y = (start_y + end_y) / 2
        return 1 + divide_4(start_x, start_y, down(middle_x), down(middle_y)) + divide_4(up(middle_x), start_y, end_x,
                                                                                         down(middle_y)) \
               + divide_4(start_x, up(middle_y), down(middle_x), end_y) + divide_4(up(middle_x), up(middle_y), end_x,
                                                                                   end_y)


ans_1 = divide_1(0, 0, binaray_pow(num-1) - 1, binaray_pow(num-1) - 1)
print ans_1
ans_2 = divide_2(binaray_pow(num-1), 0, binaray_pow(num) - 1, binaray_pow(num-1) - 1)
print ans_2
ans_4 = divide_4(binaray_pow(num-1), binaray_pow(num-1), binaray_pow(num) - 1, binaray_pow(num) - 1)
print ans_4

# print len(ans_1)+len(ans_2)+len(ans_3)+len(ans_4)


print 1 + ans_1 + 2*ans_2 + ans_4
Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

w

%s에 연결하는 중