ABC086C - Traveling の嘘解法

## 問題
https://atcoder.jp/contests/abs/tasks/arc089_a (300 点)

***概要***
２次元平面上で旅行をしようとしています。旅行プランでは***時刻 0***に***点(0,0)***を出発し、1以上N以下の各 i に対し、***時刻Ti***に***点(Xi,Yi)***を訪れる予定です。
時刻Tに点(X,Y)にいる時、時刻T+1には(X+1,Y),(X-1,Y),(X,Y+1),(X,Y-1)のいずれかに存在することができます***(つまりその場にとどまれないということです)***
旅行プランが実行可能かどうか判定してください。

#### 入力

```ruby
N
T1 X1 Y1
T2 X2 Y2
:
Tn Xn Yn

#例題
2
3 1 2
6 1 1
```


## <font color="orange">嘘</font>解法

以下の<B><font color="orange">嘘解法</font></B>を多く見かけました。

```ruby
n = gets.strip.to_i
n.times do
  t, x, y = gets.strip.split.map(&:to_i)
  if t < x + y || (t + x + y) % 2 != 0
    puts 'No'
    exit
  end
end
puts 'Yes'
```
例題でいうと

```
2
3 1 2
6 1 1
```
に対して***点(0,0)からの最短到着時刻(最短距離)***と、***時刻Tと点(X,Y)の偶奇が一致するか***を見ています。

それぞれ見てみましょう。まずは、

### 最短到着時刻(最短距離)

```ruby
if t < x + y
```

これは左上の点(0,0)、右下の点(1,1)とした場合

|(x,y)|(0,0)|(0,1)|
|-----|-----|-----|
|-    |(1, 0)|(1, 1)|

**点(0,0)***から上下右左のいずれかに移動できる場合の最短到着時刻は<B><font color="red">X+Y</font></B>で求めることができます。((0,0)→(1,1)には最短2歩でいける)

|(x+y)|0|1|
|---|---|---|
|-|1|2|

よって点（0,0）から出発し、<B><font color="blue">到着したい時刻(T)</font> < <font color="red">最短到着時刻(X+Y)</font></B>の場合は、必要時刻が足らずに到着できません。次に、

### 偶奇の一致

```ruby
(t + x + y) % 2
```
これは<B><font color="blue">T(予定時刻)</font> と <font color="red">X+Y(最短到着時刻)</font></B>の偶数と奇数が一致するかを見ています。X+Y(最短到着時刻)の座標が偶数の場合、その座標には***どんなに遠回りしても偶数になる***性質があります。(奇数の場合も一緒)
よって<B><font color="blue">T(予定時刻)</font> と <font color="red">X+Y(最短到着時刻)</font></B>の偶奇が一致する場合、上記のコードは必ず***0***を返します。

## なぜ嘘解法なのか？
確かに<B><font color="green">AC</font></B>の判定が出ているコードですが、
以下の様な入力例を考えてみます。

***テストケース***

```
2
4 2 2
6 0 0
```
|(x+y),(T)|0,(6)  |1  |2    |
|---------|-------|---|-----|
|-        |1      |2  |3    |
|-        |2      |3  |4,(4)|

といった感じの平面座標です。
***一つ目の入力(4 2 2)***は予定時刻と最短到着時刻が一致しているため、行けることがわかります。

では***二つ目の入力(6 0 0)***はどうでしょうか...

```ruby
  if t < x + y || (t + x + y) % 2 != 0
    puts 'No'
    exit
  end
```
この条件式は左右の条件式のどちらかが***true***だった場合は、***旅行不可***のため"No"を出力します。
よって二つ目の入力はどちらの条件式も***False***返すため、<B><font color="red">Yes<font></B>を出力します。(つまり***旅行可能***)

しかし、***点(2,2)(一つ目の入力地点)から(0,0)***までの最短距離を出してみましょう。

|(最短距離),(T)|4,(6)  |3  |2    |
|-------------|-------|---|-----|
|-            |3      |2  |1    |
|-            |2      |1  |0(4) |

***6 - 4 (ふたつ目の入力時刻 - ひとつ目の入力時刻)*** = ***2(歩分)***しか旅人は移動できないはずですが、上記の表だと２歩で到着できるのは***点(1,1)***までの様です。
しかし上記のコードでは、"Yes"と判定されてしまいます。

## <font color="green">正</font>しい解法
正しくは、以下の条件を確認する必要があります。

1. TとX+Yの偶奇の一致
1. ***(現在の地点)から(入力された目標地点(X,Y))までの<font color="red">最短到着時刻</font>*** が ***移動可能な距離圏内（入力時刻-現時刻)***である

上記1つは実行済みなので、条件2のコードを追加します。
ちなみに[最短到着時刻(最短距離)](#最短到着時刻最短距離)で記載したコードは、上記の条件2と同義なので添削します。

これをコードで表現すると以下のようになりました。

```ruby
n = gets.strip.to_i

t_old = x_old = y_old = 0
n.times do
  t, x, y = gets.strip.split.map(&:to_i)

#移動可能時刻と最短到着時刻を計算
  abel = (t_old - t).abs
  dist = (x_old - x).abs + (y_old - y).abs

  if (t + x + y) % 2 != 0 || abel < dist #<-条件追加
    puts 'No'
    exit
  end
  
#今回入力された値を記録
  t_old = t
  x_old = x
  y_old = y
end
puts 'Yes'
```

### 解説
1. 入力された(t,x,y)をそれぞれ(t_old,x_old,y_old)として保存し、次のループで使います。
1. 次の回で入力された値と保存された値を比べて旅人の移動可能時刻と、前地点から今地点の最短距離を出します。
    - ***移動可能距離 = (今回の到着時刻 - 前回の到着時刻)***の絶対値
    - ***最短到着時刻 = （前回のX地点-今回のX地点）***の絶対値 + ***(前回のY地点-今回のY地点)***の絶対値
1. 最短到着時刻(dist)が移動可能距離(abel)圏内か判定します。***←3つめの追加条件***

これを提出すると正しく<B><font color="green">AC</font></B>となります。
先ほどの***1: 4 2 2 , 2: 6 0 0***のケースにおいても正しく "No"と判定します。


以上でこの問題の嘘解法についての投稿は終了します。

***ここからは記事を書いた感想文です。(笑)***
## 初投稿
初めまして！今回がQiita初投稿となりました！:pray:
僕自身は、競技プログラミングを始めてようやくAOJ(AizuOnlineJadge)のITP1を解き切れたレベルです:sweat_smile:
しかし競技プログラミングは非常に楽しいので、今後も粘り強く続けていきます:relaxed:

実はこの嘘解法との出会いは、***解き方が分からずに他の人のコードを閲覧したこと***がきっかけでした。(笑)
コード長の項目が１番少ない物のが***１番スマート***でしょ！！という安易な理由でたどり着いたのが今回の嘘解法です。
閲覧したコードを解釈したときには、こんなに簡単なコードで成り立っているのか！***全くもってスマートだぜ！！***と唸りました。
しかし何か引っかかるものがありました。他の方が書いたコードに疑いを持ったのは初めてでした。

そうして見つけた嘘解法...とても興奮しました...!
その勢いのまま投稿をした次第です(笑)
今見返しても、とても***スマート***ではない記事とコードですが、この楽しみを味わえたことには、非常に満足しています:star2:

そして、
もっともっと***スマート***なコード・記事を書ける猛者はたくさんいると思うので、
この記事を閲覧してくれた際は、是非ともご教示いただければ幸いです。
よろしくお願いします:grin:


### 追記
- コードと記事の内容を修正しました(@superrino130さん、ご教示いただきありがとうございました！)
    - [正しい解法](#正しい解法)の確認条件を修正しました
    - [正しい解法](#正しい解法)のコード内容を修正しました