概要

各メモの「読める値（\(-1\) 以外）」が、同じ位置ごとに矛盾なく一致できるかを判定する問題です。結局は「各列（各位置）で、\(-1\) でない値がすべて同じか」を調べれば十分です。

考察

各メモにはちょうど 1 つだけ \(-1\) があり、\(-1\) の位置はどんな値でも後から補えます。したがって、あるパスワード \(P\) が存在するための条件は次の通りです：

• 位置 \(j\) ごとに見たとき、\(-1\) 以外で書かれている値があれば、それらはすべて同じでなければならない。

もし同じ列 \(j\) に対して、 - あるメモでは \(S_{i,j}=5\) - 別のメモでは \(S_{k,j}=7\) のように異なる値が現れたら、どんな \(P_j\) を選んでも両方を満たせないので不可能です。

逆に、各列で矛盾が一度も起きなければ、 - その列に値が1つでも書かれていればその値を \(P_j\) に採用 - 全部 \(-1\) しかなければ \(P_j\) は任意（例えば \(0\)） とすれば、全メモと整合する \(P\) を構成できるので可能です。

素朴に「パスワード候補 \(P\) を作って全行と照合」するのもできますが、より直接的に 列ごとの制約だけ見ればよい と分かるのが重要です（この問題では \(N \times M \le 2\times 10^5\) なので全要素を一度見る解法が最適です）。

アルゴリズム

1. 長さ \(M\) の配列 col を用意し、各列で「確定した値」を管理する。初期値は未確定（None）。
2. 全ての要素 \(S_{i,j}\) を読む。
   • \(S_{i,j}=-1\) なら制約がないので無視する。
   • \(S_{i,j}\neq -1\) のとき：
     • col[j] が未確定なら col[j]=S_{i,j} としてその列の値を確定する。
     • すでに col[j] が確定していて、それと異なる値が出たら矛盾なので No。
3. 最後まで矛盾がなければ Yes。

具体例： - ある列が [3, -1, 3, 3] のようなら \(P_j=3\) にできる - ある列が [3, -1, 4] のようなら 3 と 4 が衝突するので不可能（No）

計算量

• 時間計算量: \(O(NM)\)（全要素を1回ずつ確認）
• 空間計算量: \(O(M)\)（列ごとの確定値を保持）

実装のポイント

• col[j] を「未確定（None）／確定値」の2状態で管理すると簡潔に書けます。

• 制約で \(N \times M \le 2\times 10^5\) ですが、Python では入力がボトルネックになりやすいので、コードのように sys.stdin.buffer.read() で高速に読み取るのが安全です。

  ソースコード

import sys

def main():
    it = iter(sys.stdin.buffer.read().split())
    N = int(next(it))
    M = int(next(it))

    col = [None] * M

    for _ in range(N):
        for j in range(M):
            x = int(next(it))
            if x == -1:
                continue
            v = col[j]
            if v is None:
                col[j] = x
            elif v != x:
                print("No")
                return

    print("Yes")

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。