AtCoder Beginner Contest 413 E - Reverse 2^i
使用言語はPythonです。
問題のポイント
-
区間は長さが 2b2^b2b の連続部分であり、その区間を丸ごと反転できる。
-
反転の単位は自由に選べるが、区間の長さは必ず2のべき乗。
-
辞書順とは、順列を辞書式に並べたときの順番。
-
操作回数制限はなく、0回でもOK。
考え方のコツ
-
NNN が大きくなると全探索は不可能。
-
区間の反転をうまく利用して、部分列の辞書順を比較し、より小さい順序を選ぶ必要がある。
-
再帰的に配列を半分に分けて比較し、必要なら左右の半分を反転させて並べ替える方法が効果的。
コードの説明
-
search関数は渡されたリストを再帰的に半分に分割し、左右の最小値を比較して必要なら左右を反転。 -
こうすることで部分列ごとに辞書順が小さくなるように整え、最終的に全体の辞書順最小を求める。
コード例
T = int(input())
def search(lst):
b = len(lst)
if b == 1:
return lst
if min(lst[:b//2]) > min(lst[b//2:]):
lst.reverse()
return search(lst[:b//2]) + search(lst[b//2:])
for _ in range(T):
N = int(input())
P = list(map(int, input().split()))
ans = search(P)
print(*ans)
まとめ
-
問題は区間反転を使って辞書順最小を目指すもの。
-
再帰的に配列を左右に分けて比較し、反転を決める方法で解く。
-
2N2^N2N のサイズの配列を半分に分ける操作を繰り返すことで効率的に解決可能。
