AtCoder Beginner Contest 138
2日連続でACのコンテストじ
A - Red or Not
3200未満がredで3200以上がsと出力する
逆じゃん！というネタですね。
redじゃなくてresとtypoして危うくペナ踏むところでした。あぶねえ
B - Resistors in Parallel
問題：逆数を足したものの逆数をとる
やるだけですが、小数点以下を表示させる方法知らないと厳しいです。
というかググれば出てきます。
C - Alchemist
問題：価値vのものがn個あります。n-1回操作をします
操作：価値xと価値yのものを除いて価値（ｘ＋ｙ）／２のものを加える
最後のものの価値を最大化せよ
考察：
３つで考えます。それぞれの価値はｘ、ｙ、ｚです
前からマージするとき最後に残るものの価値ｗは
((x+y)/2+z)/2
=x/4+y/4+z/2になります
最後のほうにマージしたほうが寄与が高いので、昇順にマージすれば最適です。
D - Ki
問題：n頂点の根付き木が与えられます。クエリQ個を処理した後の各頂点の値を求めよ
クエリ：頂点ｐの部分木にｘを加える。
考察
愚直にやったら無理そうです。
なので、先にクエリを読みます。
ある頂点ｖを部分木の一部とする根頂点は、vから根１までのパスに含まれます
はじめ各頂点で求めようとしたんですけど、dfsしながら子に答えを足していけばよいことに気づきました。
ついったで話題になっていたんですが、根付き木の辺は無向か有向かということでした。
調べた感じだと無向辺になりそうです。
ただ問題文が「根付き木が与えられる」となっていたので、各頂点の親を与えるような感じですよね。入力形式に違和感を感じました。
まあ自分の知識不足をテストケースの弱さに助けられた部分もあるのでこれからは気を付けます。
特に記述がないときは無向辺として処理しましょう。
E - Strings of Impurity
問題：文字列ｓ、ｔが与えられる。ｓを無限につなげたｓｓの前からk文字が、（連続しなくてもよい）ｔの部分文字列（subsequence?)になるような最小のkを求めよ
考察：
愚直に考えると、tの各文字についてsのindexを進めていき、一致したらtを先に進めるとすればよいです。
このままでは最大で|s||t|かかるので間に合いません。
アルファベットごとに整理しておくと、二分探索で高速化できます。
開始位置が１になっていて１ペナくらいました。もったいない。
F - Coincidence
問題：L<=x<=y<=Rであるｘ、ｙでy%x==x^yとなるx、yの組の数を求めよ
考察：
まずy%x=zとします。
x>zより、yとxで桁が違うと成り立ちません。
なぜならx^y>ｘになってしまうからです。
各桁数で調べればよいです。
xi,yi：ｘ、ｙのiビット目とします
x<=yから、0,0 0,1 1,1の３通りになります。
k+1桁の整数を調べるとき、2^k~2^(k+1)-1が対象です。
[L,R]に含まれている場合3^k通りです。
中途半端なときだけ考えればよくて、これは桁DPでできます。
バグります。終わりです。
※やーーっと通せたので追記
3つの関数を定義します。
calc_x(k)：xがL以上を満たすようなk桁の場合の数。y<=Rが常に成り立つ
calc_y(k)：yがR以下を満たすようなk桁の場合の数。x>=Lが常に成り立つ
calc_xy(k)：L<=x<=y<=Rを満たすようなk桁の場合の数。
まずx、yのみで考えます。
k桁なので1<<kがあります。
k-1～0桁目での挙動を考えることになります
Li=1：xi=0にすると必ず小さくなるので1にするしかないです
Li=0：xi=1にすると必ず上回るので残りのbit分の3^(i-1)通りがあります。
xi=0にする場合のみを次から考えます。
Ri=1：yi=0にすると必ず下回るので残りのbit分の3^(i-1)通りがあります
yi=1にするときのみ次にいきます
Ri=0：yi=1にすると必ず大きくなるので0にするしかないです。
以上からcalc_x,calc_yではｘ、ｙを1つに決めながら下の桁へ進めます。
次に進むとき上の桁が2通りあることに注意しましょう。
次にcalc_xyを考えます。
上を組み合わせて、矛盾が生じるところはreturn
どちらかだけ自由になればcalc_？を呼び出しましょう
どちらも自由になることはありません。
最後にx=Lやy=Rに定まっているので、その分を足したら答えになります。
bitごとでよいことに気づいたら素早く実装できました。
桁DPと、bitの扱いに慣れていなかったのが敗因ですね。
0か1しかないというのはすごく扱いやすいことだなと実感しました。
感想
久しぶりにABCであったまりました！
というかF解いた人が少なかったからですけどね。
Eまではまあ早くもなく、遅くもなくというか、１ペナが大きかったくらいです。
1.5か月のコンテストでレート伸びたのが1回で+16だったので、昨日今日で+113してるのは非常にうれしいです。
まあHighestじゃないんですけど
とにかく、慢心せず黄色目指して頑張ります。またな
