ABC171 参加メモ - tinumu's reminder

atcoder.jp
速さが…足りない！ 427th Perf=1901 1917->1916(-1)

A - αlphabet

isupperを知っている喜びを噛み締める

B - Mix Juice

ソートして $K$ 要素を小さい順に足す

C - One Quadrillion and One Dalmatians

$26$ のべき乗を引いていくと文字数が少ないときのナンバリングが消えていくので最終的に $26$ 進数の値になってくれる。デコードして終わり

D - Replacing

今どの数字が何個あるかは高速に追えるので、それをシミュレーションして総和も同時に計算していけばいい。

E - Red Scarf

$N$ が偶数のときは $a_i$ を全てxorしたときの値が全てのすぬけくんのスカーフの非負整数のxorになっているので、その値から $a_i$ に xorすれば答えが出てくる。

F - Strivore

$K+|S|$ 文字を「置く」事を考える。
これは $?$ を置くか、 $S_i$ を置くかということである。
現在 $k$ 文字目を置こうとしていて、 $S_i$ を置こうか否かというようになっているとき、もし、 $S_i = c$ の $c$ を置こうとしているなら、 $S_i$ を必ず置くものと見ても構わない。明らかに、後に $?$ を残しておいたほうが見られるパターンは多いし、置かない理由が他に無いと思う。
このような遷移にしておくと、実はパターンの重複も起こらず、全パターン列挙できる。
置くときに分岐が発生しないので重複はないし、 $S_i$ 置くことでのパターンの欠如はないのでそうだと思う。

すると、 $dp_{k,i}$ : $k$ 文字目まで置いていて、現在 $S_i$ を置こうとしているときのパターン数
というDPが生まれるが、遷移を見てみると、DPの答えが二項係数に $25^{k-i}$ つけたような数になる。
$i=N$ のとき、少し挙動が異なるが、もう $i \gt |S|$ があるように見てしまって、 $\displaystyle \sum \limits _{i=|S|}^{K+|S|} dp_{K+|S|, i}$ を見てしまっても、最終的な答えが変化しない。というのも、文字がどうであるかはそもそも関係無かったりする。
DPが二項係数に依存するということは、実際にやらなくても求まることがわかるので、 $\displaystyle \sum \limits _{i=|S|}^{K+|S|} \binom{K+|S|}{i}$ を求めて、これが答えになる。