ABC150の解説です。
2回目のunrated。
なんだしなんだしABC。
今回はFの解き方がかなり微妙で未証明・テストケースに勝った感じなので、解説というより解き方の説明になります。Eまではちゃんとした解説です。
A問題
if文を知っていますか？僕は知っています
B問題
std::string::substrを知っていますか？僕は知っています（知らなくても解けます）
C問題
std::next_permutationを知っていますか？僕は知っています（知らないと辛そう）
D問題
まず、$a_i$ それぞれが素因数に $2$ を持つ個数が全部同じでないと答えが存在しません。$X$ に何を代入しても $N$ 通りの $p$ がすべて整数になることがないからです。以降では、このような場合は除いて考えます。
次に、 $a_i$ すべての最小公倍数 $L$ を求めます。$L$ が奇数の場合、答えが存在しません。$(p+0.5)$ の形の数にいかなる奇数をかけても整数にならないからです。以降では、このような場合は除いて考えます。
まず、問題文の式の両辺を $2$ 倍すると、$2X$ は $L$ の倍数であることがわかります。
また、 $X$ が $L$ の倍数である場合、 $a_i$ で割った商が整数になってしまうので、当然条件を満たしません。
逆に、 そうでない場合は、必ず条件を満たします。（$\frac{L}{2}$ が条件を満たすことを考えて、そこから帰納的に考えると簡単に証明できます）
よって、$M$ 以下でそのような数の個数を数えればいいです。愚直に数えると間に合うはずがないので、$\mathrm{ceil}(\frac{M-\frac{L}{2}}{L})+1$ です。
E問題
Dより証明は簡単です。
まず、変えなければいけないビットが決まっているとき、コストの小さい方から取るのが最適です。かなり自明なので既知とします。
ここからは、それぞれのビットを独立で考えます。
$1$ 回あたりのコスト $c$ のビットを変更するのにかかるコストの合計を考えます。
まず、このビットが異なる場合の数は $2^{2n-1}$ です。また、残りのビットでまだ異なっている可能性があるのは、コストが $c$ より大きいビットのみで、そのうち異なるものの個数の期待値は、当然個数の半分です。
よって、これらと $c$ をかけあわせたものがかかるコストの合計です。これを全部のビットについて計算して足せば答えが出ます。おしまい。
コストが同じビットが含まれている場合も、順番を先に決めてしまえばいいだけなので、ソートをしてindexをもとに計算すると楽です。
F問題
正しい解法は知りません。僕が通した嘘解法だけ書きます。
よい子の皆さんはマネしないように…
・$k$ を決め打ちする。そのとき、$a'$ と $b$ の各要素のxorをとったとき、これが全て一致すれば組がひとつ見つかり、そうでなければこの $k$ では実現できない。ここで、要素を全部試したい。
・要素を全部試すと計算量オーダーが $O(N^2)$ になってしまい。間に合わない。どうにかしたい。
・全部試すのは時間がかかりそうなので、$5000$ 個だけ試してみる。
・通る。
以上でした。
愚直な $O(N^2)$ でも、落ちるのは $3$ ケースだけだったので、ランダムに並び替えをするなどの対策をすれば、その $3$ つが強いケースだったとしても通っていたかもしれません。
おわりに
このあとのこどふぉで代わりにレートを上げようと思います
※2020/01/11 追記:下がりました
明後日も解説を書くかもしれないので、よろしくお願いします。