競技プログラミング

競技プログラミングとは、プログラミングして競いあう競技である。プログラミングコンテストともいう。

概要

競技プログラミングとは、条件を満たすプログラムを書き上げる時間を競ったり、書いたプログラムの性能を競ったりする競技である。

「プログラミング」コンテストあるいは競技「プログラミング」と名乗ってはいるが、「プログラミング」の技術が必要になるのは分岐・反復からせいぜい配列・クラスまでとごく基本的な部分で、デザインパターンのようなプログラミング手法や、windows.hライブラリやLinuxコマンドのようなアプリケーションやOSの知識は必要ではない。

むしろ必要になるのは数論を始めとした様々なアルゴリズムの知識と数学の素養、特にアルゴリズムの構成力である。プログラミングコンテストではなくアルゴリズムコンテストとでも呼んだほうがいいのではないだろうか。

方式

問題タイプと制限時間

競技プログラミング大会として多いのは、「与えられた問題が制限時間内(数秒以内とか)に解けるプログラムコード」を製作し終えるまでの時間を競うタイプである。製作に与えられる時間は1〜2時間程度で、単に競技プログラミングと言った場合、このタイプの大会を指すことが多い。

(睡眠をはさんで)2日以上に渡ってコーディングをする前提のものはマラソンとも呼ばれ、期間は数週間に渡ることがある。このタイプの大会では正解が存在せず、「与えられた条件に最も適した解答をするプログラムコード」を製作した者が優勝となる方式が多い。

使用言語

速度の問題で、使われるプログラミング言語の割合は、C++ > Python > C# = C > Java >> その他、といった感じらしい。大会によって使える言語が限られているので、自分の使用言語を採用している大会を選ぶと良いだろう。ただし、使用言語によっては実行時間制限をクリアできる保証がされていない場合もある。正しいアルゴリズムを選択できさえすれば言語処理系の速度の差は問題にならないことが多いが、マイナー言語を選択する場合は心に留めておいた方が良いかもしれない。

環境

自宅からネットにつながった自分のパソコンで参加し、Webサイトに自分で書いたソースコードを提出して、プログラムに自動判定させる「オンラインジャッジシステム」が主流。

自分のパソコンなので、あらかじめ主なアルゴリズムを実装しておいて、問題に適したアルゴリズムのコードをコピペして時間を短縮することができる。この短縮方法は公認されていることがほとんどであるが、正式には個々の大会規約を確認のこと。

大きな大会の決勝にもなると、会場に招かれて主催者が用意したPC上でギャラリー監視の中コーディングするという場面も出てくる。

個人参加のものが多いが、3人くらいのチームで参加できるものもある。

ランキング

ほとんどの大会で、大会終了後にランキングが発表される。頻繁に大会を開催するサイトでは過去の成績に応じてユーザーのクラス分けが行われる。クラス名には色を用い、最上位のクラスには赤色が割り当てられてレッドコーダーと呼ばれることが多い。

競技プログラミングへの批判

上述の通り主に試されるのはプログラミングよりもアルゴリズムの構築力であるため、競技プログラミングは(プログラミングの)役に立たないと批判されることがある。名前をアルゴリズムコンテストに変えれば万事解決しそうな気がする。大事なことなので(ry

この話題は宗教戦争に近いものがあるので、以下ではやや煽り気味に紹介するが、掲示板はほんわかレス推奨。

主な批判

• 競技プログラミングをやると、可読性より速度を優先するため、汚いコードを書く癖がつく。
• 競技プログラミングをいくらやったところで、ライブラリの使い方や設計技術は身につかない。
• 競技プログラミングのランキングをあげても就職の役には立たない。

主な反論

• 競技プログラミングを極めた人のコードは美しい。汚いのは無能の証。美しさが分からないのも無能の証。
• 競技プログラミングを通じてアルゴリズムの考え方を身につければ、設計などもおのずと洗練されてくる。
• むしろ、計算量の見積もりもせずに設計してプロジェクトを破綻させるのは、非競プロerの方。
• お前らIT土方の就職には役立たないが、一流の人材を求めるところでは評価する会社もある。

例題

例題としてAtCoderから簡単な問題を解いてみる。

問題

500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りあるでしょうか？

【入力】
入力は以下の形式で標準入力から与えられる。

A
B
C
X

【制約】
0≤A,B,C≤50
A+B+C≥1
50≤X≤20000
A,B,Cは0以上の整数である
X は 50 の倍数である

【制限】
実行時間制限: 2秒以内
使用メモリー制限: 256MB以内

AtCoder Beginner Contest 087 B - Coins より

解答例

C言語の解答例

#include <stdio.h>
int main()
{
  int A,B,C,X;
  int a,b,c;
  int ans=0;
  scanf("%d",A);
  scanf("%d",B);
  scanf("%d",C);
  scanf("%d",X);
  for(a=0;a<=A;a++)
   {
     for(b=0,b<=B;b++)
      {
        for(c=0;c<=C;c++)
         {
           if(500*a+100*b+50*c==X)
            {
              ans++;
            }
         }
      }
   }
  printf("%d",ans);
  return 0;
}

解説

人間が考えるような方法をコードに起こしてもいいが、このコードは「(a,b,c)の全ての組合せで実際にXと一致するか総当たりでチェックする」という、単純だが人力でやったら非常に時間がかかる一方でコンピュータならすぐに終わる、というアルゴリズムになっている。工夫がいらないところには工夫をしないというのもテクニックのうちである。

しかし、X, A, B, Cの範囲によっては実行制限時間(2秒)以内に処理が終わらない、あるいは計算中に32ビットで表現しきれない整数が出てきて正しく計算できない、などの可能性が出てくるので工夫をする必要が出てくるだろう。

傾向

問題は数論が多い傾向にあり、Xⁿを8ケタくらいの素数で割った余りを求めさせる問題などは基本問題である。中級になると、木構造(木造住宅の構造ではない)などのデータ構造・グラフを扱う問題も出てくる。また、コンピュータにとって理解しやすいアルゴリズムは簡潔なコードになる傾向にある(模範解答がそうなるように問題を作ってあるというのもある)。

様々なアルゴリズムの実装に慣れていないと解答の方針すら分からず終わってしまう可能性もあるが、正答を得られた時は苦労に見合った達成感があるだろう。

主要な競技プログラミングコンテスト

日本語対応あり

• AtCoder
• AOJ (Aizu Online Judge)
• YukiCoder
• KMCoder

英語のみ

• IEEEXtreme
• TopCoder
• CodeForces
• GCJ (Google Code Jam)
• ACM/ICPC (International Collegiate Programming Contest)

関連動画

関連商品

関連項目

• アルゴリズム
• 組み合わせ爆発
• 数学
• 数論
• 情報理論
• CTF(セキュリティコンテスト)
• コードゴルフ
• ワンライナー
• 将棋電王トーナメント
• bits/stdc++.h: 競技プログラミングでよく使われるgcc専用c++ヘッダーファイル。
• プログラミング
• プログラミング関連用語の一覧
• e-sports