■A - Difference Max
xは大きく、yは小さくしたいので
b-cが答え
■B - Round Down
findとsubstr
nposとか扱いたくなければXの末尾に'.'をつける
■C - Doubled
全部試しても10^6なので全部試す。
■D - Hanjo
dfsすれば良い。
ということが思いつかなかったので。
bit全探索をしてbitがA個立っているものだけ考える。
立っているところに縦置きor横置きすればいいので、さらに2^A分全探索する
制約が小さいので2^(HW+HW/2)で済むので十分に間に合う。
■E - Filters
バグらせまくって間に合わなかった。
解説pdfの情報のもたせ方が思いつかなかったので
F(-INF)とF(INF)の値をとりあえず持ってみる。(Fは合成関数)
これが一致すれば、定数関数。
そうでないときはどこかの区間に傾き1のゾーンがあるはずなので、その区間を二分探索で探す。
三点あれば、グラフの形がわかるのでそこから答えを求める。
■F - Substring 2
難しい。解説見てやっとわかった。
以下メモ。
(1,0),(0,1)のときにコスト1がかかるのでxorを使いたくなる。
求めるのは
min(ΣS[i + j] xor T[j]) iはsの開始位置(0 <= i <= S.size() - T.size())、jはTのどこを見ているか。
これはFFTできそうな気がする(らしい)(は？)
Tをreverseすると
min(ΣS[i + j] xor T[(T.size() - 1 ) - j)]となり
SとTの添字の和が定数(i + T.size() -1)になる。
すると答えは
Ci =ΣS[j] xor T[k] (j + k == i)な配列Cの
T.size() -1 <= i <= S.size() - 1の範囲内のminになる
なので配列Cを求めればいい。
xorのままでは扱えないので、掛け算に分解する。
a xor b = a*(1 - b) + (1 - a) *b なので
FFTを２回すると出来る。
