コンテンツにスキップ

DOJ Starter Contest 1 D - 수열 정렬하기 3

サイト
DOJ
コンテスト
DOJ Starter Contest 1
問題
D - 수열 정렬하기 3

長さ NN の整数列 AA に対し、「末尾の要素を先頭へ移す」「先頭の要素を末尾へ移す」という操作を何回でも行えます。数列を広義単調増加にできるか判定する問題です(N≤100N\le100)。

どちらの操作も数列を循環シフトする操作です。何回操作しても、要素の円環上での並び順は変わりません。逆に、先頭にする位置は自由に選べます。

よって、調べるべき数列は、各 i=0,1,…,N−1i=0,1,\dots,N-1 について先頭を ii 番目にした

A[i:] + A[:i]

の NN 通りだけです(0 始まり)。

あらかじめ s = sorted(A) を求め、いずれかの循環シフトが s と一致すれば YES、どれも一致しなければ NO を出力します。ソート済みの並べ方は同じ値を区別しなければ一意なので、この比較で判定できます。

各循環シフトの作成と比較に O(N)O(N) かかるので、計算量は O(N2)O(N^2) です。for に付いた else は、break せずにすべての候補を調べ終えた場合に実行されます。

Python
N = int(input())
A = list(map(int, input().split()))
s = sorted(A)
for i in range(N):
if s == A[i:] + A[:i]:
print("YES")
break
else:
print("NO")