paizaラーニング問題集「平方分割」を解いてみた

▼感想：

区間(l,r)が、分割した中に存在する場合と、存在しない場合で、
分けて考えました。

後者の場合は、左端lからl2を計算します。
左端l、l2、右端rの位置関係を場合分けして、
最大の要素の値を求めるやり方にしました。

計算量を考えてプログラムを組む、ということを
ものすごく意識させられた問題でした。

▼コード：

########## 処理0(準備) インプット,リスト定義など ###########

K = int(input())

# tmp: 最大の要素の値を求める際に、利用するリスト
# maxdata: 分割した中の最大の要素の値を、格納する辞書
A = []
tmp = []
maxdata = {}

########## 処理1 配列Aを分割し、分割した中の最大の要素の値を求める ##########

import math
N = int(math.sqrt(10000))

for i in range(10000):

    tmp.append(int(input()))

    if len(tmp) == N:
        maxdata[i+1] = max(tmp)
        A.extend(tmp)
        tmp.clear()

########## 処理2 区間(l,r)に応じて最大の要素の値を求める ##########

for _ in range(K):

    l,r = map(int,input().split())

    l -= 1
    r -= 1

    ########## 処理2.1 区間(l,r)が分割した中に存在する場合の処理 ##########

    if r-l+1 < N:
        for i in range(l,r+1):
            tmp.append(A[i])

    ########## 処理2.2 区間(l,r)が分割した中に存在しない場合の処理 ##########

    else:
        # 左端lから、l2を計算
        l2=((l//100)*100)+99

        # 左端lとl2が、分割した中に存在する
        if l2-l+1 < N:
            for i in range(l,l2+1):
                tmp.append(A[i])

        # 左端lとl2が、分割した中に存在しない
        else:
            tmp.append(maxdata[l2+1])

            # l2を、次の、分割した中に移動させる
            l2 += N

            # l2と右端rの位置関係を場合分け
            while True:

                if l2-r == N:
                    break

                elif l2-r == 0:
                    tmp.append(maxdata[l2+1])
                    break

                elif l2-r > 0 and l2-r < N:
                    l2 -= N
                    for i in range(l2+1,r+1):
                        tmp.append(A[i])
                    break

                elif l2-r < 0:
                    tmp.append(maxdata[l2+1])
                    l2 += N

        print(max(tmp))
        tmp.clear()