DOJ Starter Contest 1 D - 수열 정렬하기 3
- サイト
- DOJ
- コンテスト
- DOJ Starter Contest 1
- 問題
- D - 수열 정렬하기 3
長さ の整数列 に対し、「末尾の要素を先頭へ移す」「先頭の要素を末尾へ移す」という操作を何回でも行えます。数列を広義単調増加にできるか判定する問題です()。
どちらの操作も数列を循環シフトする操作です。何回操作しても、要素の円環上での並び順は変わりません。逆に、先頭にする位置は自由に選べます。
よって、調べるべき数列は、各 について先頭を 番目にした
A[i:] + A[:i]の 通りだけです(0 始まり)。
あらかじめ s = sorted(A) を求め、いずれかの循環シフトが s と一致すれば YES、どれも一致しなければ NO を出力します。ソート済みの並べ方は同じ値を区別しなければ一意なので、この比較で判定できます。
各循環シフトの作成と比較に かかるので、計算量は です。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") breakelse: print("NO")