ABC147 C - HonestOrUnkind2
ABC147は参加できなかったんだが今年のABCのC問題では一番難しいと一部で言われていた問題。 題材はbit全探索というアルゴリズムでbit全探索で集合の全パターン列挙するというのも慣れていなかったので当然難しかったんだが、正直者の発言が集合を満たせばその集合には妥当性があるという考察も難易度高いと思った。（参加しても100％解けなかったと思う
前提知識
今回の問題を解く際に用いるbit全探索で重要な概念を自分の理解のために書いておくと
- bitシフト
bit演算における桁操作。 左側にシフトすれば2、右側にシフトすれば1/2の操作になる。
コードのREPの1<<nの部分だと例えばn=3だったら左に3桁ビットシフトして 1000 となる。
なのでREP(i, (1<<n))のiは 1 -> 10 -> 11 -> 100 -> 101 ...とループする。
同様にi >> lはiを右にlシフト、つまり(1/2)^l操作していることになる、例えばi=4,l=2だとすると100->001となって4*(1/2)^2で1になるといった具合。
- bit演算(&)
コードでいうとif (i & (1 << l)) の部分。同じ桁の値がともに1であればtrueとなる。言い換えるとiのl桁目が1であればtrueとなる。
以下が提出したACコード、全探索した集合をvectorにpushしてるが手練の方の回答と比べると全然洗練されていない。
Submission #9248259 - AtCoder Beginner Contest 147
改善と気付き
改善
もう少しビット演算らしく記述したのが以下のコードで変更点としては主に2つ
- 右ビットシフトで集合のビットが立っている（正直者）ことを判別する
コードでいうとif(1&(i >> l)) のところ。例えばi=4だと集合としては(1,0,0)になるのだがこれを各人の発言に照らし合わせて(3人目, 2人目, 1人目)とすると、3人目が正直者であるかを検証するときに3桁目のビットが立っているかをビット演算で判別する必要がある。
このときに右側に2桁ビットシフトすると100 -> 001となって1&(i >> l)はtrueとなり各人が正直者か否かを判別可能となる。
- 右ビットシフトで正直者の発言の妥当性を検証する
与えられた集合が正直者の発言と矛盾しないことを検証するときに同様に右ビットシフトを利用している。
コードでいうとif(vp.at(l).at(k) != -1 && (i >> k & 1) != vp.at(l).at(k))) の部分。
ここではlが発言者、xが対象者を表すのでvp.at(l).at(x) != -1 で自分自身が対象ではないこと、(i >> k & 1) != vp.at(l).at(k) で集合における対象者の実体（Honest or unkind）と発言が矛盾しないことを検証している。
Submission #9263988 - AtCoder Beginner Contest 147
気づき
- 結局は表題に対する考察が重要
この問題でいうところの正直者の発言を満たす集合は妥当であるという考察のこと。不親切な人の発言はどうだっけとか考えて沼にハマったんだが不親切な人は嘘か本当かどっちの発言をしているかわからないので検証不要だと気づけなかった。bit全探索という方法を知っていても結局この考察ができないとACにはならなかったなと思った。
- 闇雲にログを仕込むよりも理論的に正しいと思われる仮説を先に導出する、ログはその検証のために仕込む。
ACにならないコードを書いたときにとりあえずログを仕込んで動作を追いかけがちなんだが、論理的にいったらこのコードの次はこのログが表示されるはず、みたいな仮説を持った上でログを仕込んだほうがバグに気づきやすいと感じた。普段実務でやってはいることではあるが時間制限がある中だと意識しないと忘れる。
- 変数名やログはわかりやすいものにする
競技プログラミングのコードは変数名に意味づけされていなかったりすることが多いがバグがあるときに気づきにくくなるし自分が書いたコードを読み直す必要が出たときに理解しにくいのでこの点意識する。
