概要

\(N\) 人のメモ（それぞれちょうど1箇所が \(-1\) で欠損）が、すべて同一のパスワードを記録したものであり得るかを判定する問題です。各位置について、\(-1\) でない値がすべて一致しているかを確認すればよいです。

考察

重要な気づき

パスワードを \(P = (P_1, P_2, \ldots, P_M)\) とします。各メモ \(i\) について、\(S_{i,j} \neq -1\) ならば \(S_{i,j} = P_j\) でなければなりません。

つまり、ある位置 \(j\) に対して、\(-1\) でない値が複数のメモに存在する場合、それらはすべて同じ値でなければならないということです。

具体例で考えてみましょう。\(M = 3\) で以下の2つのメモがあるとします：

• メモ1: 3 -1 5
• メモ2: -1 7 5

位置1を見ると、メモ1は \(3\)、メモ2は \(-1\)（不明）→ 矛盾なし（\(P_1 = 3\)） 位置2を見ると、メモ1は \(-1\)（不明）、メモ2は \(7\) → 矛盾なし（\(P_2 = 7\)） 位置3を見ると、メモ1は \(5\)、メモ2は \(5\) → 一致しているので矛盾なし（\(P_3 = 5\)）

よって答えは Yes です。

もしメモ2の位置3が \(9\) だったら、位置3でメモ1の \(5\) とメモ2の \(9\) が矛盾するので No です。

なぜこれで十分か

\(-1\) の位置には任意の \(0\) 以上 \(10^9\) 以下の値を入れられるため、制約を生むのは \(-1\) でない位置だけです。すべての \(-1\) でない値が位置ごとに矛盾しなければ、パスワード \(P\) を構成できます。もしどの位置もすべてのメモで \(-1\) であった場合は、任意の値（例えば \(0\)）を選べばよいです。

アルゴリズム

1. 各位置 \(j\)（\(1 \leq j \leq M\)）について、すべてのメモの \(S_{i,j}\) を確認する。
2. \(S_{i,j} \neq -1\) であるものを集め、それらがすべて同一の値であるかを判定する。
3. 1つでも矛盾する位置があれば No、すべての位置で矛盾がなければ Yes を出力する。

具体的には、各位置 \(j\) に対して「最初に見つかった \(-1\) でない値」を記録し（decided[j]）、以降の \(-1\) でない値がそれと一致するかを確認します。

計算量

• 時間計算量: \(O(N \times M)\)
  • すべてのメモの全要素を1回ずつ走査するだけです。制約より \(N \times M \leq 2 \times 10^5\) なので十分高速です。
• 空間計算量: \(O(N \times M)\)
  • メモ全体と、各位置の確定値を格納するための配列が必要です。

実装のポイント

• 配列 decided を None で初期化し、各位置について最初に出現した \(-1\) でない値を記録します。2つ目以降の \(-1\) でない値が異なれば即座に No を出力して終了できます。

• sys.stdin.buffer.read() で入力を一括読み込みすることで、Python でも高速に処理できます。

• 「ちょうど1箇所だけ \(-1\)」という条件は判定ロジック自体には影響しません。どの位置が \(-1\) かに関わらず、\(-1\) でない値の整合性だけを見れば十分です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    # For each position j, collect all non-(-1) values
    # We need to check that for each position, all non-(-1) values agree
    # Also, each memo has exactly one -1
    
    # Store memos
    memos = []
    for i in range(N):
        row = []
        for j in range(M):
            row.append(int(input_data[idx])); idx += 1
        memos.append(row)
    
    # For each position j, find the "decided" value (if any)
    # All non-(-1) values at position j must be the same
    decided = [None] * M  # None means no constraint yet
    
    for i in range(N):
        for j in range(M):
            v = memos[i][j]
            if v != -1:
                if decided[j] is None:
                    decided[j] = v
                elif decided[j] != v:
                    print("No")
                    return
    
    # Now, decided[j] is either None (no non-(-1) value seen) or a specific value
    # For positions where decided[j] is None, we can choose any value in [0, 10^9]
    # 
    # But we also need to verify: the decided values are all in [0, 10^9]
    # Since input guarantees S_{i,j} in [0, 10^9] when not -1, this is automatic.
    # For None positions, we just pick 0 (any valid value works).
    
    print("Yes")

main()

---

この解説は claude4.6opus-thinking によって生成されました。