😊
ABC365 C - Keysを理解し忘れないようにする
問題概要
C本の正しいorダミーの鍵を差し込み、正しい鍵がK本以上の場合、ドアが開く。ドアが開けばo、差し込めなければxとし、それをM回行う。
各鍵の正しいかダミーかの組み合わせの内、矛盾しないケースの数を求める。
ハマった点
各鍵の正しいかダミーかの組み合わせの全列挙をbit全探索するところまでは分かったが、矛盾しないケースをどうコードに落とし込めばいいのか言語化できず。。
解説見た
こちらの記事が大変分かりやすかった。
矛盾しないケースの考え方は以下
- ans変数を用意して各鍵の組み合わせの内、下記条件が成立していればans++する。
- oの場合、C本の内、正しい鍵がK本以上差し込めれること
- xの場合、C本の内、正しい鍵がK本未満差し込められていること
提出コード
Discussion