はじめに
この記事は チームスピリットAdvent Calendar 2017 の15日目の記事です。
私自身、競技プログラミングは全く強くありませんし、この記事で紹介するのはほんの初歩です。
paiza のA ~ S問題で苦戦しているくらいの人に向けた記事です。
アルゴリズム力を測るサービス
ITプログラマ・エンジニア向け転職・就活・学習サービスのpaiza
アルゴリズムの難易度は低めだが、たまに実装量がエグい問題がある。AtCoder
アルゴリズムに落とし込むことを大事にしており、解法さえ分かれば実装量はそんなに多くない。しかし超難しい。LeetCode
問題が一部ユーザー投稿式になっており、一部の問題に関しては判定の段階で問題に全く記述されていない仕様のテストが行われたりする。
データ構造を工夫してメモリアクセス回数を削減する問題が多いような
この位早いアルゴリズムで書いてくれよ! と指定されていてもゴリ押し実装で判定が通ったりする謎。HackerRank
難しい。何が難しいって英語の問題を読むのが。(しかも冒頭の場面設定は問題と何ら関係ないことが多い)
Discussion を見ると大抵答えが書いてあるので勉強にはもってこい。(大抵「俺はこんなに短く書けたぜ!」というコードゴルフに発展します)
最初に覚えておきたいこと
計算リソースの限界
プログラミング全般に言えることですが、次の2つに気をつけておかねばなりません。
| 意味 | 許容範囲の目安 | |
|---|---|---|
| 計算量 | 演算を行う回数 | 1000万回程度 |
| 空間使用量 | 確保するメモリの領域 | 基本型で10万要素程度 |
上記で挙げた目安は、一般的なサービスの実行制約を参考にしたかなりざっくりとした目安です。
ですが、上記の数値を超えるリソースの利用が想定される場合は、判定に出す前にもっと良い解法を考えたほうがいいかもしれません。
オーダー記法
[初心者向け] プログラムの計算量を求める方法 - Qiita
アルゴリズムを比較する際は、定数倍に気を配る必要はあまりありません。
数倍の差であれば使用言語の違いによりどうしても生じてしまいます。つまり、言語選択の自由がある以上その差はジャッジの範囲内です。
気にしなければいけないのは「データが増加した時に、計算量はどの程度増加するか」の比較です。
問題によってはジャッジで10万件のデータが投入される場合があり、計算量がデータ数の2乗に比例すると、計算量は100億回を超え、これは確実にタイムアウトになります。
アルゴリズムの計算量増加を簡単に計算するためにオーダー記法が便利です。
| 操作例 | 計算量の増加 |
|---|---|
| 配列からインデックスで値取り出し | $O(1)$ |
| 連結リストからインデックスで値取り出し | $O(n)$ |
| 連想配列からキーで値取り出し | $O(\log n)$ |
| 配列を挿入ソート | $O(n\log n)$ |
整数型のビット長
この手の問題で定番なのが、数値のオーバーフローです。
入力される数値の条件が明記されているので、それを確認した上で変数の型を決定します。
| 型 | 10進数での桁数の目安 |
|---|---|
| int | 9桁 |
| long long | 18桁 |
大抵の言語ではでは int は4バイト、 long long は8バイトなので、それを元に計算すると正確な容量が分かります。
上記では低めに見積もって、確実に代入できる桁数を示しています。
答えが long long になる計算では、先にキャストすることを忘れないでください。
int a, b, c;
...
long long ans = a * b + c;
int a, b;
...
long long ans = (long long) a * b + c;
ちなみに私は入力が int 型の負数で、 int 型のまま符号をひっくり返すと 1 だけオーバーフローする問題に引っかかったことがあります。(負数の絶対値は正数の絶対値より大きい)
「はいプロ」
アルゴリズム
貪欲法
深さ優先探索 - Wikipedia
幅優先探索 - Wikipedia
非常にシンプルなアルゴリズムなので、文章を読むより例題を解いた方が早いです。
深さ優先探索は関数再帰を使うと簡単に実装できます。
二分探索 (Binary Search)
二分探索は数当てゲームの攻略法と非常によく似ています。予め探索する配列をソートしておくことで、探索する範囲を半分にしていきます。
配列のソートするコストは $O(n\log n)$ として、探索自体のコストは $O(\log n)$ なので、1つのデータセットに対して何度も探索を繰り返す問題では十分に割に合います。
最もメジャーでシンプルな探索法で、殆どの言語の処理系についてきます。
| 言語 | 関連する関数/メソッド |
|---|---|
| C++ | std::lower_bound |
| Ruby | Array#bsearch |
C++ の lower_bound と upper_bound は名前と挙動が非常に紛らわしいので注意。
大抵の言語では、連想配列の値をキーで取り出す場合に、ソート済みのキーと値のペアのリストを二分探索しています。
また、セットは要素を追加する時に挿入ソートし、重複チェックに二分探索を用いるという実装が多いです。
つまり、配列内の要素が重複しないことが分かっていれば、 Set を使うことでより直感的に二分探索を扱えます。
配列の実装と探索木の実装
競技プログラミングでは入力の総数が予め分かっておりクエリーが一度に入力されるので配列での実装で十分です。
RDBのインデックスなど実際のユースケースではもう少し奥は深いです。
組合せ爆発
動的計画法
上記の組合せ爆発に対抗する方法は「一度計算した答えを再利用すること」です。
n番目のフィボナッチ数列の要素の値を求める関数を考えてみます。
int fib(int n) {
if (n == 0 || n == 1) {
return n;
}
return fib(n - 2) + fib(n - 1);
}
int fib(int n) {
int memo[n] = {0, 1};
for (int i = 2; i <= n; ++i) {
memo[i] = memo[i - 2] + memo[i - 1];
}
return memo[n];
}
(ちなみにフィボナッチ数列は行列計算を用いることで $O(\log n)$ で計算する方法があります。)
このように動的計画法は状態をキー、計算結果を値として保存して再利用します。
フィボナッチ数列は n を状態とした非常に簡単な例でした。どの状態変数が同じ時、どの計算結果が再利用できるかを見極めることが競技プログラミングの基本になります。
ダイクストラ法
について書きたかったけどなんか背中が痛いのでこの辺で
オマケ
Q. 何のためにアルゴリズムを学ぶのか。
A. 「自分の頭で考えてこそ実力では?」と考えていた時期が私にもありました。しかしこれらのアルゴリズムを覚えたところで、解けない問題が解けるようになるということはあまりありません。閃いた時に簡単な実装で点を落とさないための、競技プログラミングでのデザインパターンだと私は思っています。
Q. アルゴリズム系のコーディングテストは実務に役に立つ?
A. 実務の内容次第としか言いようがないです。検索アルゴリズムの改善やDBのクエリチューニングなどアルゴリズム改善系の業務でないと役に立たないと思います。