問題
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)のいずれかに存在することができます(つまりその場にとどまれないということです)
旅行プランが実行可能かどうか判定してください。
入力
N
T1 X1 Y1
T2 X2 Y2
:
Tn Xn Yn
#例題
2
3 1 2
6 1 1
嘘解法
以下の嘘解法を多く見かけました。
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)の偶奇が一致するかを見ています。
それぞれ見てみましょう。まずは、
最短到着時刻(最短距離)
if t < x + y
これは左上の点(0,0)、右下の点(1,1)とした場合
| (x,y) | (0,0) | (0,1) |
|---|---|---|
| - | (1, 0) | (1, 1) |
**点(0,0)***から上下右左のいずれかに移動できる場合の最短到着時刻はX+Yで求めることができます。((0,0)→(1,1)には最短2歩でいける)
| (x+y) | 0 | 1 |
|---|---|---|
| - | 1 | 2 |
よって点（0,0）から出発し、到着したい時刻(T) < 最短到着時刻(X+Y)の場合は、必要時刻が足らずに到着できません。次に、
偶奇の一致
(t + x + y) % 2
これはT(予定時刻) と X+Y(最短到着時刻)の偶数と奇数が一致するかを見ています。X+Y(最短到着時刻)の座標が偶数の場合、その座標にはどんなに遠回りしても偶数になる性質があります。(奇数の場合も一緒)
よってT(予定時刻) と X+Y(最短到着時刻)の偶奇が一致する場合、上記のコードは必ず0を返します。
なぜ嘘解法なのか？
確かにACの判定が出ているコードですが、
以下の様な入力例を考えてみます。
テストケース
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)***はどうでしょうか...
if t < x + y || (t + x + y) % 2 != 0
puts 'No'
exit
end
この条件式は左右の条件式のどちらかがtrueだった場合は、旅行不可のため"No"を出力します。
よって二つ目の入力はどちらの条件式もFalse返すため、Yesを出力します。(つまり旅行可能)
しかし、***点(2,2)(一つ目の入力地点)から(0,0)***までの最短距離を出してみましょう。
| (最短距離),(T) | 4,(6) | 3 | 2 |
|---|---|---|---|
| - | 3 | 2 | 1 |
| - | 2 | 1 | 0(4) |
6 - 4 (ふたつ目の入力時刻 - ひとつ目の入力時刻) = ***2(歩分)しか旅人は移動できないはずですが、上記の表だと２歩で到着できるのは点(1,1)***までの様です。
しかし上記のコードでは、"Yes"と判定されてしまいます。
正しい解法
正しくは、以下の条件を確認する必要があります。
- TとX+Yの偶奇の一致
- (現在の地点)から(入力された目標地点(X,Y))までの最短到着時刻 が ***移動可能な距離圏内（入力時刻-現時刻)***である
上記1つは実行済みなので、条件2のコードを追加します。
ちなみに最短到着時刻(最短距離)で記載したコードは、上記の条件2と同義なので添削します。
これをコードで表現すると以下のようになりました。
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'
解説
- 入力された(t,x,y)をそれぞれ(t_old,x_old,y_old)として保存し、次のループで使います。
- 次の回で入力された値と保存された値を比べて旅人の移動可能時刻と、前地点から今地点の最短距離を出します。
- ***移動可能距離 = (今回の到着時刻 - 前回の到着時刻)***の絶対値
- ***最短到着時刻 = （前回のX地点-今回のX地点）***の絶対値 + ***(前回のY地点-今回のY地点)***の絶対値
- 最短到着時刻(dist)が移動可能距離(abel)圏内か判定します。←3つめの追加条件
これを提出すると正しくACとなります。
先ほどの1: 4 2 2 , 2: 6 0 0のケースにおいても正しく "No"と判定します。
以上でこの問題の嘘解法についての投稿は終了します。
ここからは記事を書いた感想文です。(笑)
初投稿
初めまして！今回がQiita初投稿となりました！
僕自身は、競技プログラミングを始めてようやくAOJ(AizuOnlineJadge)のITP1を解き切れたレベルです
しかし競技プログラミングは非常に楽しいので、今後も粘り強く続けていきます
実はこの嘘解法との出会いは、解き方が分からずに他の人のコードを閲覧したことがきっかけでした。(笑)
コード長の項目が１番少ない物のが１番スマートでしょ！！という安易な理由でたどり着いたのが今回の嘘解法です。
閲覧したコードを解釈したときには、こんなに簡単なコードで成り立っているのか！***全くもってスマートだぜ！！***と唸りました。
しかし何か引っかかるものがありました。他の方が書いたコードに疑いを持ったのは初めてでした。
そうして見つけた嘘解法...とても興奮しました...!
その勢いのまま投稿をした次第です(笑)
今見返しても、とてもスマートではない記事とコードですが、この楽しみを味わえたことには、非常に満足しています
そして、
もっともっとスマートなコード・記事を書ける猛者はたくさんいると思うので、
この記事を閲覧してくれた際は、是非ともご教示いただければ幸いです。
よろしくお願いします
追記
- コードと記事の内容を修正しました(@superrino130さん、ご教示いただきありがとうございました！)