otosidamaと白昼夢は考え中なのでいったん飛ばして今日はTravelingを解いた。
自分のコード
N = int(input()) N = N + 1 t = [0] * N x = [0] * N y = [0] * N for i in range(N-1): t[i+1], x[i+1], y[i+1] = map(int, input().split()) for j in range(N-1): turn = t[j+1] - t[j] move = abs(x[j+1] - x[j]) + abs(y[j+1] - y[j]) if turn < move: result = "No" elif turn == move: result = "Yes" elif turn > move: if turn % 2 == move % 2: result = "Yes" else: result = "No" print(result)
少し丁寧に書き残しておく。
標準入力の読み込みの段階でやや変なことをしている。最初に読み込んだNに1加えている。
そのくせfor文内で1引いているので一見すると何しているんだという感じだがこれはt,x,yをリスト化する段階で初期状態の情報を加えるために入れている。(t,x,y)=(0,0,0)をリストに入れてしまおうというわけである。
標準入力後jに関して回しているfor文が本番である。
まずturnとmoveという計算をしている。これはそれぞれ移動時間と移動距離の絶対値を示す。どれだけの時刻移動したか、x,yについてどれだけ移動したかを意味する。
その次に条件分岐を行っている。まずは今計算したturnとmoveの大小関係を比較する。
turnがmoveより小さいとき、一致するときは明らかに前者は到達不可能で後者は到達可能である。
turnがmoveより大きいときは同じ道を行ったり来たりすることで到達可能な場合と不可能な場合が出てくる。これを2つの変数の偶奇によって判定している。
ただ、ここまで書いてこのコードに問題があるんじゃないかという気がしてきた。条件分岐後のresultの扱いがまずそうに感じる。これだとループ中にNo判定が出てもその後Yesの判定に上書きされる可能性がある。ただ、これでも一応AC通ったので恐らくテストケースにそういったものがたまたまなかったのかもしれない。そこで下のコードは一度TrueかFalseで格納し最後の出力を判定する方法に変えた。
N = int(input()) N = N + 1 t = [0] * N x = [0] * N y = [0] * N for i in range(N-1): t[i+1], x[i+1], y[i+1] = map(int, input().split()) result = True for j in range(N-1): turn = t[j+1] - t[j] move = abs(x[j+1] - x[j]) + abs(y[j+1] - y[j]) if turn < move: result = False elif turn == move: result = True elif turn > move: if turn % 2 == move % 2: result = True else: result = False if result == False: break if result: print("Yes") else: print("No")
一番目のコードとは大した差はないが恐らくこちらの方が適切で勿論こちらもAC通った。
以下のコードは発想は同じだがまとまっている。
N = int(input()) t_old = 0 x_old = 0 y_old = 0 flag = True for _ in range(N): t, x, y = map(int, input().split()) dis = abs(x-x_old) + abs(y-y_old) t_sa = t - t_old if t_sa < dis or t_sa % 2 != dis % 2 : flag = False t_old = t x_old = x y_old = y if flag: print('Yes') else: print('No')
Submission #39789318 - AtCoder Beginners Selectionより
・最初の標準入力のループで処理しているためforが一回少ない
・条件もorでまとめられていて可読性が高い
点でよく見えるがこのループもやはり上書きの可能性を取り切れていないままAC通っているように思える。
そもそも前提として例えばケースとして与えられる座標が複数存在するときに途中の経路において到達不可能な点を通らないならforループ内で判定する必要もなくなる。
それすなわち原点→A→ゴールとしてA・ゴールが与えられているときに原点からAまでがそもそも到達不可能でAからゴールが到達可能な時にはYesが出力されるがこれは本来Noが出力されるべきではないんだろうか?という話である。
t0, x0, y0 = 0, 0, 0 for _ in range(int(input())): t, x, y = map(int, input().split()) margin = (t-t0) - abs(x-x0) - abs(y-y0) if margin < 0 or margin%2 != 0: print("No") break t0, x0, y0 = t, x, y else: print("Yes")
Submission #39725551 - AtCoder Beginners Selectionより。
これまたやっていることは同じだがよりコードがまとまったもの。ここではNo判定が出るとbreakするようになっている。
いろいろ眺めた結果、やはりテストケース的にたまたまACが出るだけでケアすべきだと感じる。
こういう条件分岐の問題は分岐させすぎてもコードとしてクオリティの高いモノにならないし、シンプルを追求しすぎても例外をケアできなかったりと中々思考が難しいものである。
が、発想さえできればコード化は比較的労せず出来るので思考力を鍛えていきたい。
それとPythonを使う以上、forを少なくすることは常に頭に入れておきたい。まだまだである。