2019-06-10に投稿

Pythonで競プロ|ABC129C|

AtCoder Beginner Contest 129CをPythonで解く

今回は、AtCoder Beginner Contest 129C
を解いていきたいと思います。

問題文

N段の階段があります。高橋君は現在、上り口(0段目)にいます。 高橋君は一歩で 1段か 2段上ることができます。ただし、a1,a2,a3,...aM段目の床は壊れており、その段に足を踏み入れることは危険です。

壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか? 総数を1,000,000,007で割った余りを求めてください。

こう考えた

  • 数字が連続した場合は移動方法がなくなり0になる。
  • a1段目までの登り方×a1からa2段目までの登り方×...となる。

実装したコード

N,M=map(int,input().split())
A=[]
for i in range(M):
  a=int(input())
  A.append(a)
print(A)
##連続していないかチェック
if M>1:
  for i in range(M-1):
    if A[i]+1==A[i+1]:
      print("No")
      break
step=0
for a in A:
  B=a-1-step
  for b in range(B):

結果

ここで時間切れでした。

🐍なんでや!!

勉強になったコード

N, M = list(map(int,input().split()))

b = [0]*(N+2)
b[0] = 1

for i in range(M):
  b[int(input())] = -1

for i in range(N):
  if b[i] != -1:
    if b[i+1] != -1:
      b[i+1] += b[i]
    if b[i+2] != -1:
      b[i+2] += b[i]

print(b[N]%1000000007)

# 入力は以下で行う
# 6 1
# 3

出力を見ていく

N, M = list(map(int,input().split()))

b = [0]*(N+2)
b[0] = 1

print(b)

# [1, 0, 0, 0, 0, 0, 0, 0]
N, M = list(map(int,input().split()))

b = [0]*(N+2)
b[0] = 1

for i in range(M):
  b[int(input())] = -1

print(b)

# [1, 0, 0, -1, 0, 0, 0, 0]
N, M = list(map(int,input().split()))

b = [0]*(N+2)
b[0] = 1

for i in range(M):
  b[int(input())] = -1

for i in range(N):
  if b[i] != -1:
  # b[i]が-1でないなら以下の2つの処理を行う
    if b[i+1] != -1:
      b[i+1] += b[i]
    if b[i+2] != -1:
      b[i+2] += b[i]
#[1, 1, 0, -1, 0, 0, 0, 0]
#[1, 1, 1, -1, 0, 0, 0, 0]
#[1, 1, 2, -1, 0, 0, 0, 0]
#[1, 1, 2, -1, 2, 0, 0, 0]
#[1, 1, 2, -1, 2, 2, 0, 0]
#[1, 1, 2, -1, 2, 2, 2, 0]
#[1, 1, 2, -1, 2, 2, 4, 0]
#[1, 1, 2, -1, 2, 2, 4, 2]

1回目のループはb[0]=1です。
+ b[1]=0ですのでb[1]b[0]+b[1]で1が入ります。
+ b[2]=0ですのでb[2]b[2]+b[0]で1が入ります。
2回目のループはb[1]=1から始まります。
+ b[2]=1ですのでb[2]b[2]+b[1]で2が入ります。
+ b[3]=-1ですのでb[3]に対して何も行いません。
3回目のループはb[2]=2から始まります。
+ b[3]=-1ですので何も行いません。
+ b[4]=0ですのでb[2]+b[4]で2が入ります。
4回目のループはb[3]=-1から始まります。
+ b[3]=-1ですので何も行いません。
5回目のループはb[4]=2から始まります。
+ b[5]に2が入ります。
+ b[6]に2が入ります。
6回目のループはb[5]=2から始まります。
+ b[6]に4が入ります。
+ b[7]に2が入ります。

これで得た配列の後ろから2番目を表示すれば正解です。

勉強になったコード

N,M = map(int, input().split())
As = [1] *( N+1)
for _ in range(M):
    i = int(input())
    As[i] = 0

for i in range(N-1):
    if As[i+2] > 0:
      As[i+2] = As[i+1] + As[i]

mod = 10**9+7
print(As[-1]%mod)

コードを読む

As = [1] *( N+1)
for _ in range(M):
    i = int(input())
    As[i] = 0

ここで階段を[1,1,1,1,0]という形で表現する。

    if As[i+2] > 0:
      As[i+2] = As[i+1] + As[i]

2段先が0で無ければ、2段先に1段先と現在の段の数値を足したものを代入する。

🐍ポイントは3段先を読むという形に問題文を小分けにすることやったんやな。

Originally published at www.coderecipe.org

view_list Pythonで競プロ
第1回 Pythonで競プロ|ABC129A|
第2回 Pythonで競プロ|ABC129B|
第3回 Pythonで競プロ|ABC129C|
第4回 AtCoder Beginner Contest 073CをPythonで解く
第5回 AtCoder Beginner Contest 095CをPythonで解く

aocory

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

関連記事

コメント