新人ラッシュの煽りを受けて今週も新人エンジニアのspin13です．
毎週恒例の社内勉強会で競技プログラミング(一般的にプログラミングコンテストとも)について発表しました．
※ 競技プログラミングとプログラミングコンテストはどう違うの？ と思われるかもしれませんが，私も特に区別したことはほとんどないので本記事では同等のものとして扱います．
競技プログラミングとは
与えられた問題をどれだけ早く，正確に，多く解けるかを競う競技です(例外もあり) ．
プログラミングによる問題解決 ともよく言われます．
競技参加者は問題が公開されたら問題を読んで，与えられた入力に対する正しい答えを出力するプログラムを作成します．
プログラムが書けたらJudge Serverにsubmitし，ジャッジ結果を待っている間に次の問題を読むなり祈ったりします．
Judge Serverで与えられる入力に正解できると得点になります ("通る" とも言われます)． 正解できなかった場合はプログラムのデバッグを行ないます．
Judge Serverからの結果
Judge Serverから返される結果にはいくつか種類があり，その結果如何によってデバッグの参考にしたり．
・Accepted (AC) - 正解です．Judge Serverで与えられる入力に対して正しく答えられました． あくまで"用意された入力に対して期待された出力ができた" だけで完全に正しいということは保証されない． 入力データが甘い場合も稀にあります．
・Wrong Answer (WA) - 不正解． Judge Serverで与えられた入力に，期待された出力がされませんでした． プログラムを見なおして修正しましょう．
・Time Limit Exceeded (TLE) - 時間切れ． あなたが書いたプログラムは入力に対して制限時間以内に出力を返すことができませんでした． 競技プログラミングではほとんどの場合，問題に制限時間が設定され，その時間以内に答えを出力しなければならない．
・Memory Limit Exceeded (MLE) - メモリオーバー． あなたが書いてプログラムはメモリ食い過ぎです． 使用するメモリ量が少なくなるように修正しましょう． 但し，したからといってACするとは限りませんので注意してください．
・Runtime Error (RE) - 何かしらの特殊なエラーが起きている． ゼロ除算だったり一部言語のメイン関数で0を返してなかったりと多くの原因が考えられます．
・Compile Error (CE) - コンパイルエラー． そのままですね．コンテストサイトによっては自分の環境とコンパイラのバージョンが違っていることが原因になっていることもあります．
・Waiting Judge (WJ) - ジャッジを待っている状態． しばらく待ちましょう． WJって単語使ったことない・・・
他にも特殊な結果が返ってくるところもありますが大まかにはこれくらいです．
問題例1
【問題】
a, b が入力として与えられるので, aとbを掛けた結果を出力してください．
【制約】
時間制限: 1秒
1 ≦ a, b ≦ 10000
答えのコードは次のようになると思います．
C++
#include <iostream> using namespace std; int main(){ int a, b, ans; cin >> a >> b; ans = a * b; cout << ans << endl; return 0; }
$ ./a.out 4 8 32 $ ./a.out 10000 10000 100000000
Java
import java.util.Scanner; public class Main{ static final Scanner sc = new Scanner(System.in); public static void main(String[] args){ int a = sc.nextInt(), b = sc.nextInt(); int ans = a*b; System.out.println(ans); } }
$ java Main 9 3 27 $ java Main 10000 10000 100000000
JavaはJudge Server側でMain.javaとしてエンコードされる場合が多いのでクラス名はMainにしておくのが無難 (指定されている場合を除く)．
問題例2
【問題】
整数Nが与えられるので0~Nまでに含まれる素数の数を出力せよ．
問題元ネタ
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1172&lang=jp
【制約】
時間制限: 2秒
0 ≦ N ≦ 10^6
今回は素数を求める問題です．まずは愚直に書いてみましょう．
C++
#include <iostream> using namespace std; bool isPrime(int a){ if(a == 2) return true; for(int i=2;i<a;i++){ if(a%i == 0 ) return false; } return true; } int main(){ int N; int ans = 0; cin >> N; for(int i=2; i<=N;i++){ if(isPrime(i)) ans++; } cout << ans << endl; return 0; }
$ ./a.out 10 4 $ ./a.out 10000 1229
Java
import java.util.Scanner; public class Main { static final Scanner sc = new Scanner(System.in); public static void main(String[] args){ int N = sc.nextInt(); int ans = 0; for(int i=2;i<=N;i++){ if(isPrime(i)) ans++; } System.out.println(ans); } static boolean isPrime(int a){ if (a == 2) return true; for(int i=2;i<a;i++){ if(a%i == 0) return false; } return true; } }
$ java Main 10 4 $ java Main 100000 9592
「よしよし，正しく出力できてるな」 と提出する前に制約に書いてある最大値のNを与えてみましょう． 制約には何かしら意味があることが多いので制約について考える癖もつけておいたほうがいいです．
$ ./a.out 1000000 78498
すっげーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー 時間かかるけど答えはでます．
が，このままでは制約である2秒制限に引っかかってしまいます．計算量を減らすためにもっと高速なアルゴリズムを使う必要がありますね．
$ time ./a.out 1000000 78498 real 2m4.704s user 2m2.583s sys 0m0.230s
今回はエラトステネスの篩という素数アルゴリズムを使いたいと思います．詳細はスライドをご覧ください．
C++
#include <iostream> #include <math.h> using namespace std; int main(){ int N; cin >> N; int ans = 0; bool primes[N+1]; for(int i=2;i<=N;i++) primes[i] = true; for(int i=2;i<=sqrt(N);i++){ if(primes[i]){ for(int i2=i+i;i2<=N;i2+=i) primes[i2] = false; } } for(int i=2;i<=N;i++){ if(primes[i]) ans++; } cout << ans << endl; return 0; }
$ time ./a.out 1000000 78498 real 0m0.020s user 0m0.014s sys 0m0.003s
Java
import java.util.Scanner; public class PrimeSieve{ static final Scanner sc=new Scanner(System.in); public static void main(String[] args){ int N=sc.nextInt(); int ans=0; boolean[] primes=sieve(N); for(int i=2;i<primes.length;i++){ if(primes[i])ans++; } System.out.println(ans); } static boolean[] sieve(int n){ boolean[] primes=new boolean[n+1]; for(int i=2;i<=n;i++)primes[i]=true; for(int i=2;i<=Math.sqrt(n);i++){ if(primes[i]){ for(int i2=i+i;i2<=n;i2+=i)primes[i2]=false; } } return primes; } }
$ time java PrimesSieve 1000000 78498 real 0m0.132s user 0m0.123s sys 0m0.030s
問題の1000000もなんのその．
実はエラトステネスの篩のほうでも使ってますが、10^9であればsqrt(N)以下の数は調べないようにすれば愚直な方法でも2秒は間に合います．
bool isPrime(int a){ if(a == 2) return true; for(int i=2;i<=sqrt(a);i++){ if(a%i == 0 ) return false; } return true; }
合成数は素数の積で表せるので，合成数Mが素数aと素数bの積とするとM=abであるが，このaとbのうちどちらかはsqrt(M)以下でなければMを超えてしまうからである．
ある整数Nの約数には掛けるとNになるペアが存在し，そのちょうど中間地点が平方根であることが知られている．
素数を求めるアルゴリズムは他にもいっぱいあるので調べてみると面白いです．
終わりに
問題の種類も様々なものがあり，ストーリーがついてるものもあるので飽きません．
多くのコンテストサイトで過去問ができるようになっているのでぜひやってみてください．
大学生の方はICPCという大学対抗のプログラミングコンテストもあるので，大学生で興味を持った方はそちらも調べてみてください．
興味を持たれた方はぜひ競技プログラミングをやりましょう！
・Topcoder
https://www.topcoder.com
・Codeforces
http://codeforces.com
・AtCoder
http://atcoder.jp
・yukicoder
http://yukicoder.me
・Aizu Online Judge
http://judge.u-aizu.ac.jp/onlinejudge
・PKU JudgeOnline
http://poj.org
・ICPC
http://icpc.iisf.or.jp/