ABC158 参加メモ - tinumu's reminder

atcoder.jp
E、めちゃくちゃ難しくないか？
1905 -> 1936(+31 Highest) Perf=2180 でした　いい感じだね

A - Station and Bus

差がなければだめ AAA か BBBが "No", ほかは "Yes"

B - Count Balls

なんか、(A+B)で周期が来るので、最後のところでどのくらいAを入れられるかを考えるとACする

C - Tax Increase

$1$ から $10000$ くらいまで全探索します　見つけたら出して終わり　見つけられなかったら -1

D - String Formation

反転をしなくても、反転したことにできるので、フラグを持っておいて、適切に処理します

E - Divisible Substring

これ難しい
位置 $i$ からのsuffixを持った数字を $U_i$ とすると、位置 $i$ から位置 $j$ までの文字列の数字は、 $\frac{U_i - U_{j+1}}{10^{N-{j+1}}}$ になる。これがわり切れるかどうかを見れば良い。
ところで、 $10$ と $P$ が互いに素であれば、 $\frac{U_i - U_{j+1}}{10^{N-{j+1}}}$ が割り切れることと、 $U_i - U_{j+1}$ が割り切れることが同値になる。
$(=>)$ は倍数になっているので明らか。
$(<=)$ はある $x$ が $0$ で割り切れないとき、 $x \times 10^n(n \in \bf{N})$ も割り切れないことから( $10, P$ が互いに素であると、法 $P$ 上の $10$ は $0$ にはならないため $10$ を何度かけても $P$ で割り切れない)、対偶を取ると、証明できる。
このようにすると、 $U_i - U_{j+1} \equiv 0 (\mathrm{mod} P)$ を満たしていればよく、しかもこれは式変形をすると、 $U_i \equiv U_{j+1} (\mathrm{mod} P)$ であるため、等しいペアを見つける問題に落とされるので、ある値 $x$ が何個あるのかを保存しておきながら見ていくことで、 $\mathrm{O} (N+P)$ で解ける( $P$ が大きいと mapを使って $O(N \log N)$ で解くと思う)。

ところが、互いに素ではない $2, 5$ については、先ほどの条件の $(<=)$ を満たさないことから、上の解法では解けない。
しかし、 $2, 5$ はそもそも、末尾の桁が $P$ で割り切れればいいので、割り切れるものを見つけたら、すぐにそのインデックスである $i$ を足せばいいので、簡単に処理できる。

F - Removing Robots

あるロボットが動くと、どのロボットが動いてしまうかということを考える。
これは再帰的に繰り返されるので、再帰の終端点からボトムアップに処理していくと良い。
あるロボット $i$ が動くことによって、ロボット $j$ が動く時、ロボット $j$ が最終的にどのロボットまで動かすかが分かっていればいい。
しかも、 $i < j$ であるので、これは後ろからDP をすることで解くことが出来る。
すると、このような漸化式になる。
$dp_i = \max\nolimits_{X_i \leq X_j \lt X_i+D_i} dp_j$
$X_i + D_i$ より位置が小さい一番右のロボットはしゃくとりとか lower_bound とかですぐ求まる。
そして、 $X_i \leq X_j \lt X_i+D_i$ であるようなロボット $j$ は連続しているので、この遷移は、 $\max$ を求めるSegment Tree で $\mathrm{O}(\log N)$ で処理できる。

このDPを処理できれば、場合の数を求めればよいが、これも簡単なDPで求められる。
ロボットを使う/使わないで分けて、使うときは、影響しない一番左のindexを $dp_i$ から参照して遷移、使わない時は、 $i+1$ に遷移するようにしてやれば、 $\mathrm{O}(N \log N)$ でこの問題を解くことが出来る。