この記事は、Competitive Programming Advent Calendar 2016 の7日目の記事です。 あなたは、一部の競プロ勢の間で使われている「セグ木で殴る」という言葉をご存知でしょうか? priority_queueを使えば良いところをセグ木で解いてみたり*1、累積和を使えば良いところをセグ木で解いてみたり*2するアレです。 この「セグ木で殴る」は、「考察すればもっとスマートに書けるがめんどくさいのでセグ木で解いた」といった意味であり、ややネガティブな言葉でもあります*3。 しかし競技プログラミングに限定すれば、バグさえ出さなければスマートに書く必要はありません。速さが正義です。 そこで本記事では、セグ木以外での「殴り方」をいくつか紹介したいと思います。 強連結成分分解で「殴る」 強連結成分分解は蟻本にも載っているアルゴリズムで、有向グラフ上の強連結成分を圧縮して
![色々なアルゴリズムで「殴る」 - あったこといろいろ](https://cdn-ak-scissors.b.st-hatena.com/image/square/862e672ee2d90529c8a6c4a321017ba3c11b80c4/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2FY%2FYazaten%2F20161207%2F20161207125512.png)