競技プログラミングを趣味にしよう

この記事はtraP Advent Calendar 2016の22日目の記事です。ドカベントカレンダー

こんにちは。nariです。競技プログラミングではrickythetaと名乗っていたりします。

今年も去年同様、競技プログラミングに関する記事を書きます。traPは競技プログラミングサークルですからね[要出典]。

対象読者

先に読者の厳選をしておきます。この記事は競技プログラミングを始めたはいいものの、なかなか実力が上がってこないという人を対象としています。

競技プログラミングを始めようとしている人は、他の競技プログラミング入門系の記事を読んでから来ることをおすすめします。

蛇足ですが、最近ではAtCoder社が初心者向けコンテンツを開発中らしいです。期待が高まります。

AtCoderのプログラミング入門教材 AtCoder Programming Guide for Beginners の宣伝 - ブログのとさか

競技プログラミングとは

競技プログラミングは、プログラミングで競技をすることです。一般に「競技プログラミング」といえば数時間のコンテストを指すことが多く、数問の問題に対して適切なプログラム(ちゃんと解答を時間内に出力するプログラム)を提出することで得点を得るという形式になっています。

ところで、今年の8月頃についにwikipediaに「競技プログラミング」の項が出来たらしいです。めでたい。そちらも見てください。

競技プログラミング - Wikipedia

競技プログラミングを極めていこう

競技プログラミングはたくさんのコンテストが開かれています。

参加して上位に入賞すると、レート上昇の他に、次のようなものや機会がもらえることがあります。

• オンサイトコンテスト参加権
• Tシャツ
• お金

オンサイトコンテスト参加権については、オンラインコンテストで予選を勝ち抜き、本戦に出場できるという流れがほとんどです。オンサイトコンテストでは企業が?や?が振る舞われることがマナーとされているため、その恩恵を存分に浴びることが出来ます。

Tシャツは海外コンテストによくある賞品で、Google Code JamやHackerRank等で上位入賞すると郵送でTシャツがもらえます。他にもオンサイトコンテストに参加するとTシャツが配られることもあります。強さをアピールできるアイテムです。

お金はオンサイトコンテストの本戦で上位入賞したり、海外オンラインコンテストで上位入賞したりするともらえます。ここまで来るともはやガチプロですね。お金欲しい。最近はHackerRankのcodesprintが世界で上位100位以内に入ると75$相当のbitcoinがもらえるなど、チャンスは増えてきています。

どれも素晴らしいですね。最高。アドしか感じない。企業に圧倒的感謝。任意の方向に足を向けて寝られないので足を天に向けて寝るレベル。

つまり競技プログラミングで強くなればなるほど、?やTシャツや?がもらえるようになるということで、これは極めるしかありません。しかも極めるとプログラミング力やアルゴリズム力、考察力に問題解決能力も上がって、完全に一石八億鳥です。

こうなったら極めるしかありません。

入門したはいいけど実力が上がらない

めっちゃ分かる

分かるなぁ

というわけで、どうやって実力を上げるべきか、ここでは話していこうと思います。

個人的な持論として、競技プログラミングは大学受験数学と非常に酷似していると思っているので、大学受験数学の例を適度に出しています。大学生以上の方は受験期にどうやって数学を学んだかを思い出しながら、大学生未満の方はなんというか想像で補ってもらいながら、読んでいただけると良いかと思います。

とりあえずコンテストにばんばん参加する

コンテストにとにかく参加しましょう(体調は崩さない程度に)。

コンテストは他の人と競争するというモチベーションがある上、時間制限やペナルティがあるため緊張感もあり、学習効率としては最高だと思います。

またコンテスト終了後には解説が見れるようになる、もしくはプロ各位が解法をしゃべってくれるので、すぐに復習ができます。問題を解いて一定時間後にすぐ復習・確認ができるので良い学習習慣を築くことができます。

おすすめは日本一のコンテストシステムのAtCoder、世界一とも言えるTopCoder、コミュニティの大きいCodeForces、日本語でユニークな問題が出題されるyukicoder、コンテストの種類が多く頻度の高いHackerRank、などなどです。

過去問をガンガン解く

とにかく問題を解きましょう。競プロは実装速度も大事ですし、見たことある問題というものが多ければ多いほど実際に初めて見た問題に対する考察における武器が増えます。

とにかく解きましょう。AtCoder Beginner Contestの過去問はA~Dまで全部埋めましょう。またAizu Online Judgeにも日本語で大量の問題が所蔵されてるのでこちらもおすすめです。

時間をかけても問題が解けなかったら素直に解説を読もう

これは初期の内は即座にこうするべきです。しばらくして力が付いてきたと思ったら解説を我慢して実践力・考察力を身につけるべきです。

競プロ初心者、入門したての人は「解答の書き方がまず分かってない」状態になります。これは例えば大学受験数学で言えば「どのように理論を展開していいのかすら分からない」ということで、これでは得点するのは難しいでしょう。

解説では理論の展開の仕方(解法)が書いてあるので、それを真似して書くことで学んでいくのが近道です。

最近ではコンテストが頻繁に行われるようになっているので、「過去問を解説読んで解きすぎて、見たこと無い問題がなくなってしまった！実戦で考察力を鍛える練習ができない！」ということはまず無いでしょう。問題は無尽蔵に湧いてきます。というか全ての問題を解ききったらその時はすでに上位に入っていると思いますが

解説を読んで学んでも未遭遇の問題に対処できないと思うかもしれませんが、それは受験数学も大体同じで、似たような理論の展開を組み合わせて、その場その場でつなぎ合わせることでACを取ることができる問題が多いです。とにかく問題を解く方法を身につけるのが大事です。

でも他人のコードのコピペはダメです。ちゃんと自分で咀嚼して書きましょう(写経と言ったりします)。

ACしても解説を読もう

自分のACした解法と問題writerの想定解は実は違ったりします。受験数学でもそうですが、複数の解法を知っておくのは強みになります。

ACした解法とwriterの想定解が一致していた時は**ﾄﾞﾔｧ……**という気分に浸ると最高です。難しい問題ほどなんかその達成感がある。褒めてほしい。

Twitterをやろう

は？と思われますが、プロの競プロ勢は大体Twitterをしているので、コンテスト終了後にTwitterでは解法の議論や質問が飛び交います。

Twitterの活用方法としてはかなり良いと思うので、Twitterをやっていない人は是非Twitterを初めて情報収集に使いましょう。

まぁこの記事を見つけたということは大体Twitter経由だと思うのでその心配は無いと思いますが

蟻本を読もう

蟻本は競プロのバイブルとして名高いですが、あれは入門者だけではなく上級者にも役に立つテクニックが大量に載っています。

ある程度競プロに慣れてきてからもう一度読み返すと新たな発見があると思います。

データ構造を息をするように書けるようになろう

暗記しろとはいいませんが、データ構造は何も見ずに書けるぐらいにならないと本当に理解したとは言えないと個人的に思います。受験数学なら公式書き写しに当たりますから応用問題が解けないというのは大体わかるでしょう。

UnionFindとSegmentTree(RMQ)ぐらいは実装軽いですし頻出ですしいじる機会も多いので書けるようになりましょう。

平衡2分探索木は趣味(たまに平衡2分探索木で殴れる問題があるのでライブラリとして持っておくのは良いと思います) (受験数学なら高校範囲で習ってないようなチートテクみたいなポジションだと思ってます)(だがそこがいい)

他の人のブログを読もう

人によっては自身の解法の解説をブログに書いていたり、丁寧にテクニックについてまとめてくれていたりします。本当に感謝。

特に更新頻度が高いのはkmjpさんのブログとpekempeyさんのブログです。両者ともフォローしておくとかなりの知見が得られると思います。

kmjp's blog

pekempeyのブログ

ブログを書こう(アウトプットしよう)

競技プログラミングはその性質上、コードを書いては捨てて書いては捨ててを繰り返します。つまりこれでは長期記憶に残りづらく、解説を読んで書いたコードなんかはすぐに解法を忘れてしまいがちです。

そこで、ブログに自分の理解した解法を書き残しておくのが良いでしょう。特に解説と違う解法でACした場合などは他の人の参考になることもあるためぜひアウトプットしましょう。

• 参考URL : 競技プログラミングにおいて解いた問題の解説を書くことの利点について · うさぎ小屋

かくいう私はあまりブログを書かない方なのですが(sorry)、現在競プロer向けのブログツールを密かに作っていたりします。今後は積極的にブログを書いて競プロ界隈を盛り上げていきたいですね。ゲーム制作サークルなんだからゲーム作れよという突っ込みは無しで

頻出テク

というわけで、結局「コンテストガンガン参加して過去問ガンガン解いて、ダメだったら解説読んで、めっちゃ勉強して交流もしよう」という感じです。

ただここで一つ重要な問題が残っていて、それは「解説が読めない」という場合です。

日本語で書いてある部分はまぁなんとなく分かるのですが、「これはsegment treeを使うことでO(logN)を達成できます」とか、「スライド最小値を用いることで全体O(N)に落ちる」「尺取法でO(N)」「分割はこうで、統治はこうすると、分割統治でO(NlogN)」とか、なんか唐突に計算量が出てくるけど何してるかわからんということが多々あります。

まぁググれば終わりなんですけど、某友人に「そういうテクのリンクをまとめたページがほしい」と言われたので、ここではそれらをまとめて紹介します。コメントかTwitterでこれが足りないとか言ってくれれば追記します。

二分探索

アルゴリズムといえばこれだね、という感じですね。連続した範囲の内、どこかで1つだけ切れ目がある場合に、その切れ目を探すアルゴリズムです。二分探索は閉区間で持つ流派( $a\le x\le b$ )と半開区間で持つ流派( $a\le x<b$ )がありますが、基本的に半開区間の方が扱いやすいことが多いです。使うときには、切れ目がどういう条件、どっち側に含まれるか、というのをしっかり意識して書きます。

区間が半分半分になり、反復回数を $d$ 、最初の区間の長さを $n$ とすれば区間は $n\times 2^{-d}$ になっているため、区間の長さが1になるのは $d={\log }_{2}n$ となります。よって計算量は $O({\log }_{2}n)$ です。

• 分かり易いページ : 二分法（二分探索） - sataniC++

また、解が実数となるような場合の二分探索(二分法とも)では、区間の長さが $n\times 2^{-d}$ となるため、最終的な誤差もその程度で抑えられることになります。そのため、反復回数 $d$ を十分大きい値にしておけば十分小さい誤差の解が得られます。大体100回ぐらいやっておけば安心です。 $n$ の値にも影響されることに気をつけましょう。

• 参考ツイート(かわいい)

【アルゴリズム雑談】
答えが小数になる二分探索の問題についてですよ！
難易度：★★★☆☆ pic.twitter.com/pxQCvXufgl
— 古寺いろは@競プロ応援アカウント (@codera_iroha) 2016年5月9日

二分探索はかなり応用の広いアルゴリズムで、競プロにおいて何かを求めよという問題であった場合はとりあえず選択肢として「解を二分探索する」というのを疑うことは忘れないようにすべきです。

三分探索

二分探索が切れ目を探すのに対して、三分探索では区間の範囲の取る値が凸関数である場合に最大値もしくは最小値を探すというアルゴリズムです。区間を三分割して、その境目の値2つを比較すると、凸関数の性質からどちらに最大値/最小値が入っているかがわかります。これを繰り返します。

区間は1回の反復で $\frac{2}{3}$ 倍になるので、 ${\log }_{\frac{3}{2}}n=\frac{{\log }_{2}n}{{\log }_2\frac{3}{2}}$ 回の反復で区間の長さが1になります。よって定数倍を無視すれば計算量は $O({\log }_{2}n)$ です。

• 分かり易いページ : 三分探索と黄金分割探索 - naoya_t@hatenablog

なおこのページにて紹介されていますが、同様の手法に黄金分割探索があります。これは定数倍が軽いだけで計算量は $O({\log }_{2}n)$ です。制限時間が厳しい場合はこちらも視野に入れましょう。

三分探索は解が凸関数であるという保証が無いと使えません。「凸っぽいしとりあえず三分探索」というのは大体の場合嘘解法となることがあるのでちゃんと証明するようにしましょう。嘘解法で通せる人もいますがその話は別です。

繰り返し二乗法

繰り返し二乗法は、累乗の値 $a^x$ を計算する際に使えるアルゴリズムです。アルゴリズムと言ってもやってることは単純で、 $a^0=1$ $a^{2x}=(a^x{)}^2$ $a^{2x+1}=(a^x{)}^2\times a$ というようにするだけです。これは指数の値が毎回半分になっていくので、二分探索同様の計算量 $O({\log }_{2}x)$ で計算が可能です。

• 例題 : B: n^p mod m - AtCoder Typical Contest 002 | AtCoder

貪欲法

一番いい選択肢を取り続けると最適解になるという保証がある場合は、そのようにすべき、というのが貪欲法です。貪欲法は証明するのが大変ですが、貪欲法と分かっているなら一番いい選択肢を探すだけの問題になります。もし貪欲法以外の解法が思いつかず、貪欲法でサンプルも通って反例も見つかりそうにないなら、とりあえず貪欲法で提出してみるというのもありです。

• 参考ページ : 最強最速アルゴリズマー養成講座：そのアルゴリズム、貪欲につき――貪欲法のススメ (1/3) - ITmedia エンタープライズ

• 参考ツイート

ぱっと思いつく嘘かもしれない貪欲を吟味する時は, たいてい "最初の一歩を貪欲で選んだことで後で後悔しないか" か, "この貪欲をするとこういう解しか出来ないけれど, 最適解としてこういう極端なのだけ候補にしてしまっていいのか" とかを考えて, 脳内で大体証明して納得する.
— みさわ (@Mi_Sawa) 2016年3月26日

深さ優先探索/幅優先探索

全ての選択肢の組み合わせを試していくのが全探索と呼ばれるもので、そのうち選択肢を取る順番によって深さ優先探索と幅優先探索の2種類があります。

深さ優先探索は1つの可能性をどんどん掘り下げていき、終点に辿り着いたら分岐地点まで戻って別の可能性を見つけたらそこも掘り下げる、という感じのアルゴリズムで、再帰関数を書くことで実装できます。こちらは全ての可能性を探索するためのものとしては一番シンプルなものとなっています。

対して幅優先探索はすべての可能性を平等に推し進めていきます。A,B,Cという選択肢がある探索では、A、B、C、A→A、A→B、A→C、B→A、B→B、B→C、C→A、C→B、C→C、A→A→A、A→A→B、……というように最初は1回選択肢を選んだ可能性を、次は2回選択肢を選んだ可能性を、と順々に探索の深さを掘り下げていきます。幅優先探索はキューを用いることで実装が出来ます。幅優先探索では一番最初に条件をみたすような終点にたどり着いた場合に、その選択肢の選び方が一番少ない選択肢で終点にたどり着けるものだという保証があります(選択肢の少ない順に試しているため)。なので、最短経路問題等に使うことがあります。

深さ優先探索はDepth First SearchなのでDFS、幅優先探索はBreadth First SearchなのでBFS、とそれぞれ略されることもあります。

• 分かり易いページ : 深さ優先探索と幅優先探索 | 高校数学の美しい物語

• 分かり易いページ : 通勤・通学中に理解する深さ優先探索と幅優先探索【アルゴリズム】 - ottatiのブログ

• 分かり易いページと例題 : A: 深さ優先探索 - AtCoder Typical Contest 001 | AtCoder

• 分かり易いページと例題 : A: 幅優先探索 - AtCoder Typical Contest 002 | AtCoder

動的計画法(DP)

動的計画法とは、競プロerの前に立ちはだかる壁です。基本的な考えについては、ある「状態」の値を計算するために他の「状態」の値を利用し、計算をしたら値を保存しておく、という感じです。大事なのは、ある「状態」に対しての計算結果は変わらないということ、「状態」をうまく持つことで計算時間を減らすことです。

僕がここで変な説明をして誤解を招いても困るので、プロの説明を読んで下さい。

• プロの説明 : 動的計画法（ナップサック問題） - アルゴリズム講習会

• プロのスライド : プログラミングコンテストでの動的計画法

• プロの説明 : 動的計画法入門（数え上げ） - pekempeyのブログ

また、グラフ理論についての知識があるならば、動的計画法の本質はDAG(Directed Acyclic Graph)であるという説明もあります。こちらのイメージも持っておくとかなり発展させやすくなると思います。

• 参考ページ : DPの話 - aizuzia

• 例題 : C: 経路 - AtCoder Beginner Contest 034 | AtCoder の100点解法(W<=1000, H<=1000)

• 例題 : D: 経路 - AtCoder Beginner Contest 037 | AtCoder

• 難問の例 : 【No.027】「AOJ 0537 Bingo」 - dohatsutsu’s diary

さらに、動的計画法はあくまで概念で、応用が大量にあります。

bitDPとは状態として数の集合をもたせます。数の集合を持つには、含まれているかいないかの2通りの値(0 or 1)として表現すれば良いため、集合の要素数を $n$ とすれば $2^n$ 未満の2進数で表すことが可能となります。 $n\le 20$ 程度の問題サイズであれば、bitDPを疑うことがあります。

• 参考スライド : プログラミングコンテストでの動的計画法 (47ページ目から)

桁DPとは条件をみたすような数字(と言っても長さが10進数で表して10万だったりする)を数えると言った問題で使います。現在何桁目まで処理していて、どういった状態なのか、というのを持って処理を進めていきます。

• 分かり易いページ : 桁DP入門 - pekempeyのブログ

行列累乗とは、DPが状態に対する線形変換である場合に用いることが出来るテクニックで、例えばフィボナッチ数列の第5000兆番目の数字を求めたいと言った場合に、5000兆回も足し算を行うのではなく、線形変換であるために行列の掛け算で表せることを利用して、行列の累乗を繰り返し二乗法で求めることで高速に計算できるというものです。

• 参考ページ : 動的計画法でフィボナッチ数列の計算を速くする。 - from scratch

動的計画法はプログラミングコンテストにおいても頻出で、コンテストの全ての問題が動的計画法だった、ということも無くはないぐらいには頻出です。とにかくいろんな問題を解いて、どういう状態を持たせれば良いのかということを意識できるようになるといいでしょう。

メモ化再帰

メモ化再帰は動的計画法を実装する1つの手段です。メモ化再帰では、「ある状態についてすでに計算済みでメモってあるならそれを返す」「そうでないなら計算してメモって返す」というような再帰関数を書くことで動的計画法を実装します。

メモ化再帰の特徴は、ある状態がどの状態の計算結果を利用するのか、という依存関係の順番を気にしなくて済むということ、必要な状態の値のみ計算されるということです。

• 例題(やや難) : A: 通勤 - 第2回 ドワンゴからの挑戦状 本選(オープンコンテスト) | AtCoder

分割統治法

分割統治法とは問題を分割してその結果を利用するアルゴリズムの総称で、動的計画法も分割統治法に含まれます。

しかし特に「分割統治法」と書いた場合は、問題をうまく分解して、その小問題を解き、その結果を合成する、という操作を組み立てる必要がある難しい問題のことを指します。大体のパターンは問題サイズを半分以下にすることで、分割の回数が $O({\log }_{2}n)$ になるという良い性質を利用することが多いです。

例題としては2次元平面上の最近点対問題を点の数 $n$ に対して $O(n{\log }_{2}n)$ で求めるというものがあります。

• 参考ページ : 最近点対問題について語ってみる - Topics Related to Computers and NLP
• 例題 : 最近点対 | 計算幾何学 | Aizu Online Judge

最近では木を分割して解くというパターンが難問で良く見かけます。木の場合は重心という点があり、その点を基準に部分木に分解するとサイズが半分以下になるため、分割統治法を用いることが出来ます。

• 例題(難しい) : D: 道路網 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder

座標圧縮

値の範囲は大きいけれども、実際使っている値の数は少なく、値の大小関係だけが大事だったりする場合には、その値の代わりに小さい値を使うことで問題が解けるようになることがあります。この時に使うテクニックが座標圧縮です。小さい値から0,1,2,...と値を新しく付け直せば良いので、std::setとstd::mapが使えれば簡単に実装できます。座圧と略されることがあります(ググっても出てこないので勘弁してほしいと最初は思いました)。

• 例題 : C: 座圧 - AtCoder Beginner Contest 036 | AtCoder

• 例題(ちょっとむずかしい) : 魚の生息範囲 | Aizu Online Judge

尺取法

区間和などを求める際に、必要な区間の左端と右端が必ず進む場合には、ある区間と次に求めたい区間との間の差分が小さいことを利用して、全体で区間の長さに対する線形オーダー $O(n)$ を達成できます。

• 参考リンク : 尺取法についてのあれこれ - kira924ageの雑記帳

スライド最小値

尺取法と同じで、区間に対する最小値等を、必要な区間の左端と右端が必ず進む場合に差分が小さいことを利用して、全体で区間の長さに対する線形オーダー $O(n)$ を達成できます。

• 参考リンク : スライド最小値 - Algoogle

ダブリング

各ノードに対して、 $2^k(0\le k)$ だけ先の情報を予め持っておくことで、各クエリ $O({\log }_{2}n)$ を達成できます。これは数列やグラフに応用されます。特にグラフにおいてはLCA(Lowest Common Ancestor)を求める際に使うことができます。

• 参考リンク : AtCoder Beginner Contest 014 解説 (6ページ目から)

• 例題 : E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder

Segment Tree

ある2つの区間の計算結果を簡単にマージ出来る場合に、任意の区間に対して各クエリ $O({\log }_{2}n)$ で計算結果を手に入れることのできるデータ構造です。応用範囲が非常に広く、基本的に単純なRange Min Queryオンリーの問題はあまり出ません。

持たせるデータを工夫させたり、マージの仕方に癖のある問題など、動的計画法と並んでジャンルの広いものです。

• 分かり易いスライド : プログラミングコンテストでのデータ構造 (33ページ目から)

• 難しい応用問題と説明 : 初心者の初心者による初心者のための典型segment tree - DEGwerの競技プログラミングと時々数学

また、Segment Treeで値を2つ同時に持つようにすると、区間に値を足して区間の最小値を求めるということもできるようになります。StarrySky Treeと呼ばれることもあるそうです。

• 参考リンク : Introduction to Segment Tree - Lilliput Steps

さらに、値の範囲が大きい場合などでは、必要な場所だけ作るSegment Treeといったものが必要になることもあります。(これは座標圧縮でも対応できることが多いです)

• 参考リンク : JOI春合宿 2011-day4 apples - Lilliput Steps

Fenwick Tree(Binary Indexed Tree)

Segment Treeの下位互換ですが、構造が単純で実装も簡単で、何より定数倍速いのでたまに使います。良く使うのは転倒数を数えるときとかですね。計算量は変わらず $O({\log }_{2}n)$ です。

• 参考pdf : 20140319_bit.pdf

• 例題 : バブルソート | アルゴリズムとデータ構造 | Aizu Online Judge (想定は普通にバブルソートするだけですが、 $O(n{\log }_{2}n)$ でも解けます)

平方分割

ある数 $n$ に対して、数 $B$ を使って、計算量 $O(nB+\frac{n}{B})$ で書けるアルゴリズムで、 $B=\sqrt{n}$ とした時に計算量が $O(n\sqrt{n})$ となるアルゴリズムを平方分割と呼びます。実際には $B$ の値はプログラムで固定値にすることが多いです。

平方分割は考え方がかなりユニークですが、使えるようになるとかなり応用範囲の広い武器と成り得ます。

• 参考スライド : プログラミングコンテストでのデータ構造 (19ページ目から、数字列に対する平方分割)
• 参考ページ : AOJ 2667 Tree (クエリ平方分割解法） - くじらにっき++ (クエリに対する平方分割)
• 参考ページ : Mo's algorithm - pekempeyのブログ (平方分割の応用アルゴリズム)

遅延評価

SegmentTreeや一般的な木上で巨大な変更クエリを飛ばす際に、必要になるまで評価しない、という戦略を取ることで計算量が落ちることもあります。SegmentTreeでは、範囲に対する変更クエリを $O({\log }_{2}n)$ の範囲に分割してその範囲に遅延評価マークを付けて起きます。実際に評価されるのは他のクエリがその範囲を使おうとした際で、そのときはその下のノード(SegmentTreeなので半分にした区間)に遅延評価を伝播させます。

• 参考ページ : 僕のセグメントツリーの使い方 - kyuridenamidaのチラ裏
• 参考ページ : Lazy Propagation Segment Tree

データ構造をマージする一般的なテク

略してマージテクと呼ばれたりします。2つのデータ構造をマージしたい場合に、小さいやつを大きいやつに移す、という風にするだけで各マージのならし計算量 $O({\log }_{2}n)$ を達成できるという、最初に見ると少し不思議なテクニックです。あるアイテムについて考えると、移動する度に所属チームのサイズが倍々になるので、各アイテムの移動回数はたかだか $O({\log }_{2}n)$ 回ということに基づいています。

• 参考リンク : "データ構造をマージする一般的なテク" とは？ - (iwi) ｛ 反省します - TopCoder部

Heavy-Light Decomposition

HL分解とか重軽分解とか言います。これもマージテクと考え方は同じです。根付き木のあるノードについて、部分木のサイズが一番大きい子への辺をHeavy Edge、そうでない辺をLight Edgeと区別して、Heavy Edgeによって連結となったノードをひとまとめにしておくのがHeavy Light Decompositionです。こうすると、これもやはり各ノードから根までのパスについてLight Edgeを使って登る度に部分木のサイズが倍以上に増えるのでLight Edgeを使う回数が $O({\log }_{2}n)$ で抑えられます。よって、各ノードから根まで登るのに $O({\log }_{2}n)$ の計算量で済むため、LCAを求めたり、木上の任意の2点間のクエリに用いたりすることができます。

• 参考リンク : Heavy-Light Decomposition - math314のブログ
• 参考リンク : HL分解 (Heavy-Light Decomposition) - pekempeyのブログ

余談ですが、最近HL分解っぽいマージテク(？)のようなアルゴリズムが話題となっていましたのでこちらも紹介します。理解するとよりHL分解が使いこなせるようになるかもしれません。

• 参考リンク : やぶについて書きます

さらに横道にそれますが、「やぶ」とは大岡山に存在する定食屋で、東工大生に愛されている場所です。メニューがめちゃくちゃ豊富でしかも大体どれを選んでも当たり(むしろハズレを見たことがない)という神のような定食屋です。オーダーから出てくるまでに時間がかかりますが友人と来れば談笑で時間は気になりません。夜になるとコーヒーのサービスもあり最高なので大岡山に立ち寄った際には皆さんぜひ行きましょう。

ローリングハッシュ

私が結構好きなデータ構造/アルゴリズムです。

文字列に対して、先頭からの部分文字列に対するハッシュ値を計算しておくと、任意の部分文字列のハッシュ値を $O(1)$ で計算できるようにするというものをローリングハッシュといいます。ハッシュ値というのは、同じ文字列に対しては同じハッシュ値を返し、同じハッシュ値を持つ違う文字列を意図的に作ることが難しいという性質を持ったハッシュ関数によって計算された値のことで、これを使うと、任意の部分文字列同士の比較が $O(1)$ で行えるようになり、これを利用して文字列の大小を $O({\log }_{2}n)$ で、さらにこれを用いて各suffixの比較をしてソートをすることで $O(n({\log }_{2}n{)}^2)$ でsuffix arrayを構成することができます。

• 参考リンク : ローリングハッシュ - odan’s diary

Suffix Array

ある文字列に対して、i文字目から末尾までの部分文字列をソートし、そのiの値を並べた配列のことをSuffix Array(接尾辞配列)といいます。この構成については蟻本に載っている $O(n({\log }_{2}n{)}^2)$ のものから、前述の通りローリングハッシュを用いた方法、さらに文字列の性質を利用したSA-ISとよばれる $O(n)$ による高速な構成方法もあります。

• 参考リンク : 接尾辞配列 - Wikipedia
• 参考リンク : SA-IS - Shogo Computing Laboratory

その他文字列に関するアルゴリズム

その他、文字列に対してはかなり多種多様な効率的なアルゴリズムが存在します。ここではまとめて紹介します。

• KMP法(単一パターン文字列検索) : 文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• Manacher Algorithm(最長回文) : 文字列の頭良い感じの線形アルゴリズムたち２ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• Z Algorithm(最長共通接頭辞) : 文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• Aho Corasick法(複数パターン文字列検索) : Aho-Corasick法 - Algoogle
• Trie木(文字列管理構造) : 説明は↑に一緒に載ってます 例題は C: たんごたくさん - 天下一プログラマーコンテスト2016本戦（オープンコンテスト） | AtCoder

個人的に最近Z Algorithmを難問で良く見るのでとりあえず文字列にはSAとZ Algorithmを疑うようにしています。ローリングハッシュは基本的に定数倍が重いので……(哀しい)

フェルマーの小定理

競技プログラミングでは1,000,000,007で割った余りを出力せよ、という形式が非常に多いですが、これは組合せ爆発によって64bit整数ではとても表しきれない値になるような数え上げ問題が多々あるからです。

1,000,000,007(十億七)は素数なので、良い性質があります。その一つがフェルマーの小定理で、簡単に言うと $p$ を素数として $a^{-1}\equiv a^{p-2}(modp)$ というものです。つまり剰余のもとでの逆元で、割り算が出来るようになります。

例を見るのが早いでしょう。 $p=1,000,000,007$ に対して、 $a=2$ としましょう。すると $a^{-1}\equiv a^{p-2}\equiv 500,000,004(modp)$ となります。
さてここで8を $a$ で無性に割りたくなったとします。もちろん8は偶数なので割り切れるというのはわかりますが、もしかしたら割り切れなくて小数になってしまって困ってしまうかもしれない。
そんな時、 $a^{-1}\equiv 500,000,004$ を使うことで、 $\frac{8}{a}\equiv 8a^{-1}\equiv 8\times 500,000,004\equiv 4,000,000,032\equiv 4(modp)$ となります。割ることが出来ました。これで安心ですね。

というようなものになります。なお十億五乗するには繰り返し二乗法を用いることが出来ます。

• 参考リンク : フェルマーの小定理 - Wikipedia

その他

他にもたくさんのアルゴリズムやテクニックがありますが、ここでは紹介しきれません。というか筆者が把握しきれていない。
個人的に最近使ったやつだと「約数の数の最大値は意外と小さい」ということですかね、これは高度合成数とかでググると出てきます。
大量にあるので、アルゴリズム等をまとめているページを最後に紹介しておきます。

• Spaghetti Source - 各種アルゴリズムの C++ による実装
• Algoogle
• libalgo

終わりに

これにてこの記事は終了です。お読み頂きありがとうございました。

私が競技プログラミングに初めて触ったのは高校の頃(4年前ぐらい？)で、その頃AtCoderは毎週ではなく不定期開催でした。私はJavaScriptの腕を磨きたい！という目的でAtCoderをやっていたのですが、当時アルゴリズムのアの字も知らなかったため当然実力は上がりませんでした。

時が流れて昨年度に大学に入り、traPでICPCに出ようとなってからC++を触っての本格的な競技プログラミング生活が始まりました。アルゴリズムのアの字も知らなかったので蟻本を買ってとにかく読んだりAtCoderに出たりTopCoderやCodeForcesに手を出してみたりしました。とにかく問題を解きまくりました。CodeForcesが毎回深夜1時35分からスタートだったので風邪を引いて耳が聞こえなくなったり目をヤバイ感じに充血させた時もありました。目に横一閃の赤い筋が入っててついに能力に覚醒したのかと勘違いしました。一週間安静にしたら治った。

そうこうして現在に至るのですが、今ではTopCoderでイエローコーダーにまでなりました。本当に有耶無耶なので競プロ上達のコツが何だったのか自分でも分からないのですが、やはりひたすら問題を解くと良いんじゃないかな、と思ってこの記事を書きました。さすがに目が充血するまではやりすぎだと思います。ちなみに単位は落としていません。慈悲で60点貰った科目はあります。

競技プログラミングはとにかく時間を奪っていきます。ひたすら時間が消えていくので、人におすすめするのに少し躊躇いがありますが、とにかく問題を解く快感を知っている人にとっては楽しいです。大学受験数学が大好きだった人には分かってもらいたいこの気持ち。

ぜひ競技プログラミングを極めて、最高の人生を送ってください。

ところで明後日24日にはXmasコンテストがAtCoderのジャッジシステムで開催されます。ぜひ参加しましょう。チームで出てもOKとのことなので、友人を巻き込んで参加してみるのも楽しいかもしれません。リア充は帰って、どうぞ。

Xmas Contest 2016

明日のtraP Advent Calendarの担当はDavidさん、gotohさん、satorikuさんです。Davidさんは院生なので高度なことをしてくるかもしれませんし、gotohさんは去年ファミコン記事を書いてかなり好評だったことから期待されます。satorikuさんはUnityの記事ですね。Unityは最近traP内でも使っている人が増えており、自分も使ったことがあるので興味があります。どれも楽しみです。