ハッシュ衝突
ハッシュ関数は完璧ではなく、まったく異なるデータから同じハッシュ値が得られることがあります。これは、入力とハッシュ値が1対1で対応しなくなることを意味し、異なる文字列が同じハッシュ値を持ったり、2つの数値が同じハッシュ値になってしまったりする場合があります。ハッシュの衝突が起きると、状況によってはセキュリティ上の問題やパフォーマンスの低下を招く可能性があります。たとえば、整数のペア (a, b) をハッシュ値にマッピングする単純なハッシュ関数を使う場合、多くの (a, b) ペアが同じハッシュ値を共有してしまうかもしれません:
以下は同じハッシュ値となる (a, b) の例です:
- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
仮に、同じハッシュ値をもつように意図的に作られた (a, b) のリストが手元にあったとすると、特定の値を探したり、「(a, b) がリストに含まれているか」を確認する処理が非常に非効率になったり、実装次第では誤動作を起こす恐れもあります。
ハッシュ衝突はセキュリティ上の脆弱性につながる場合があります。ユーザーのパスワードは、万が一データベースが漏洩してもパスワード自体は流出しないように、通常はハッシュ化して保存されます。しかし、もしハッシュ関数の質が悪く衝突が多いと、攻撃者が正しいパスワードを当てずとも、偶然同じハッシュ値が得られるパスワードを使って不正ログインできてしまうかもしれません。つまり、無作為に生成したパスワードのハッシュと本人のパスワードのハッシュが一致すると、システムからは同一人物として扱われてしまうということです。
良いハッシュ関数は、衝突をできるだけ少なく抑えることができます。一般的に、組み込みのハッシュ関数はランダムな入力に対しては十分に良好な動作を示します。しかし、入力データの種類や特定の要件によっては、自分でカスタムのハッシュ関数を実装する必要がある場合もあります。
チャレンジ: 衝突をチェックする
整数のペア (a, b) を整数にマッピングするハッシュ関数 h が与えられたとき、与えられた入力の中に衝突がないかを確認する必要があります。具体的には、次のように定義されるハッシュ関数が、入力されたペアについて衝突を起こさないかを調べます。もし衝突がまったくなければ "Yes"、衝突があった場合は "No" を出力してください。
入力
最初の行に整数 n (1 ≤ n ≤ 10 000) が与えられ、これはペアの数を表します。
次の n 行には、空白区切りで整数 ai, bi (0 ≤ ai, bi ≤ 10^9) が与えられます。これらのペアはすべて異なるものとします。
出力
与えられたペアに対し、定義されたハッシュ関数 h(a, b) に衝突が一切なければ
Yes、衝突があれば No と出力してください。例
入力 | 出力 |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB