順次追記: 競技プログラミングの知識(小手先のテクニック)

Q. これはなに？

考察で要求された知識や考え方を雑多に書くだけのメモ帳、小手先のテクニック編です。
累積和とかimosとか座圧とか、これ知ってると解けるよ的なやつ。
ちなみに僕が知ってることは省くので、網羅的ではないです。ゆるして。

イベントソート

これすごくない？今回改めて考え直したけど感動しちゃった。

ABC128-E Road Work

これの本質は区間の操作を、イベントとして端点の操作に落とし込むことだと思っています。
いもす法って区間の足し算を、点の足し算引き算に変換するじゃないですか、あんな感じ。
イベントソートは一次元いもすを拡張したものと言えるかも？
この問題において、イベントソートで点の操作に落とし込んで何が嬉しいかというと、「あるイベント（点）までに飛んできたクエリ」を時系列順に処理することができるので、結果的にイベントを全て舐めていくだけで全てのクエリに答えることが出来るんですよね。
日本語難しいね、まあ自分が分かればいいので（最低）

クエリ毎に中央値を求めるやつ

priotity_queを2本持つ！（素振り）

ABC127-F Absolute Minima

中央値よりも大きい値と小さい値の和をそれぞれデータ構造の方に持っておかねばならなかった。

グラフ拡張

ABC132 -E Hopscotch Addict

これかなり好きなんですよね。頂点を増やすだけ！
シンプルだけど賢くてすごい。
ちなみにスタートが「パ」なの気付きませんでした

ある数列の区間和が0になる区間の数を高速に求めるテク

俗に言うZero Sum Ranges。AtCoderではマジで頻出。

Zero Sum Ranges

200点とかウッソだろお前。お前より簡単な400を俺は沢山見てきたぞ。

区間和が0になるということは $S_j - S_i = 0$ になるということで、これは移項すると $S_j = S_i$ となる区間を数えればいいことになる。

なおこれを応用すると、数列の区間和がある数の倍数かどうか判定することもできる。
数列の区間和がある数Mの倍数である = 数列の区間和がmod M で0である
ということなので、累積和をmod(M)で構築しておけばあとは同じようにできる。

最近のAtCoderではこれがメインかも(いかにこの操作に落とし込むかが肝になる)。

ABC158-E Divisible Substring

与えられた数列の連続する部分列を10進表記の整数と見た時に、その部分列がPの倍数であるかを示せという問題。
倍数となる区間の数え上げなのでこれに落とし込みたくなるが、区間和ではなく10進表記なので少し戸惑った。

数列Aを逆順にして累積10進数(？？？) $S$ を取ることにして、
$S_{i+1} = S_i + A_i \times 10^i \pmod P$ としてやる

するとiからjまでの区間10進数(？？？)は
$\frac {S_{j} - S_{i}} {10^{j-i}}$ となる。
例えば12345から23を取り出す時は、 $2345 - 45 = 2300$ として、 $2300 / 100 = 23$ とする。

ここで $\frac {S_{j} - S_{i}} {10^{j-i}} \equiv 0 \pmod P$ となるのは ${S_{j} - S_{i}} \equiv 0 \pmod P$ の時のみである。
分子が0になる時以外に、割り算が0になったら怖いだろ。

で、後はこの区間10進数がmod Pで0になる区間を求めるだけ......ではないんだな恐ろしいことに。

$\frac {S_{j} - S_{i}} {10^{j-i}} \equiv 0 \pmod P$ をグッと睨むと、合同式の中で割り算していることがわかる。
合同式の項を割り算する時は、分母とPが互いに素でなければならないが、2と5は10と互いに素ではない。
よってこれら2つだけ場合分けする必要がある。

この処理自体は簡単で、1番下の桁が2(または5)の倍数なら左端は選び放題ということを踏まえて適当にやればいい。

文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます