AtCoder Beginner Contest 138

A - Red or Not

　これAtCoderの色システムと対応しているの？上のほうがどうなっているのかよく知らないし3200以上がredなのかとやや混乱しかけた。

B - Resistors in Parallel

　doubleを信じて愚直に計算するだけ。解説PDFを見ていて気づいたんだけど、桁数を指定して出力するときstd::setprecisionだけで良いのか。std::fixedも指定しなきゃいけないのかと思っていたが、0が続く場合にそれが出力されるかどうかという違いがあるだけっぽい。機械学習とかで損失の桁を揃えて綺麗に表示したいときは当然これ使うわけだけど競プロではいらなかったか。

　提出

C - Alchemist

　無駄にstd::priority_queueを使ってしまったが混ぜることで大きくなるわけがないんだからソートして小さい方から混ぜていくだけで良かったか。

　提出

D - Ki

　妙に簡単で拍子抜けした。最近はdfsをstd::stackを使ってそのまま書くことがマイブーム。

　提出

　最初、順番を考慮せずに $t$ で各文字が出現した回数を上回るような位置を二分探索すればいけるじゃんと思って書き始めたが途中でミスに気づく。時間をロスして焦り始めたが、冷静になれば $s$ における各文字の位置を記録して、次に到達するべき文字で二分探索すれば良いとわかって落ち着いた。細かいところだけど出現位置をstd::vectorで取って毎回二分探索するんじゃなくてstd::setで保持して降りていくだけの方がなんか好みの実装だったな。書いていたときはそうできなかったが……。

　提出

F - Coincidence

　 $x$ が $y$ の最左ビット以外を適当に降ろしたものだというのは実験してなんとなくわかったけど、 $L \le x$ とか $x \le R$ とかそういう制約を考えると数えられない。ある $y$ を固定したときの適切な $x$ の数は $O(\log L)$ で求められる（たぶん）んだけど、そもそも $y$ を $L$ から $R$ までループするということができないので……というところで思考が詰まって終わった。