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

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

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

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

###第  9 問: [ABC 049 C - Daydream](https://atcoder.jp/contests/abc049/tasks/arc065_a) (300 点)

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

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


```python:解答例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")
```

<B>解答例1は<font color="#449d44">AC</font></B>です。
最初から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`を返します。

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

```python:解答例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でこのコードを入力すると<font color="#449d44"><B>AC</B></font>に判定されます。しかし、本当にこのアルゴリズムは正しいでしょうか。
以下のような入力例を考えてみます。

```入力例
>? dreaerasem
```

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


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

```python:解答例3
s = input()
if s.replace("eraser"," ").replace("erase"," ").replace("dreamer"," ").replace("dream"," ").replace(" ", ""):
    print("NO")
else:
    print("YES")
```

<B>解答例3は<font color="#449d44">AC</font></B>です。
また実はこの問題は正規表現を使うことで以下のように簡潔に解くこともできます。

```python:解答例4
import re
s = input()
print("YES" if re.match("^(eraser?|dream(er)?)*$", s) else "NO")
```

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

###第 10 問: [ABC 086 C - Traveling](https://atcoder.jp/contests/abc086/tasks/arc089_a) (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$ だけつぶすことができ、移動距離と時間の差が偶数であれば移動可能です。移動距離と時間の差が奇数の場合は、どうやっても移動は不可能です。

```python:解答例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でこのコードを入力すると<font color="#449d44"><B>AC</B></font>に判定されます。しかし、本当にこのアルゴリズムは正しいでしょうか。
以下のような入力例を考えてみます。

```入力例
>? 2
>? 4 4 0
>? 5 0 5
```

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

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

```python:解答例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")
```

<B>解答例2は<font color="#449d44">AC</font></B>です。
入力された値を $[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]$ に対してそれぞれ時間と距離から移動可能かどうかを判定しています。

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

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