LE社のエンジニアたちの風がふくまま気の向くまま本音コラム

競技プログラマの間で名高い、オンラインジャッジまとめ

»

 リーディング・エッジ社の吉永彰成です。以前言語マニアが勧めるプログラミングコンテストまとめというコラムを書いたところ、私の想像以上に多くの人にご覧頂きました。今回は、プログラミングコンテストと関連して、一般にオンラインジャッジと呼ばれるいくつかのサイトをご紹介します。

■オンラインジャッジについて

 オンラインジャッジは、与えられた問題を解くソースコードを提出すると、そのソースコードが正確かどうか判定してくれるWebサービスです。具体的なサービスの内容は下記の通りです。

  • 無料で利用できますが、利用前にアカウントの登録が必要
  • 簡単なものから難しいものまでさまざまなレベルの問題が与えられる
  • サンプルのインプット(入力)とアウトプット(出力)が与えられる
  • プログラムの実行時間の制限とメモリの使用量の制限が与えられる
  • 使用できるプログラミング言語は、各オンラインジャッジで異なりますが、C++、Javaなどを使える
  • 問題を解くソースコードを提出すると、そのソースコードがビルドされて、バグの有無やプログラムの実行時間、メモリの使用量などをチェックするテストが実行される
  • テスト実行後、結果(正解/不正解/時間制限オーバー/メモリ制限オーバー)やプログラムの実行時間、メモリの使用量、使用したプログラミング言語などが表示される

 問題の内容は、基本的なアルゴリズムの実装能力を試すものから数論やグラフ理論のような高度な数学・計算機科学の知識が必要となるものまで、実に多種多様です。多くの問題では、複数の解法で解けるため、平凡な発想で力任せ(ゴリ押し)で長時間かけて解く人もいれば、高度な発想で美しくエレガントなソースコードを素早く書き上げる人もいます。利用者のスキルに応じて、プログラミングの実技試験対策やプログラミングコンテストの練習として利用できます。

 以下では、日本の競技プログラマの中で知名度の高いオンラインジャッジをいくつかご紹介します。

■PKU JudgeOnline

 PKU JudgeOnlineは、北京大学のオンラインジャッジです。PKUやPOJという略称で親しまれています。主な特徴は下記の通りです。

  • 競技プログラマならば、誰もが知っているオンラインジャッジ
  • 時々、プログラミングコンテストが開催されている
  • 使用可能な言語は、C、C++、Java、Fortran
  • 問題数は3000以上
  • 問題文は英語ですが、中には日本語に翻訳されている問題もある

■AIZU ONLINE JUDGE

 AIZU ONLINE JUDGEは、会津大学のオンラインジャッジです。AOJという略称で親しまれています。主な特徴は下記の通りです。

  • 日本のオンラインジャッジ!
  • 時々、プログラミングコンテストが開催されている
  • 使用可能な言語は、C、C++、Java
  • 問題は、日本情報オリンピックやACM国際大学対抗プログラミングコンテストなどの過去問
  • 問題文は英語ですが、日本語の問題もある

■その他のオンラインジャッジ

 前回ご紹介したプログラミングコンテストTopCoderCodeforcesでは、過去問が公開されており、ソースコードの提出及びテストが可能のため、オンラインジャッジとして利用できます。

■オンラインジャッジの活用方法

 オンラインジャッジの問題やプログラミングコンテストの過去問を解いた人の中には、解いた問題のソースコードをブログで掲載している人もいます。例えば、TopCoder部でリンクされているブログを見てみて下さい。この中には、RedCoderと呼ばれるTopCoderの上位者のブログもあり、着眼点や解答に至るまでの思考過程が、非常に参考になります。

■参考書

 前回ご紹介した『プログラミングコンテストチャレンジブック』の第二版が出版されています。この第二版では、PKU JudgeOnline、AIZU ONLINE JUDGE、Codeforcesの問題が練習問題として参照されています。

■最後に

 最近では、日本でも、エンジニアのプログラミング能力を見るため、プログラムを書いて提出するシステムを採用試験として導入する企業が現れ始めました。上記のようなオンラインジャッジで問題を解き、優れたプログラマのソースコードを読む事で、アルゴリズムとデータ構造の知識を深め、実装力を磨く事で、このような試験に対しても有利になれるのではないでしょうか。

Comment(0)