問題
考察
$N$この商品のうち、ある商品に対して上位互換に値する商品の組み合わせは存在しますかという問題です。上位互換と言える条件は問題文に示されています。$N$も$M$もあまり大きな値を取らないです。そのため、$N$この商品のうち2個の組み合わせを選ぶ選び方を全探索しても十分間に合います。全ての選び方を試し、条件にあるものが無いかを探しましょう。
条件が複雑なため、満たしているかの判定が難しいです。1つ1つ確実に実装していきたいです。
下記の内容のものを実装できれば条件を満たすかの判定ができます。
- $P_j > P_i$ならば、条件を満たさないことが確定。次の組み合わせを調べる(continue)
- それ以外なら2へ進む
- 「$i$番目の製品がもつ機能」のうち、「$j$番目の製品が持ってない機能」が1つでも存在すれば条件を満たさないことが確定。次の組み合わせを調べる(continue)
- それ以外なら3へ進む
- $P_i > P_j$を満たすならば、上位互換なる組み合わせが存在することが確定。"Yes"を出力して終了
- それ以外なら4へ進む
- 「$j$番目の製品がもつ機能」のうち、「$i$番目の製品が持ってない機能」が1つでも存在すれば上位互換なる組み合わせが存在することが確定。"Yes"を出力して終了
- それ以外なら次の組み合わせを調べる
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。