Atcoder Beginners Selection コード解説[3]

記事の目的

　Atcoderの初心者向けの課題である「Atcoder Beginners Selection」のC問題のコードを解説していきます。より良い解法など、コメントお待ちしております。

ABC085C - Otoshidama

問題文

日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

　~~うらやまし～！！！！~~
　お札の枚数が指定されていて、金額がその枚数で実現できるかどうか判定するといった問題です。　はじめはそれぞれのお札の枚数について３重ループを組んでみましたが、TLE（タイムアウト）してしまいました。　この問題は３重ループを２重ループにすることが出来ます。

　問題を数式化するとこうなります。これを満たすx, y, zを１組見つけるという問題ですね。
この連立方程式が成り立つとすると、変数を一つ消すことが出来ます。
それを踏まえて、実行したコードがこちらになります。

n, y = map(int, input().split(" "))
flag = False
for i in range(n+1):
    for j in range(n+1):
        if i + j <= n:
            k = n - (i + j)
            if 10000*i + 5000*j +1000*k == y:
                print("{} {} {}".format(i, j, k))
                flag = True
                break
    else:
        continue
    break
if flag == False:
    print("{} {} {}".format(-1, -1, -1))

変数が1つ消えたので、2重ループで解を見つけ、見つけ次第処理を打ち切っています。また、処理終了まで解が見つからなかった場合は(-1, -1, -1)が出力されるようになっています。

ABC049C - 白昼夢

問題文

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

　一見簡単そうですが、文字列を前から検索してdreamerという文字が出てきた場合、それがdreamerなのかdream + eraseなのかがわかりません。　そこでこの場合は、文字列を後ろから探索します。

s = input()
 
s_reversed = s[::-1]
tmp_s = s_reversed
 
while len(tmp_s) > 0:
    if tmp_s[0:5] == "maerd":
        tmp_s = tmp_s[5:]
    elif tmp_s[0:5] == "esare":
        tmp_s = tmp_s[5:]
    elif tmp_s[0:6] == "resare":
        tmp_s = tmp_s[6:]
    elif tmp_s[0:7] == "remaerd":
        tmp_s = tmp_s[7:]
    else:
        print("NO")
        break 
if len(tmp_s) == 0:
    print("YES")

私の実装では、後ろから探索する代わりに、文字列を反転させて、前から探索しています。もちろん見つけ出す文字もdreamがmaerdのように反転することになりますが、探索する文字が部分的に一致するというようなことが起こりません。

また、Pythonでは文字列の反転が、s[::-1]で簡単にできます。

ABC086C - Traveling

問題文

シカの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くんの旅行プランが実行可能かどうか判定してください。

AtCoDeer君！AtCoDeer君じゃないか！！
AtCoDeer君が座標平面上を移動して、ある時刻にある点に存在できるかを判定するという問題です。その場にとどまることはできませんが、時刻を2つ使って行ったり来たりすることはできます。
つまり、自分の今いる点から目的の点まで、最短何時刻で行けるかを求めたうえで、指定された時刻と最短時刻の差が偶数なら実行可能といえます。

s = input()
 
t_list = []
x_list = []
y_list = []
 
for i in range(int(s)):
    t, x, y = map(int, input().split(" "))
    t_list.append(t)
    x_list.append(x)
    y_list.append(y)
 
now_time = 0
place_x = 0
place_y = 0
flag = True
 
for i in range(len(t_list)):
    t = t_list[i] - now_time
    dis_x = abs(x_list[i] - place_x)
    dis_y = abs(y_list[i] - place_y)
 
    if dis_x + dis_y <= t and (t- dis_x - dis_y) % 2 == 0:
        place_x = x_list[i]
        place_y = y_list[i]
        now_time = t_list[i]
    else:
        flag = False
if flag == True:
    print("Yes")
else:
    print("No")

今いる場所から指定された場所まで向かうための、最短時刻は以下の図のように算出できます。

おわりに

　今回はABCのC問題について解説しました。これでABCは終了しましたので、次は競プロ典型90にチャレンジしてみようと思います。

中百舌鳥雑記組

競技プログラミングを始めてみました。過去問や勉強したことをまとめていきます。