2完。
各問題
A - Dial Up
S_1とT_1が一致している場合と、i > 1でT_i-1とT_iが一致している場合は、aをシフトさせる動作が必要ないので操作回数は1回です。
S_1とT_1が一致していない場合、またはS_1とT_1が一致していてかつT_i-1とT_iが「初めて」一致しなかった場合は、aをT_iに一致させるためにS_1から最も近いT_iにシフトさせるためのコストがかかります。
それ以外でT_i-1とT_iが一致しなかった場合は、シフトのコストは1だけ必要です。
また、bにあってaにない数が存在した場合はもちろん-1です。
B - Squares
ちゃんと説明する自信がないので(おい)、まずはソースを見てください。実装はめちゃくちゃ軽いです。
ざっくり説明すると、x^2 - y
が平方数であるということは、x^2-y=z^2
と置けて、式変形してx^2-z^2=y
、さらに(x+z)(x-z)=y
となり、このyはN以下なので、(x+z)(x-z) <= N
となる、(x, z)の組がいくつあるかを探す、ということをしています。(なお、探索部分は簡単な算数で求まるはずですが、考えるのが面倒だったのでにぶたんしちゃいました。)
z=0のとき(x+z)(x-z) = x^2
なので、探索するのはsqrt(x)まででよいとなります。
C - LIS to Original Sequence
ぜんぜんわかりませんでした。
D - Unique Subsequence
一応のぞいてみましたが、のぞいてみただけ。
まとめ
Bは(x+z)(x-z)=y
まで瞬時にたどり着いたのに、そこから考察を詰め切るのも実装に落とすのも時間がかかりすぎてちょっと残念でした。
昨日のEもそんな感じだったし、この辺がわかりやすく壁になってますね。