色々なアルゴリズムで「殴る」
この記事は、Competitive Programming Advent Calendar 2016 の7日目の記事です。
あなたは、一部の競プロ勢の間で使われている「セグ木で殴る」という言葉をご存知でしょうか？
priority_queueを使えば良いところをセグ木で解いてみたり*1、累積和を使えば良いところをセグ木で解いてみたり*2するアレです。
この「セグ木で殴る」は、「考察すればもっとスマートに書けるがめんどくさいのでセグ木で解いた」といった意味であり、ややネガティブな言葉でもあります*3。
しかし競技プログラミングに限定すれば、バグさえ出さなければスマートに書く必要はありません。速さが正義です。
そこで本記事では、セグ木以外での「殴り方」をいくつか紹介したいと思います。
強連結成分分解で「殴る」
強連結成分分解は蟻本にも載っているアルゴリズムで、有向グラフ上の強連結成分を圧縮してDAGにするアルゴリズムです(ざっくり)。
知名度はそれなりですが、使う機会はあまり多くありません*4。
早速殴っていきましょう。
今回、この強連結成分分解で殴られる問題はこちらです。（問題のネタバレを含みます)
abc030.contest.atcoder.jp
この問題を説く過程では、頂点をたどることによってたどり着く閉路に含まれる頂点数を求める処理が必要になる場面があります。
スマートに実装するならば「有向グラフを1頂点づつたどってゆき、usedの頂点とぶつかったときの深さ - usedの頂点の深さ が閉路の大きさ が答え」みたいな感じで求める方法が考えられます。
しかし、このアルゴリズムを考えるのが面倒だったり*5バグが怖いので書きたくないという気持ちになるかもしれません。
そこで、強連結成分分解で殴ってみることにしましょう。
強連結成分分解を適用する過程で、ある頂点を含む強連結成分の大きさ をO(1)で知ることができる配列を得ることができます。
そこで、「頂点をたどっていき今いる頂点を含む強連結成分の大きさを調べる。大きさが2以上であればそこが最終的にたどり着く閉路であり、その大きさは前述の配列を使って容易に求まる。」といった手順で目的の処理を実現することができます。
実際に強連結成分分解で解いたソースコードへのリンクを以下に貼っておきます。
Submission #961082 - AtCoder Beginner Contest 030 | AtCoder
二重辺連結成分分解で殴る
二重辺連結成分分解は蟻本には載っていませんが、僕の記事を初めいくつかの解説記事があります。無向グラフ上の二重辺連結成分を圧縮するアルゴリズムです(ざっくり)。知名度は強連結成分分解以上に低く、使う機会はかなり少ないです*6。
どんどん殴っていきましょう。
今回、この二重辺連結成分分解で殴られる問題はこちらです。（問題のネタバレを含みます)
utpc2014.contest.atcoder.jp
この問題を解く過程で、N頂点N辺の連結なグラフ*7の持つ閉路に含まれる頂点数を求める処理が必要になる場面があります。
スマートに実装するならば「根つき木にして深さを持ったDFSをし、usedの頂点にぶつかった時の深さ - usedの頂点の深さが閉路の大きさ が答え」みたいな感じで求める方法が考えられます。
しかしここでは二重辺連結成分分解で殴ってみることにしましょう。
二重辺連結成分分解を適用する過程で、各二重辺連結成分に含まれる頂点の数とその要素を得ることができます。
N頂点N辺の連結なグラフはちょうど1つの閉路を持ち、閉路は二重辺連結成分の一種です。
そのため、「頂点数 = 辺数 かつ 連結な有向グラフ」に１つだけ含まれる閉路のサイズを容易に知ることができます。
実際に二重辺連結成分分解で解いたソースコードへのリンクを以下に貼っておきます。
Submission #1015041 - 東京大学プログラミングコンテスト2014 | AtCoder
「殴る」ことによるメリット・デメリット
メリット
- ライブラリを貼るだけで良いので実装量が減る
- Twitterで「C問題は◯◯で殴った」とか言える
デメリット
- 可読性が低くなる
- ソースコード長が無駄に長くなる(冗長な部分が増える)
- 計算量が増加する場合がある
まとめ
非競技プログラミングでこういうことをすると微妙な顔をされてしまう可能性があります。用法用量を守って正しくご使用下さい。
明日、8日目の記事はskyaozoraさんの「競プロを初めて10年になるので振り返ります」とyosupotさんの記事（内緒と書いてあった…）です。
