ABC154の解説です。
今回はペナルティも多く、全完するまでに時間もかかり、自分としては反省すべき結果となりました。
では、解説に入ります。
A問題
文字列の一致判定をしましょう。
あまりA問題としては良問ではない気がしました。気のせいかもしれません。
B問題
問題のネタ性がいいですね。
文字列の長ささえわかれば'x'
をその個数だけ出力すればいいですが、愚直に文字列を置き換えてもいいです。
C問題
ソートして隣り合った要素を比べるのが楽です。
mapやmultisetなどを使ってもいいです。
D問題
$i$ 番目のサイコロについて出る目の期待値を考えると、$(1+p_i)/2$ です。
これを連続する $k$ 個について求めて和を取ると、その区間での $p_i$ の総和を $s$ として、$(k+s)/2$ が答えになります。区間を一つずつずらしていけば $s$ は $O(1)$ で更新できるので、$O(N)$ でこの問題が解けます。累積和を取っても同様の操作が実現できます。
ところで、オーバーキルですが、Segment Treeを使いたくなりませんでしたか?僕はなりませんでした。
E問題
典型的な桁DPの問題です。
桁DPの解説はこちらの @drken さんの記事へどうぞ。
一瞬オーバーフローが怖くなりますが、桁DPを落ち着いてやればオーバーフローは起こりません。(そもそもサンプルに最大ケースが置いてある)
${\rm dp}[i][j][k]=i$ 桁目までで $j$ 個 $0$ でない数字を含むもの
とし、$k$ で桁あふれを管理すればよいです。
これで $O(\log N)$ となります。
F問題
すべての場所について通り数を求めては間に合いません。
求める領域が長方形になっていることを利用して、長方形を囲んでいる部分の通り数から中の値をまとめて求めることを考えます。
長方形の左と下の部分の通り数をそれぞれ求め、それを動的計画法のイメージでグリッド上に伝播させていき、最終的に長方形の中に何度加算されるか考え、それをまとめて足せばよいです。
対称性から、下の部分に対してのみ考えます。
たとえば、$f(r_1,c_1-1)$ の値の何倍が長方形の中に加算されるか考えると、
{}_{c_2-c_1+1} C_{c_2-c_1},{}_{c_2-c_1+2} C_{c_2-c_1},\cdots{}_{c_2-c_1+1+(r_2-r_1)} C_{c_2-c_1}
の総和になります。
同様に、他の場所においてもこのような組み合わせの個数の総和で係数を求めることができるので、計算に無駄がないように順次求めていくと $O(r+c)$ で解くことができます。
おわりに
少し解説が雑になったかもしれません。ごめんなさい。(こどふぉまで時間がない)
Fのような問題をさっと解ききる力が、必要ですね。