伯準Z(分割征服)

アルゴリズムタイプ:分割征服
一人で解けたの?O
浴室床にタオルを敷く問題を解決した後は、それほど難しくはありませんでしたが、最初は問題のまま耳で解こうと思っていたので、それを並べて中で値上げしましたが、Nは15まで大きくなってしまい、そうするとタイムアウトになるので、この方法で解くことにしました.

問題を解く

0 | 1
_ _
2 | 3
各象限の数字が上の数字と同じであれば、Zの形を探索するのが0象限です(ちょっとおかしいですが、後に解に乗じた数字が0なので、そうします)->1斜面->2斜面->3斜面順探索,再帰関数を用いて実現できるかどうかわからない場合は,問題中の画像を見たり,画像を見たりして感覚が得られるが,いずれにしても
でもさっき言ったようにここに直接並ぶとタイムアウトになります.従って,divide関数は再帰的に深く入り込み,各ステップが与えられた(r,c)がどの象限にあるかを理解する関数を実現した.次に、各ステップで最左上隅に位置する要素の値を求め、rst上で累積し、関数に渡し、正方形のエッジの長さが2の場合、rst上に積分値を返します.
(r,c)が何象限に位置することを求めます
この象限の最左上隅値の要素rst+=値を次の再帰に転送します.
Basecase:n=1は1辺の長さが2であることを示す.
(r,c)が0象限の場合-これまでの累計値+0に戻る
(r,c)が1象限の場合-これまでの累計値+1に戻る
(r,c)が2象限の場合-これまでの累計値+2に戻る
(r,c)が3象限の場合-これまでの累計値+3に戻る
なぜ+0、1、2、3を返すのか、なぜ最左上隅の値を積算するのか、質問付きの図を見てください.すぐに理解できます222

import sys

n, r, c = map(int, sys.stdin.readline().split())


def divide(n, x, y, rst):
    xm = (x+x+pow(2, n)-1) // 2
    ym = (y+y+pow(2, n)-1) // 2

    if (n == 1):
        if (xm >= r and ym >= c): return rst
        elif (xm >= r and ym < c): return rst+1
        elif (xm < r and ym >= c): return rst+2
        elif (xm < r and ym < c): return rst+3
    
    if (xm >= r and ym >= c): return divide(n-1, x, y, pow(pow(2, n-1), 2)*0 + rst)
    elif (xm >= r and ym < c): return divide(n-1, x, ym+1, pow(pow(2, n-1), 2)*1 + rst)
    elif (xm < r and ym >= c): return divide(n-1, xm+1, y, pow(pow(2, n-1), 2)*2 + rst)
    elif (xm < r and ym < c): return divide(n-1, xm+1, ym+1, pow(pow(2, n-1), 2)*3 + rst)

print(divide(n, 0, 0, 0))

注目すべきは、rの座標とcの座標、すなわちx座標とy座標の比較基準値が異なる(xm、ymのように2つの変数が必要)ことです.この2つの変数を求めるには、正方形の辺長と最も左上の要素のxが必要です.y座標値が必要です.エッジの長さが8のとき(4,0)がどこにあるかを求めてみると、わかります.
この部分はシャワーブースの床を塗る問題でもミスがあり、ここでも似たようなミスが残っています