概要

各メモにちょうど1箇所の欠損値（-1）がある複数のメモが、同じパスワードを表しているかどうかを判定する問題です。

考察

すべてのメモが同じパスワード \(P\) を表すためには、各列（パスワードの各桁）において、すべてのメモでその桁の値が一致している必要があります。ただし、-1（欠損値）の場合は値が任意であるため、無視できます。

重要な観察点は、同じ列に2つ以上の異なる非-1の値が存在する場合、それらのメモが同じパスワードを表すことは不可能だということです。なぜなら、-1でない値は正しい値として固定されているため、それらが異なると矛盾が生じるからです。

逆に、各列について非-1の値がすべて同じか、あるいは非-1の値が存在しない場合（すべてのメモでその列が-1の場合）は、矛盾なく一つのパスワード \(P\) を構成できます。

アルゴリズム

1. 入力データを読み込み、\(N\) 個のメモを二次元リストとして格納する
2. 各列（\(j = 0\) から \(M-1\) まで）について、すべてのメモのその列の値を調べる
3. 各列に対して：
   • 非-1の値が存在する場合、最初の非-1の値を基準値とする
   • その列の他の非-1の値と基準値を比較し、1つでも異なる値があれば「No」を出力して終了
4. すべての列で矛盾がなければ「Yes」を出力する

計算量

• 時間計算量: \(O(N \times M)\)
• 空間計算量: \(O(N \times M)\)

ただし、問題の制約で \(N \times M \leq 2 \times 10^5\) であるため、このアルゴリズムは十分効率的です。

実装のポイント

• 入力データの読み込み時に、一度にすべてのデータを読み込むことで効率化しています

• 各列ごとに値を集計する代わりに、メモを走査しながら直接比較することでメモリ使用量を抑えています

• 早期リターン：矛盾が見つかった時点ですぐに「No」を出力して処理を終了します

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print("No")
        return
        
    n = int(data[0])
    m = int(data[1])
    index = 2
    memos = []
    for i in range(n):
        row = list(map(int, data[index:index+m]))
        index += m
        memos.append(row)
    
    # 各列ごとの値（-1以外）を保存するリスト
    columns = [[] for _ in range(m)]
    
    for i in range(n):
        for j in range(m):
            val = memos[i][j]
            if val != -1:
                columns[j].append(val)
                
    # 各列をチェック：同じ列に異なる値が2つ以上あればNo
    for j in range(m):
        if len(columns[j]) == 0:
            continue
        first_val = columns[j][0]
        for val in columns[j]:
            if val != first_val:
                print("No")
                return
                
    print("Yes")

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。