概要

各メモの不明瞭な部分（\(-1\)）を適切に補って、すべてのメモが同じ整数列になるようにできるかどうかを判定する問題。

考察

各メモにはちょうど1つの \(-1\) があり、それ以外の要素は確定しています。目標は、すべてのメモが一致するような元のパスワード \(P\) が存在するかどうかです。

重要な観察は、各位置 \(j\) において、すべてのメモの \(j\) 番目の要素を比較したときに、矛盾がないかを確認すれば良いということです。

素朴なアプローチの問題点

最初に思いつくのは、すべてのメモを実際に補完してみて、一致するか試すことですが、これは補完方法が多すぎるため現実的ではありません。特に、\(-1\) の箇所に代入できる値が \(0\) から \(10^9\) まであるため、全探索は不可能です。

解決方法

実は、補完する必要はありません。重要なのは「各位置 \(j\) において、確定している値がすべて一致しているか」だけです。

つまり、各位置 \(j\) について： - \(-1\) でない値を集めて、それが1種類だけであることを確認します。 - 2種類以上あるなら、どんな値を代入しても一致させられません → No - 1種類だけなら、その値が答えの \(P_j\) になります。 - すべてが \(-1\) なら、任意の値（例えば \(0\)）を設定できます。

このようにして、すべての位置で矛盾がなければ Yes、そうでなければ No と判定できます。

アルゴリズム

1. 各メモを入力として受け取ります。
2. 各位置 \(j\)（\(0 \leq j < M\)）に対して以下を行います：
   • その位置の値を集める（ただし \(-1\) は無視）。
   • 集めた値の種類数が 2 以上なら No を出力して終了。
   • 1 種類ならその値が \(P_j\)。
   • 0 種類（すべて \(-1\)）なら任意の値が選べるのでOK。
3. すべての位置で矛盾がなければ Yes を出力。

計算量

• 時間計算量: \(O(N \times M)\)
  各要素に1回ずつアクセスするだけなので線形時間。
• 空間計算量: \(O(N \times M)\)
  すべてのメモを保持する必要がある。

実装のポイント

• 各位置ごとに独立に処理できるので、ループを入れ替えて位置 \(j\) を外側に持ってくると見通しが良くなる。

• 値の集合を管理するのに set を使うことで、値の種類数を簡単に求められる。

• 値の範囲（\(0\) 〜 \(10^9\)）は、矛盾がなければ自動的に満たされるので、最後に1回だけチェックすれば十分。

  ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # メモを読み込む
    notes = []
    idx = 2
    for _ in range(N):
        note = list(map(int, data[idx:idx+M]))
        notes.append(note)
        idx += M
    
    # 各位置jについて、矛盾がないかチェックし、P_jの候補を求める
    for j in range(M):
        # 位置jにおける、-1でない値を集める
        values = set()
        missing_positions = []  # -1があるメモのインデックス
        
        for i in range(N):
            val = notes[i][j]
            if val == -1:
                missing_positions.append(i)
            else:
                values.add(val)
        
        # もし-1でない値が2種類以上あれば不可能
        if len(values) > 1:
            print("No")
            return
        
        # 値が1種類であれば、それがP_jの値
        if len(values) == 1:
            p_val = values.pop()
            if not (0 <= p_val <= 10**9):
                print("No")
                return
            # -1の箇所もこの値にできることを確認（これは常に可能）
            continue
        # valuesが空 => 全て-1 => 任意の値（例えば0）を選べばよい
        # 特に問題なし
    
    print("Yes")

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。