AtCoderに登録したら解くべき過去問精選10問 #4【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginners Selectionのpythonでの解答の最後の記事です。

ABC049C - 白昼夢

atcoder.jp

問題文

英小文字からなる文字列Sが与えられます。
Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで
S=Tとすることができるか判定してください。

・Tの末尾に dream dreamer erase eraser のいずれかを追加する。

制約

・1≦|S|≦10^5
・Sは英小文字からなる。

解答例

# coding:utf-8

s = input()

string_divide = ["dream", "dreamer", "erase", "eraser"]

new_s = s[::-1]
new_divide = []
k = 0

for i in range(4):
    alt = string_divide[i]
    new_divide.append(alt[::-1])

can = True
for i in range(len(s)):
    can2 = False
    if k > i:
        continue
    for j in range(4):
        d = new_divide[j]
        if new_s[i:i + len(d)] == d:
            can2 = True
            k = i + len(d)
    if can2 == False:
        can = False
        break

if can == True:
    print("YES")
else:
    print("NO")

解説

Tに追加できる4つの単語は前から読むと
例えばdreamerの最後のerとeraseの最初のerがかぶり、
dreamとdreamerのどちらを用いるか判断が難しいです。
反対から読むと上記のような重なりがなくなるので、
new_divideリストに4つの単語を反対にした文字列を格納しました。
同様に入力sを反対にした文字列new_sを作成し、
for分内でnew_sがnew_divideと一致するか確認し、
すべて一致する場合のみcanフラグがTrueのままループを抜けるようになっています。
文字列の一致確認にはスライスを用いました。
便利な機能だと思いましたので、しっかりと使い方を覚えたいです。

ABC086C - Traveling

atcoder.jp

問題文

シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。
AtCoDeerくんの旅行プランでは、
時刻 0に点 (0,0)を出発し、1以上 N以下の各 iに対し、
時刻 tiに点 (xi,yi)を訪れる予定です。
AtCoDeerくんが時刻 tに点 (x,y)にいる時、
時刻 t+1には点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。
その場にとどまることは出来ないことに注意してください。
AtCoDeerくんの旅行プランが実行可能かどうか判定してください。

制約

・1≤N≤10^5
・0≤xi≤10^5
・0≤yi≤10^5
・1≤ti≤10^5
・ti < ti+1(1≤i≤N−1)
・入力は全て整数

解答例

# coding:utf-8

n = int(input().strip())

a = [[0, 0, 0]]
for i in range(n):
    b = list(map(int, input().strip().split()))
    a.append(b)

can = True

for i in range(n):
    dt = a[i+1][0] - a[i][0]
    dist = abs(a[i+1][1] - a[i][1]) + abs(a[i+1][2] - a[i][2])
    if dt < dist:
        can = False
    if dist % 2 != dt % 2:
        can = False

if can == True:
    print("Yes")
else:
    print("No")

解説

問題文から時刻tが1増加するごとにxかyのどちらか1のみ増加、あるいは減少します。
for分では点iから次の点(i+1)に到着するまでの時間dtと
xとyのそれぞれ何マスあるかを示す距離distを求めます。
tが1増加するごとに1マスしか動けませんので、
dtがdistより小さければ次の目的地に着くことはできませんのでcanフラグをFalseにします。
dtがdistより大きい場合、
distが偶数であれば行ったり来たりを繰り返して時刻tiで目的地に着くことができます。
distが奇数の場合、
時刻tiでは1マスずれた位置にしか存在できないので、このときもcanフラグをFalseにします。
canフラグがTrueのままループを抜ければYesを出力し、そうでなければNoを出力します。

これでAtCoder Beginners Selectionが一通り終わりました。
とんでもなく難しいプログラムを考えなくても大丈夫という印象ですが、
どんな場面でも問題なく答えにたどり着くロジックを考えることが大変だと感じました。
慣れもあると思いますので、今後もコンテストに多く出て経験を積みたいです。

精選10問のあとはこちらもおすすめ
ebisuke33.hatenablog.com

競技プログラミングの学習にはこちらの本もおすすめです。

リンク