ABC136 C - Build Stairs に苦しめられた

11229 ワード
AtCoder Python AtCoderBeginnerContest Python テキストリンク



サクッと、0,1,2,3,... と順番にやっていけば良くね？
そんな軽い気持ちが苦労の始まり。。

BuildStairs_r0.py
n = int(input())
X = list(map(int,input().split()))
from sys import exit

for j in range(n-1):# O(10^5)
    if X[j] > X[j+1]:
        X[j] -=1

for k in range(n-1):# O(10^5)
    if X[k] > X[k+1]:
        print("No")
        exit()
print("Yes")

なぜ、WA かわからない。ググってみも皆、後ろから試してる。。。
そんな自分に、救いの手が。。

test_case.py
#case1
4
1 2 2 1

#以下のケースも検討すべきだと思った。

#case2
4
1 3 3 2

上記をもとに再検討する。

BuildStairs_r0.py
n = int(input())
X = list(map(int,input().split()))
from sys import exit

for j in range(n-1):# O(10^5)
    if X[j] > X[j+1]:#分岐条件
        X[j] -=1
    #前述の分岐条件を抜けたとしても、X[j] を下げないと
    #エッジケースを切り抜くことが出来ない。
    elif X[j-1] <= X[j]-1:
        X[j] -=1

for k in range(n-1):# O(10^5)
    if X[k] > X[k+1]:
        print("No")
        exit()
print("Yes")

とおった(泣)。。なんで駄目だったか。分かって嬉しい。。

あれから時間が経って、すっかり忘れた状態で再チャレンジ
汚いコードだったが通った。素直に嬉しい。

abc136c.py
N = int(input())
H = list(map(int,input().split()))

#if 文で条件する場合、確実に分かることを少しずつ切り分けると
#整理しながら進めることが出来る。

REF = H[0]                             #Step1:比較する基準値、最初は H[0]
for i in range(N):                     
    if REF == H[i]:                    #Step2:基準値とH[i]が同じなら何もしなくて良い
        pass                           
    elif REF > H[i] and REF-H[i] > 1:  #Step3:基準値 > H[i] であり、かつ差分が 
        print("No")                    #      2以上なら手の施しようがない."No" として EXIT していい
        exit()                         
    elif H[i]-REF == 1:                #Step4:基準値とH[i]の差分が 1 なら引いておこう
        H[i] -= 1                      #      適当に見逃すと、コーナーケースを潰せない可能性が高い
    elif H[i]-REF > 1:                 #Step5:基準値とH[i]の差分が 2 以上なら、間違いなく
        H[i] -= 1                      #      H[i] -= 1 とした方がいい。じゃないと話が進まない(笑)
        REF = H[i]
#print(H)

for j in range(N-1):
    if H[j+1]-H[j]<0:
        print("No")
        exit()
print("Yes")