未知問に向かう：不変量と反例

赤を目指す段階では、知っている解法名への一致だけでは足りません。操作しても変わらない量と、達成できる範囲を考えます。

言語：Python / 計算量：証明と状態空間による

前提：貪欲法は「よさそう」で決めない

考え方

  1. 小さな例を列挙して仮説を作ります。
  2. 必要条件と十分条件を分けます。
  3. 条件が揃ったときの構成を示し、反例探索で弱点を見つけます。

具体例

2つの整数に同時に1を足す操作では差 a-b が不変。差が違う目標には到達できません。ただし差が同じでも減少はできないので十分ではありません。

実装

def reachable(a,b,c,d):
    return c-a==d-b and c>=a

print(reachable(1,3,4,6))

注意する条件

不変量が同じなら必ず到達できる、と飛躍しないこと。操作方向や非負条件を確認します。

確認問題

(1,3) から同時+1だけで (0,2) に到達？ Yes/No

解答と理由

No

差は同じでも、値を減らす操作がないため到達できません。

実装課題

A B C D が1行。操作 (a,b)→(a+1,b+1) を0回以上使って (A,B) から (C,D) に到達できるか。各絶対値≤10^18。

入力:
1 3 4 6
出力:
Yes
参考実装
a,b,c,d=map(int,input().split())
print("Yes" if c-a==d-b and c>=a else "No")

読了の記録・下書き・メモへ