動的計画法

カエルが最小コストで段差を移動する問題の２つめを、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1, 2, …, N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場1にいます。

カエルは次の行動を何回か繰り返し、足場Ｎまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1, i + 2, …, i + K のどれかへジャンプする。 

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を

コストとして支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

前回の問題との違いは、ジャンプする幅が i+1, i+2 だけではなく、i + K と可変になっているところです。

ただし、前回の処理で +1, +2 の２パターンで処理していた個所を、K回ループで回す 処理に変えるだけなので、ほんの少しの修正で対応することが可能です。

修正したソースコードは次のようになります。

[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

#--------- 入力例1 ----------
k=3
lst = [10, 30, 40, 50, 20]
#--------- 入力例2 ----------
# k=1
# lst = [10, 20, 10]
#--------- 入力例4 ----------
# k=100
# lst = [10, 10]
#--------- 入力例4 ----------
# k=4
# lst = [40, 10, 20, 70, 80, 10, 20, 70, 80, 60]
#----------------------------
n = len(lst)      # 段差の数

memo = [float('inf')] * n

memo[0] = 0
for i in range(n):
    for x in range(1, k + 1):
        if i - x >= 0:
            memo[i] = min(memo[i], memo[i - x] + abs(lst[i] - lst[i - x]))
print(memo[n-1])

[実行結果（入力例1）]

30

足場 1 → 2 → 5 と移動すると、コストの総和は ∣ 10 − 30 ∣ + ∣ 30 − 20 ∣ = 30 となります。

[実行結果（入力例2）]

20

足場 1 → 2 → 3 と移動すると、コストの総和は ∣ 10 − 20 ∣ + ∣ 20 − 10 ∣ = 20 となります。

[実行結果（入力例3）]

0

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

[実行結果（入力例4）]

40

足場 1 → 4 → 8 → 10 と移動すると、コストの総和は ∣ 40 − 70 ∣ + ∣ 70 − 70 ∣ + ∣ 70 − 60 ∣ = 40 となります。

動的計画法

カエルが最小コストで段差を移動する問題を、動的計画法 を使って解いていきます。

[問題]

Ｎ個の足場があります。 足場には 1,2,…,N と番号が振られています。

各 i (1 ≦ i ≦  N) について、足場 i の高さは h_i です。

最初にカエルは、足場 1 にいます。

カエルは次の行動を何回か繰り返し、足場Nまで辿り着こうとしています。

足場 i にいるとき、足場 i + 1 または i + 2 へジャンプします。

このとき、ジャンプ先の足場を j とすると、コスト ∣h_i − h_j∣ (差分の絶対値)を支払う必要があります。

カエルが足場 N に辿り着くまでに支払うコストの 総和の最小値 を求めてください。

解法・ソースコード

メモ化テーブル memo[i] を頂点iへと至る最短経路を表していると定義します。

memo[i] の値を求めるために、次の２つを比較します。

• 頂点 i - 1まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
  memo[i - 1] + abs(h[i] - h[i - 1])
• 頂点 i - 2まで最短経路で行ってから、頂点 i へと至る方法の最小コスト
  memo[i - 2] + abs(h[i] - h[i - 2])

memo[i] の値は、これらのうちの 最小値 となります。

以上を踏まえて実装すると以下のようなソースになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#--------- 入力例1 ----------
lst = [10, 30, 40, 20]
#--------- 入力例2 ----------
# lst = [10, 10]
#--------- 入力例3 ----------
# lst = [30, 10, 60, 10, 60, 50]
#----------------------------
n = len(lst)    # 足場の数

memo = [float('inf')] * n
memo[0] = 0

for i in range(n):
    if i - 1 >= 0:
        memo[i] = min(memo[i], memo[i - 1] + abs(lst[i] - lst[i - 1]))
    if i - 2 >= 0:
        memo[i] = min(memo[i], memo[i - 2] + abs(lst[i] - lst[i - 2]))
print(memo[n - 1])

[実行結果（入力例1）]

30

足場 1 → 2 → 4 と移動すると、コストの総和は ∣10 − 30∣ + ∣30 − 20∣ = 30 となります。

[実行結果（入力例2）]

0

足場 1 → 2 と移動すると、コストの総和は ∣ 10 − 10 ∣ = 0 となります。

[実行結果（入力例3）]

40

足場 1 → 3 → 5 → 6 と移動すると、コストの総和は ∣ 30 − 60 ∣ + ∣60 − 60 ∣ + ∣ 60 − 50 ∣ = 40 となります。

最長共通部分列

部分列 は系列のいくつかの要素を取り出してできた系列のことです。

二つの系列の共通の部分列を 共通部分列 と言います。

共通部分列のうちもっとも長いものを 最長共通部分列 と言います。

最長共通部分列 を求める問題を 動的計画法 を使って解いていきます。

問題

２つの文字列があります。

これら２つの共通部分列の長さの最大値を求めて下さい。

解法・ソースコード

メモ化テーブル を次のように定義します。

memo[i][j] は、【１つめの文字列のｉ文字まで】と【２つめの文字列のｊ文字まで】の

最長共通部分列の長さ

この定義を踏まえて、漸化式 を作成し 動的計画法（メモ化テーブル） を実装すると次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#---------- 入力例 ----------
a = 'ABCBDAB'
b = 'BDCABA'
#----------------------------
# メモ化テーブル
memo = {}

for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        if a1 == b1:    # 文字が一致した場合
            # 最長共通部分列の長さを１つ増やす
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:           # 文字が一致しない場合
            # これまでの最長共通部分列で長いほうを選択
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))

print('解：', memo[(len(a), len(b))])

[実行結果]

解： 4

解は 4 となりました。

２つの文字列を確認すると 最長共通部分列 が B, C, B, A となっていて解が正しいことが分かります。

動的計画法（順方向）

前回は 動的計画法 を使ってナップサック問題を解きましたが、再帰関数に合わせてループの順番が 逆方向 になっていました。

今回は、このループの順番を 順方向 に変えてみます。

[ナップサック問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

解法・ソースコード

ループを 順方向 に変えるためには、ループ文 と 漸化式 を少し変更する必要がありますが、根本的な内容は前回記事の処理と変わりません。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# 動的配列
dp = {}
for i in range(0, len(items) ):             # アイテムを順方向にループ
    for j in range(capacity + 1):           # 重さを順番にループ
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i + 1, j] = dp.get((i, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i, j - items[i]['weight']), 0) + items[i]['value']
            dp[i + 1, j] = max(a, b)        # 価値が高いほうを選択

print('解：', dp[len(items), 5])

ループを 順方向 に変えることで、ループ文 や 漸化式 がシンプルで分かりやすくなったのではないでしょうか。

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となっています。

動的計画法

今回は 動的計画法 を使ってナップサック問題を解いていきます。

動的計画法 は、値を覚えて再利用する手法です。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

前回使った メモ化した辞書型データ に注目してみます。

メモ化した辞書型データ は、ｉ番目以降の品物から、重さの総和がｊ以下 となるように選んだ時の 価値の総和の最大値 となっています。

再帰関数を書かなくても、直接この 漸化式 を用いて各項目の値を順に計算していくことにより、単純な二重ループ で ナップサック問題を解くことができます。

（漸化式 とは、数列の各項をその前の頃から1通りに定める規則を表す等式のことです。）

解法・ソースコード

前回の 再帰関数 をもとに、動的計画法 で実装を行うと下記のようになります。

２重ループの中で、漸化式 を使って順番に メモ化テーブル に結果を格納していきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化テーブル
dp = {}
for i in range(len(items) - 1, -1, -1):     # アイテムを後ろからループ
    for j in range(capacity + 1):
        if j < items[i]['weight']:          # 重さが許容範囲外の場合
            dp[i, j] = dp.get((i + 1, j), 0)
        else:                               # 重さが許容範囲内の場合
            # 品物を入れない場合
            a = dp.get((i + 1, j), 0)
            # 品物を入れる場合（許容範囲の重さを減らし、価値を増やす）
            b = dp.get((i + 1, j - items[i]['weight']), 0) + items[i]['value']
            dp[i, j] = max(a, b)    # 価値が高いほうを選択

print('解：', dp[0, 5])

[実行結果]

解： 7

解（価値の総和の最大値）はこれまで同様 7 となりました。

前回と同じナップサック問題を より効率的に解く方法 を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックにい列品物の総和は capacity を超えてはいけません。

選んだ品物の価値の総和として考えられる最大値を求めて下さい。

メモ化

前回は、再帰関数 を使ってナップサック問題を解きましたが、再帰関数が 同じ引数で何度もコールされる ことがありました。

このままでは非効率なので、メモ化 という方法で効率的に処理を行ってみます。

メモ化 では、最初の計算時の結果を記憶しておくことで、同じ引数での二度目以降の計算を省略 します。

ソースコード

メモ化 のために、9行目、13～14行目、23行目を追加しています。

[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

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# メモ化用変数
memo = {}

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if (i, j) in memo:      # メモに結果があったら
        return memo[i, j]   # その結果を返す

    if i == len(items):     # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    memo[i, j] = res        # 結果をメモ化
    return res

print(rec(0, capacity))

[実行結果]

7

解（価値の総和の最大値）は前回同様 7 となりました。

今回の入力例では、同じ引数で再帰関数がコールされる回数 が少ないので大幅な効率化はしていませんが、この改良により 解ける問題のサイズを大幅に増やす ことができたことになります。

functools

functools というPythonの標準モジュールを使うと デコレータ を設定するだけで 簡単にメモ化 することができます。（8行目、11行目）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
import functools

# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
@functools.lru_cache(maxsize=None)
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

7

ナップサック問題

次のような問題を考えます。

[問題]

Ｎ個の品物があります。

それぞれの品物の 重さ(weight) と 価値(value) は分かっています。

これらの品物からいくつか選んでナップサックに詰めていきます。

ナップサックに入れる品物の 重さの総和 は capacity を超えてはいけません。

選んだ品物の 価値の総和 として考えられる最大値を求めて下さい。

解法・ソースコード

それぞれの品物を入れるか入れないかで分類しながら、再帰関数を使って探索を行ってみます。

再帰関数の第１引数には 品物のインデックス を渡し、第２引数には あとどのくらいの許容量があるか（どのくらいの重さを許容できるか） を渡し、返す値は 価値 となります。

再帰関数内の条件分としては次の３つになります。

• 品物がない場合
  価値が増えないので 0 を返す。
• 許容の重さを超える場合
  今回の品物は選択せずに、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
  その関数の結果を返値（価値）とします。
• 許容の重さを超えない場合
  今回の品物を 入れない場合 と 入れる場合 の両方で、次の品物のチェックのため品物のインデックスを増やし関数をコールします。（再帰呼び出し）
  ２つのパターンで価値の大きいほうを返値（価値）とします。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#---------- 入力例 ----------
items = [{'weight':2, 'value':3},
         {'weight':1, 'value':2},
         {'weight':3, 'value':4},
         {'weight':2, 'value':2}]
capacity = 5
#----------------------------
# i番目以降の品物の中から重さの総和がj以下となるように選ぶ
def rec(i, j):
    if i == len(items):  # 品物がもう残っていない場合
        res = 0
    elif j < items[i]['weight']:    # 品物が入らない場合
        res = rec(i + 1, j)
    else:
        # 品物を入れない場合と入れる場合で価値が大きいほうを選ぶ
        res = max(rec(i + 1, j), rec(i + 1, j - items[i]['weight']) + items[i]['value'])
    return res

print(rec(0, capacity))

[実行結果]

7

解（価値の総和の最大値）は 7 となりました。

１番目、２番目、４番目の品物を選んだ場合、価値の総和が7、重さの総和が5 となり 重さの許容範囲内で価値が最大 となっていることを確認できます。

再帰関数

次のような問題を考えます。

[問題]

整数 k に対して、レベル k の AB文字列 を次のように定義します。

・レベル 0 の AB 文字列は "B" です。

・レベル k の AB 文字列は "A" + (レベル k - 1 の AB 文字列) + "B" + (レベル k - 1 の AB 文字列) + "A" です。

　例 : レベル 2 の ABC 文字列は "A" + "ABBBA" + "B" + "ABBBA" + "A" = "AABBBABABBBAA" となります。

レベル k の AB 文字列の x 文字目 までに "B" が何個あるかを求めてください。

[条件]

・レベル k は、1以上 50以下の整数

・x（何文字目） は、1以上 レベル kのAB文字列の長さ以下の整数

解法・ソースコード

まず レベル k のAB文字列の長さは ２の k 乗 以上になり k ≦ 50 という条件を考慮すると、単純に文字列を生成する方法では処理が終わりません。

そこで 再帰関数 を使った解法を考えてみます。

問題をよく読むと、レベル k の AB文字列は レベル k - 1 の AB文字列によって定義されていることがわかります。

つまり、AB文字列は １つ前のAB文字列 によって再帰的に定義されています。

レベル k の AB文字列の長さを len_s[k]、レベル k の AB文字列に含まれる文字列”B”の個数を cnt_b[k]とします。

このとき、レベル k の AB文字列を表す文字列の先頭から x文字目 に含まれる 文字列”B”の数 は次のように考えることができます。

• x=1のとき
  0個
• x=2 ～ len_s[k-1]+1のとき
  ひとつ前の文字列レベルの先頭から、x-1文字列の中に含まれる文字列”B”の個数
• x=len_s[k-1]+2のとき
  ひとつ前の文字列レベルの文字列”B”の個数+1
• x=len_s[k-1]+3 ～ 2 * len_s[k-1]+2のとき
  ひとつ前の文字列レベルの先頭から、x-len_s[k-1]-2文字の中に含まれる文字列”B”の個数 + cnt_b[k-1] + 1個
• x=2*len_s[k-1]+3のとき
  cnt_b[k-1] * 2 + 1個

以上により、レベル k の AB文字列 を レベル k-1 の AB文字列 に関する問題へと帰着することができました。

また、レベル k の AB文字列の長さ(len_s) と 文字列”B”の個数(cnt_b) は以下のように定義できます。

• レベル k の AB文字列の長さ
  len_s[k] = len_s[k-1] * 2 + 3 　　(len_s[0] = 1)
• 文字列”B”の個数
  cnt_b[k] = cnt_b[k-1] * 2 + 1 　　(cnt_b[0] = 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
29

#---------- 入力例 1 ---------
k = 2   # 文字列レベル k 
x = 7   # 何文字目までの "B" をカウントするか
#---------- 入力例 2 ---------

# 再帰関数
def rec(k, x, len_s, cnt_b):
    if k == 0:      # 終了条件
        return 1
    # xに応じて処理分け
    if x == 1:
        return 0
    elif x <= len_s[k - 1] + 1:
        return rec(k - 1, x - 1, len_s, cnt_b)
    elif x == len_s[k - 1] + 2:
        return cnt_b[k - 1] + 1
    elif x <= len_s[k - 1] * 2 + 2:
        return rec(k - 1, x - len_s[k - 1] - 2, len_s, cnt_b) + cnt_b[k - 1] + 1
    else:
        return cnt_b[k - 1] * 2 + 1

len_s = [1] * (k + 1)   # レベルごとの文字列の長さ
cnt_b = [1] * (k + 1)   # レベルごとの文字列"B"の数
for i in range(1, k + 1):
    len_s[i] = len_s[i - 1] * 2 + 3   # ひとつ前のレベル文字列を２倍し３を足したものが文字列数
    cnt_b[i] = cnt_b[i - 1] * 2 + 1   # ひとつ前のレベル文字列を２倍し１を足したものが文字列"B"の数

# 再帰的に求める
print(rec(k, x, len_s, cnt_b))

[実行結果]

4

文字列レベル2の文字列は “AABBBABABBBAA” であり、この文字列の先頭から7文字の中に 文字列”B” が 4個 含まれます。

パリティ

操作に関する問題は、決まったパターンを持たず 柔軟な思考 を必要とするものが多くあります。

しかしながら、次のように問題を解くための指針となる考え方があります。

• 操作をわかりやすく言い換える。
• 操作によって作れるものを特徴付ける。

[問題]

Ｎ個の整数が一列に並んでいます。

この整数列に対して次の操作を好きなだけ行うことができます。

「隣り合う２つの整数を選んで、両方の整数に－1を掛ける」

操作終了後のＮ個の整数の 総和 として考えられる最大値を求めて下さい。

解法・ソースコード

今回の操作を分類すると、次のいずれかになります。

• 数列の「プラス」「プラス」が連続している箇所を「マイナス」「マイナス」にする。
• 数列の「プラス」「マイナス」が連続している箇所を「マイナス」「プラス」にする。
• 数列の「マイナス」「プラス」が連続している箇所を「プラス」「マイナス」にする。
• 数列の「マイナス」「マイナス」が連続している箇所を「プラス」「プラス」にする。

上記により「マイナス」の個数は「２つ増える」か「変わらない」か「２つ減る」 かのいずれかであることが分かります。

つまり「マイナス」の個数の パリティ（偶数／奇数） は 操作の前後で不変 です。

実装は次のように行います。

• 数列の中のマイナスの数値が 偶数個 ある場合
  マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
• 数列の中のマイナスの数値が 奇数個 ある場合
  マイナスの数値を全てなくして（絶対値をとって）、総和を算出する。
  その総和から、絶対値が最小 である数値を ２回差し引く。
  （総和にはすでに最小の数値が含まれているため ２回差し引く 必要があります。）

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#---------- 入力例 1 ---------
lst = [-10, 5, -4]
#---------- 入力例 2 ---------
# lst = [1, 2, -3, 10, 100]
#-----------------------------
# マイナスの個数
cnt_minus = sum(x < 0 for x in lst)

# Ｎ個の整数の絶対値の総和
total = sum(map(abs, lst))
# Ｎ個の整数の絶対値の最小値
abs_minus = min(map(abs, lst))

# マイナスの個数が[偶数の場合]は、[絶対値の総和]を出力。
# マイナスの個数が[奇数の場合]は、[絶対値の総和] － [絶対値の最小値×２]を出力。
print(total if abs_minus % 2 == 0 else total - abs_minus * 2)

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

19

マイナスの数値の個数が 偶数 なので、すべての整数の 絶対値の総和 が解となります。

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

114

マイナスの数値の個数が 奇数 なので、すべての整数の 絶対値の総和 から 絶対値の最小値×２ を引いた値が解となります。

パリティ

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

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

[問題]

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

時刻 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 では、時間が足りていない ため移動できません。