| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
52分6完（ペナルティなし）で21位でした。
ここ2ヶ月くらいでは一番の高順位でした。
最近のABCでは簡単セット？
Fが細部でミスしやすいくらいでしょうか。ほかの問題は実装に悩む要素も少なかったように思います。
問題B – Resistors in Parallel
numpyに慣れたい人は適当な練習問題でしょうか。
\[ \frac{1}{\frac{1}{A_1}+\cdots+\frac{1}{A_N}} \] は
1/((1/A).sum())と書くだけでよくて簡潔です。
※ numpy は、難しいことやって高速化を得る方法というよりも、簡単なことが簡単に書けるので便利です。
問題D – Ki
各操作と、最終状態の関係を考えると、
・頂点 $x$ には、最終状態で、$x$ の親のどこかに足された値の合計が加わる
というルールだと分かります。すると、根から順に、その頂点の最終値を計算していくことができます。
より詳細には、$x$ の親が $y$ であるとき、最終的な頂点 $x$ の値と最終的な頂点 $y$ の値は、直接 $x$ に足しこまれた値だけの違いしかありません。よって $x$ の値は $y$ の値からすぐに計算できます。
再帰関数による dfs → ■
list での dfs → ■
どちらでも書ける場合は、深い関数呼び出しを避けた方がやや高速のようです。
問題E – Strings of Impurity
$t$ の一文字ずつ見て行って、sのどこに現れるかを見ていくことゲームです。
・contestcontestcontest
・contestcontestcontest
・contestcontestcontest
sで1度も使われていない文字が出てきたらアウト（答は’-1’）。
そうでないなら、文字列を追加で1周するまでに必ず1度見つかります。あとは次の課題をクリアすればよいです。
【課題】sにおいて、$x$ 文字目以降で指定のアルファベットが最初に出てくる位置を計算せよ。
各アルファベットの出現位置のリストを事前計算しておくと、
【課題】リストから、$x$ 以上であるような最小の元を取り出せ。
というような課題に置き換えることが可能です。これは、リストがソートしてあれば二分探索により高速に計算できます（今回は自然に作ればソート済リストになる）。
pythonの場合は、二分探索は bisect を使うのが簡単です。
問題F – Coincidence
・結局、商が1（$x > 2y$）かつ $y = x \ \mathrm{xor} \ (y-x)$ という条件
ということも分かります。また、$y = x \ \mathrm{xor} \ (y-x)$ については、2進法で繰り上がりのない足し算なっていることと同値です。
というような条件が得られます。あるいは bit列を集合と見立てて
と書いてもよいでしょう。これを数える問題です。解法は、俗に桁DPと呼ばれているっぽいものだと思います。
「上の方とか下の方が適当な条件になっているものを数えようとすると、それは小さい桁数のときの問題に帰着できるよ」というタイプ。
・$F(L,R)$：$L\leqq x\leqq y\leqq R$ かつ $2x > y$ かつ $x\subset y$ となる $x,y$ の個数（答になるやつ）。
・$G(L,R)$：$L\leqq x\leqq y\leqq R$ かつ $2x \geqq y$ かつ $x\subset y$ となる $x,y$ の個数（補助的に）。
などと置きます。これをそれぞれ、1の位（偶奇）で分割して漸化式（DP）を作ります。
$2x > y \iff 2x’ > y’$ であり、$\lceil\frac{L}{2}\rceil \leqq x’,y’\leqq \lfloor\frac{R}{2}\rfloor$ なのでこれは $F(\lceil\frac{L}{2}\rceil, \lfloor\frac{R}{2}\rfloor)$ 通り。
