この記事は、traP Advent Calendar 2015 - Adventarの3日目です。
筆者は Twitter:@_n_ari です。軽い自己紹介をすると、競プロとごちうさが大好きです。
アイキャッチはTreap(データ構造)の実装の一部です。エディタはSublime Text。
参考：プログラミングコンテストでのデータ構造 2　～平衡二分探索木編～

競プロのめっちゃ初歩的思考法

響きが良いと思ったら五七五だった。和を感じる。
参考：川柳 - Wikipedia
参考：#csenryu - Twitter検索

競プロとは

競技プログラミングの略。競技プログラミング Wiki*とか見ると分かると思う。
簡単に言うと、ある条件に沿った入力が与えられて、問題の解になるような出力をする、というのをプログラムするもの。
プログラミングのスキルを上げたり、アルゴリズムや数学の勉強になったり、何より楽しかったりする。世界的な大会もいっぱいあって、世界の強豪たちがしのぎを削っている。
コンテストの一例：AtCoder (アットコーダー) (数少ない国内日本語コンテスト)

競プロの本質

競プロは、だいたいは以下の様な順番に沿って行われる。
「問題を読む」→「考察を行う」→「実験する」→「プログラムを書く」→「デバッグ」→「提出」→「正解なら終了、不正解なら考察からやり直し」
この内一番時間がかかるのは、一般に「考察を行う」部分だと考える。早くプログラムを組み立てるスキルというのは一番重要とは思えない。

少し蛇足になるが、この流れはみんなお馴染みの「大学受験数学」に似ていると私は思う。
受験数学では「問題を読む」→「どういう公式を使えば解けるか考える」→「実際に数式を並べる」→「微修正」→「提出」であるが、この内「数式を並べる」ところが本質だと考える人は少ないと思われる。
基本的には、どんな公式や法則が使えて、どういう結果が得られるかを考えるのが受験数学であり、計算力は(必要な問題もあるが)そこまで要求されない。

つまり競プロでは問題を読み、素早く考察を行い、それにあったプログラムを書く、という競技になる。

バイブル

競プロには蟻本と呼ばれる競プロ勢のバイブルのような物がある。基本的にこれを読んで、すべてを理解した時には立派なプロ競プロerになっていることだろう。
参考：プログラミングコンテストチャレンジブック [第2版] | マイナビブックス

実はこれを読めばほとんどのことは解決してしまうのだが、今回はほぼすべての競プロに共通しそうな概念についてお話する。

競プロ三大兵器

競プロには三大兵器、三種の神器が存在する(今勝手に決めた)。それは以下の3つである。

• 数学
• 記憶
• 分割統治法

今回はこれらについてお話する。

1.数学

みんなだいすきすうがく。
数学と言っても、基本的には一般的な実数空間における数学ではなく離散的な数学である。
参考：離散数学 - Wikipedia

例えば高校数学でお馴染みの組み合わせの数である。
組み合わせの公式、nCk=n!/(n-k)!k!という公式や、パスカルの三角形といった性質を知っている我々なら組み合わせの数え上げなど造作も無いことではあるが、もし知らなかった場合、どのようにすれば良いだろうか？
考えられる方法としては、およそすべてのパターンを考え、条件を満たすパターンの数を数える、というのがある。当然面倒でしか無い上、組み合わせの式では一発で求まる値に、パターンを列挙し、チェックし、数え上げる、という処理が入っては、速度の求められる場所では使いものにならない。
このように数学的考察を重ねることで、無駄な演算を減らすことが可能となることが多々ある。
例：C: 擬二等辺三角形 - 天下一プログラマーコンテスト2015予選B | AtCoder という問題は、数学的考察を重ねることで、式一つで答えが求まるようになる。
この辺りは数学的知識が必要となる。日頃から数学へ関心を向けると良い。

2.記憶

例えば上にもあったとおり、組み合わせの数nCkという数を求めるにはn!/(n-k)!k!という式で求められる。しかしこの式は重要な欠点があり、階乗n!を求めるのにn個の自然数を掛け算しなければならない。
もし万が一nC1,nC2,nC3,...という値が必要になった時、n回の掛け算を何度もやる必要があるだろうか？
そんなことは無いはずである。計算するたびにn!の値は変わったりすることはない。ということで、n!の計算は一回行っておけば、あとはその値を使えば計算の重複がなくなる。
このように、何度も使う計算結果を記憶するということは、一見普通のことに見えるが大事なことである。「メモ化」と呼ぶことがある。
参考：メモ化 - Wikipedia

3.分割統治法

本命である。これは概念的なもので、「大きなサイズの問題を、いくつかの小さなサイズの問題に分割し、その結果を使い元の大きなサイズの問題の解を得る手法」を指す。
例えば、順序が不規則な数列のうち、最大の値を求めたい時、その数列を2つに「分割」して、2つの数列の最大値を求めて、そのうち大きい方が元の数列の最大値になる、という計算方法も立派な分割統治法である。
主によく使われるのは「二等分」と「平方分割」である。

「二等分」では、問題のサイズを半分にして行くというのを繰り返す計算方法である。ステップを踏むごとに二倍二倍と増えていくため、log_2(N)回のステップを踏むことで、サイズNの問題を、サイズ1の問題に帰着できる。
ところで唐突に数学の話になるが、対数関数logというのは非常に強力なもので、log_2(1073741824)=30であり、大きなNに対してもほぼ定数のような数を返す関数である。
よって、N回のステップが必要だった問題を、log_2(N)回のステップで十分なようにするのは非常に効果の大きい改善となる。
例えば、順序が不規則な数列を昇順に並べ替えるアルゴリズム(ソートアルゴリズム)には、数列を2つに分けてそれぞれを昇順に並び替えてから合成するマージソートと呼ばれるアルゴリズムや、ある値を定めてその値より大きい値と小さい値を集めて数列を2つに分けるという操作を繰り返すことで昇順に並び替えるクイックソートと呼ばれるアルゴリズムがある。
参考：マージソート - Wikipedia
参考：クイックソート - Wikipedia

「平方分割」とは、サイズNの問題を、√N個の、サイズ√Nの問題に分割する方法である。√N個のブロックの内どのブロックに解があるかを調べ、そのブロックの√N個の物のうちどれが解かを調べる、という感じに計算を行うようにすれば、2√N回調べるだけで良くなる。
これは二等分系に比べてマイナーであるが、競プロにおけるクエリ系問題と呼ばれるもので有効なテクニックだ。
参考：プログラミングコンテストでのデータ構造

今回伝えたいのは、分割に限らず、問題のサイズを小さくして元の問題を解決するという手法を用いることで、計算回数を大幅に削ることができるということだ。競プロで問題を考察する際にも、どのようにして問題のサイズを小さくできるか、という観点を持つことは大事である。

まとめ

以上が競プロ(個人的)三大兵器である。これらの概念を理解したうえで、AtCoderの解説や、蟻本を読むことで理解が進むと考えられる。
またこれらの三大兵器は独立したものではなく、融合することであらゆる兵器を生み出すことができる。

競プロでは頻出の動的計画法(Dynamic Programming, DP)とは、メモ化と分割統治法を用いた概念で、「重みと価値という値を持った物品のリストが与えられる。これらの物品のリストの内、重みの総和がW(定数)以下になるようにいくつか選び、価値の総和を最大化せよ。」といった問題(0-1ナップサック問題)を効率よく解くことができるようになる。
具体的には、それぞれの物品を選ぶか選ばないかを考えると2のN乗個の組み合わせになり、N=1000ほどになると0が30個続くような天文学的数字になり到底解けなくなるが、それをメモ化と分割統治法を用いることで(N×W)回程度の計算で済むようになる。
参考：動的計画法 - Wikipedia
参考：ナップサック問題 - Wikipedia

他にも、高速フーリエ変換(FFT)というのは、離散フーリエ変換を高速化したものであるが、その背景には、数学的考察、記憶、二等分といった概念が使われており、それらによって離散フーリエ変換の(Nの2乗)回の計算をFFTでは(N×log_2(N))回の計算で済むようにしている。
参考：高速フーリエ変換 - Wikipedia
FFTについては、サイトを眺めていてもどのような仕組みになっているのかがわかりづらいため、N=8ぐらいの離散フーリエ変換の式を手計算で展開し、どの値をメモ化で使いまわせるかというのを考えると理解しやすくなると思う(筆者の実体験による感想)。

おまけ

traPは最近、ICPC練習会の方々と交流し、競プロ勉強会を始めた。現時点では毎週木曜5時から第1演習室で行っていたりする。少しでも競プロに興味を持ってくれたのなら、ぜひ参加して欲しい。大人数でやると分からない問題について質問ができたりしていろいろ便利である。

おまけ(本編)

　2015年12月03日(木)の23時30分からTOKYO MXにて「ご注文はうさぎですか？」(1期)の9羽「青山スランプマウンテン」が再放送される。長々と競プロについて語ったが、そんなことよりごちうさを見たほうが良い。見よう。ぜひ見よう。
参考：第9話 青山スランプマウンテン｜ご注文はうさぎですか？｜アニメ｜TOKYO MX

追記(2015/12/03 14:51)

本日12月3日は「のんのんびより」より宮内れんげ殿のお誕生日でした。おめでとうございます。
参考：TVアニメ『のんのんびより りぴーと』公式サイト