パリティ①

パリティ

パリティ とは、偶数と奇数に関する性質 のことです。

パリティ に注目すると問題が簡単に解けることがあります。

[問題]

２次元平面上で旅をしようとしています。

時刻 0 に地点 (0, 0) を出発し、時刻 t に地点 (x, y) を訪れる予定です。

時刻 t に地点 (x, y) にいるときには、時刻 t + 1 には

地点 (x + 1, y)、(x - 1, y)、(x, y + 1)、(x, y - 1) のうちいずれかに

移動することができます。

その場にとどまることはできません。

入力は、時刻と地点(t, x, y)が複数与えられます。

入力の旅行プランが実行可能であれば "Yes"、不可能であれば "No" を出力してください。

解法・ソースコード

まず、不可能な場合を考えてみます。

例えば、時刻が１ のときは、１つしか移動できない ので地点(5,6)のような移動はできません。

次に時間は足りているのに移動できない状況は考えられるでしょうか。

例えば、時刻が３ のときには 地点(1, 1) への移動はできません。

これをよく考えてみる、パリティ（奇数か偶数か） によって移動できる地点とできない地点が 交互 になっていることに気づくことができます。

つまり、時刻のパリティ と 移動数のパリティ が同じであれば移動でき、パリティ が異なれば移動できないことになります。

以上を踏まえて、コードを書くと次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#---------- 入力例 1 ---------
plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
        (6, 1, 1)]   # 時刻 t、地点 (x, y)
#---------- 入力例 2 ---------
#plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
#        (6, 2, 1)]   # 時刻 t、地点 (x, y)
#---------- 入力例 3 ---------
#plan = [(3, 1, 2),   # 時刻 t、地点 (x, y)
#        (2, 1, 1)]   # 時刻 t、地点 (x, y)
#-----------------------------
# 前回の時刻と座標
pt, px, py = 0, 0, 0    # 初期状態

for t, x, y in plan:
    # 前回状態との差分
    dt, dx, dy = t - pt, abs(x - px), abs(y - py)
    # 時間が足りない場合は移動不可
    if dt < dx + dy:
        print('No (時間が足りない)')
        break
    # パリティが合わないときは移動不可
    if dt % 2 !=  (dx + dy) % 2:
        print('No (パリティが合わない)')
        break
    # 前回状態を更新
    pt, px, py = t, x, y
else:
    print('Yes (移動可能)')

[実行結果 (入力例 1)]

Yes (移動可能)

入力例 1 では、時間が足りておりパリティもあっている ので移動が可能です。

[実行結果 (入力例 2)]

No (パリティが合わない)

入力例 2 では、時間は足りていますが パリティ があっていないので移動できません。

[実行結果 (入力例 3)]

No (時間が足りない)

入力例 3 では、時間が足りていない ため移動できません。