AtCoderに登録したら解くべき精選過去問10問の嘘解法

AtCoderに登録したら解くべき精選過去問

@drkenさんの「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」はかなり有名であり、多くの方がいろいろな言語で解答例を記事にしてくれています。

他の人のユニークな解法を見て勉強になることが多いのですが、テストケースの弱さのせいで間違ってACに判定されてしまっている嘘解法があることに気づいたので記事にしてみます。

第 9 問: ABC 049 C - Daydream (300 点)

問題概要
英小文字からなる文字列$S$ が与えられます。 以下の4つの単語のいずれかを選んで順番に並べていくことで文字列$S$を作れるかどうかを判定してください。
dream dreamer erase eraser

解法
文字列$S$を最初から消していき、完全に消せるかどうかで判定できます。正しくつなげられる可能性をつぶしてしまわないように、注意深く貪欲法で消していきましょう。

解答例1

s = input()

while s:
    if s[:6] == "eraser":
        s = s[6:]
    elif s[:5] == "erase":
        s = s[5:]
    elif s[:5] == "dream":
        if s[5:8] == "era":
            s = s[5:]
        elif s[5:7] == "er":
            s = s[7:]
        else:
            s = s[5:]
    else:
        print("NO")
        exit()
print("YES")

解答例1はACです。
最初から6文字をみてeraserの場合は、eraseを消してrを残しても仕方ないので、eraserを消します。それ以外で最初から5文字がeraseの場合はeraseを消します。最初から5文字をみてdreamであった場合に、次の文字がerでなければdreamを消します。dreamの次がerの場合はdreamerを消したいところですが、そのerはeraseやeraserの一部である可能性があります。なのでdreamの次の文字がeraであれば、dreamerではなくdreamを消し、eraseやeraserにつなげられるようにします。この操作を繰り返していき文字列$S$が完全に消えればYESを返します。途中で消えない文字が出てきた場合はNOを返します。

かなり冗長なコードなのでもっと短く表現したいですね。

解答例2

s = input()
if s.replace("eraser","").replace("erase","").replace("dreamer","").replace("dream",""):
    print("NO")
else:
    print("YES")

dreamの後にeraseやeraserが続く場合があると場合分けがややこしくなるので、先頭から順番に消していくのではなく、最初に$S$の中に含まれているすべてのeraserとeraseを消してしまってから、dreamerとdreamを消していこうという発想です。eraser, erase, dreamer, dreamの順番に$S$に含まれている部分をすべて消していき、最後に全部消えたかどうかで判定しています。

AtCoderでこのコードを入力するとACに判定されます。しかし、本当にこのアルゴリズムは正しいでしょうか。
以下のような入力例を考えてみます。

>? dreaerasem

この入力に対しては、題意からNOを出力するべきです。なぜならdreaerasemは、dreamとeraseを順番につなげて作ることができないからです。しかし今回のコードではdreaerasemに含まれるeraseを消すと残りがdreamになるのでYESを出力してしまいます。つまり解答例2は嘘解法です。

この方式で判定したいのであれば、eraseを消したことによってdreamがつながるのを防ぐ必要があります。見つかった文字列をreplaceで消すのではなく空白にいったん置き換えて、最後に消すようにします。

解答例3

s = input()
if s.replace("eraser"," ").replace("erase"," ").replace("dreamer"," ").replace("dream"," ").replace(" ", ""):
    print("NO")
else:
    print("YES")

解答例3はACです。
また実はこの問題は正規表現を使うことで以下のように簡潔に解くこともできます。

解答例4

import re
s = input()
print("YES" if re.match("^(eraser?|dream(er)?)*$", s) else "NO")

解答例4はACです。
正規表現の^と$は文字列の先端と末尾を示しています。A|BはA, Bのうちのどれかを示します。?は直前の正規表現があってもなくてもいいとする表記です(eraser?はeraseもしくはeraser)。*は直前の正規表現を繰り返したものにマッチさせる表現です。

第 10 問: ABC 086 C - Traveling (300 点)

問題概要
時間 $0$ に位置 $(0, 0)$ を出発し二次元平面上を旅行します。時間 $t$ に位置 $(x, y)$ にいるとき、時間 $t+1$ には以下のいずれかに移動します。その場にとどまることはできません。
$$(x+1, y), (x-1, y), (x, y+1), (x, y-1)$$

$1$ 以上 $N$ 以下の各$i$に対し、時間 $t_i$ に位置 $(x_i, y_i)$ を訪れる旅行プランが入力されます。旅行プランが実行可能かどうかを判定してください。

解法
与えられた $x$ と $y$ の値より必要な移動距離が計算できます。時間が $1$ 経過する間に $1$ ずつ移動できるので、時間と移動距離が等しい場合は明らかに移動可能です。移動距離が時間より大きい場合には、どうやっても移動は不可能です。時間の方が移動距離より大きい場合には、行って戻る動作をすることにより時間を $2$ だけつぶすことができ、移動距離と時間の差が偶数であれば移動可能です。移動距離と時間の差が奇数の場合は、どうやっても移動は不可能です。

解答例1

n = int(input())

for _ in range(n):
    t, x, y = map(int, input().split())
    if  x + y > t or (t - x - y) % 2:
        print("No")
        exit()
print("Yes")

入力されたそれぞれの時間 $t_i$ と位置 $(x_i, y_i)$ に対して、 $x_i + y_i$ が $t_i$ 以下であり差が偶数であることを確認しています。当てはまらない場合があればその時点でNoを出力して終了します。すべての場合に条件が成り立つことが確認できればYesを出力しています。

AtCoderでこのコードを入力するとACに判定されます。しかし、本当にこのアルゴリズムは正しいでしょうか。
以下のような入力例を考えてみます。

>? 2
>? 4 4 0
>? 5 0 5

この入力に対しては、題意からNOを出力するべきです。なぜなら時間 $4$ に位置 $(4, 0)$ にいた状態から、時間 $5$ に位置 $(0, 5)$ に移動することは不可能だからです。しかし今回のコードでは開始時から時間 $4$ に位置 $(4, 0)$ に行くことは可能、開始時から時間 $5$ に位置 $(0, 5)$ に行くことは可能として、それぞれを別々に判定してしまっているのでYesを出力してしまいます。つまり解答例1は嘘解法です。

正しくは以下のように、入力された時間と位置の差分を計算して、 $t_i$ から $t_{i+1}$ の間の時間に $(x_i, y_i)$ から $(x_{i+1}, y_{i+1})$ に移動できるかどうかをそれぞれ判定する必要があります。

解答例2

def difference(two_lists):
    return [abs(two_lists[1][i] - two_lists[0][i]) for i in range(3)]


n = int(input())

txy = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(n)]
dtxy = list(map(difference, zip(txy, txy[1:])))

for i in range(n):
    dt, dx, dy = dtxy[i]
    if  dx + dy > dt or (dt - dx - dy) % 2:
        print("No")
        exit()
print("Yes")

解答例2はACです。
入力された値を $[t_i, x_i, y_i]$ の順番にtxyというリストで受け取っています。スタート地点の$[0, 0, 0]$ を1つめの要素として追加しています。2つのリストの値の差(位置については差の絶対値)を計算するdifference関数を定義し、map関数を使ってtxyの各要素に対して1つ前の要素との差を計算しdtxyというリストにしています。そこから後は解答例1と同様ですが $[\mathrm{d}t_i, \mathrm{d}x_i, \mathrm{d}y_i]$ に対してそれぞれ時間と距離から移動可能かどうかを判定しています。

まとめ

いかがだったでしょうか。
精選過去問は非常に良い練習問題ですが、テストケースがおそらく弱くて今回の記事に取り上げたような嘘解法でもACになってしまうようです。簡潔に正しいコードが書けたつもりで、実は間違っていた人もいるのではないかと思います。

今回の記事で正しいコードとして紹介したコードにも、実は正しく判定されない入力例があるなど気づいた人がいれば教えてください。他にも内容について修正などあればコメントいただければ幸いです。