Educational Codeforces Round 69 Div2 B

内容

• Educational Codeforces Round 69 DIv2 B "Pillars" を解きました。
• python3

問題

本文

• N本の柱がある。(1~N)これらは、横一列に並んでいる。
• それぞれの柱には、半径 r_iの円盤が乗っている。
• 円盤は隣の柱に移動することができる。

• 円盤の移動には、以下の条件を満たす必要がある

  • 隣の柱にしか移動できない
  • 移動元の柱には、一つしか円盤が載ってない
  • 移動して重ねる時に、下の円盤よりも半径が小さくないといけない。

• 全ての円盤を一つの柱にまとめることができるか?

Input

N: 柱の数
A: それぞれの柱に乗っている円盤の半径
Aは全て異なる。

output

• 全ての円盤を一つの柱にまとめることができるなら"YES".
• そうでないなら"NO"

link

codeforces.com

考えたこと

• ハノイの塔かと思った。( 雰囲気はそんな感じ)
• 隣にしか移動できないから、ハノイの塔のようにはいかない
• 一番大きいやつに、大きい順に重ねていけば良い
• 他の円盤をまたいでの移動はできなさそう。

ポイント

• 一番大きいやつに、大きい順に重ねていく。
• すでに重ねた円盤は、連続した範囲になる。
• すでに重ねた範囲の、隣の円盤を次に重ねることができる。

実装

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
 
N = int(input())
L = list(map(int, input().split()))
L_sorted = sorted(L, reverse=True)
 
# 最大の円盤の柱があることろ。
max_ind = L.index(L_sorted[0])
#すでに重ねた範囲の左端と右端
left = max_ind-1
right = max_ind+1
 
ans = "YES"
#　大きい順に見ていって、全て重ねることができたらOK
# 一つでも重ねられないなら、NO

for l in L_sorted[1:]:
    # 左隣を重ねる。
    if left >= 0 and L[left] == l:
        left -= 1
　# 右隣を重ねる
    elif right < N and L[right] == l:
        right += 1
    # 両隣とも無理ならNO
    else:
        ans = "NO"
        break
print(ans)

　終わりに

• pillarは柱らしい。