5完
各問題
A - Adjacent Product
いわれたとおりやりましょう。
B - Piano
いろいろ考え方はある気がしますが、自分は S を充分な数(200 もあればよい)つなげた文字列を作って、W + B
の幅に w
と b
がいくつあるかを一つずつずらしながら数えていきました。
制約が小さいので毎回いちいち数えても間に合いますが、新しく範囲に含まれた文字の分を足して範囲外になった文字の分を引いていけば効率よくできます。
C - Σ
最初に仮の答えとして K * (K + 1) / 2
と置きます。これはいうまでもなく、A の中にどれも現れなかった場合の答え(1からKまでの和)です。
あとは A の要素を一つずつみていって、K 以下のまだ現れていない数があれば仮の答えから引いていけばよいです。
D - Gomamayo Sequence
隣接する二文字のパターンは i 文字目と i + 1 文字目 がそれぞれ 00
になるときと 11
になるときの (N - 1) * 2
通りなので、それらをすべて調べます。
隣接する以外の場所は、i が偶数で 0
の時、その左については偶数文字目が 0
、右については奇数文字が 0
、など一意に決まりますので、あらかじめ偶数文字目が 0
のときと偶数文字目が 1
のときのコストの累積和を求めておけば、O(1) で取り出すことができます。
E - Paint
最後に塗ったものが優先されるので、操作を後ろからみていって、どの行とどの列が塗られたかに注意して色の数を数えていけばよいです。
行を塗るときはまだ塗られていない行について W - (すでに塗られた列)
分塗ることができ、列についてはまだ塗られていない列について H - (すでに塗られた行)
分塗ることができます。
色 0 は初期値を H * W
として、塗られるたびにこれを引いていく必要がありますが、0になった時に答えの出力に含めてしまわないよう注意です。
F - SSttrriinngg in StringString
二分探索で行けそうなのですが、行ききれず...。
まとめ
D の方針が固まるまでがめちゃくちゃ時間がかかってしまったのがあれなんですが、また一発で水色復帰できた(っぽい)のでよしとするか。