編集  

競技プログラミング単語

キョウギプログラミング

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

概要

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

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

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

方式

問題タイプと制限時間

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

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

使用言語

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

環境

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

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

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

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

ランキング

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

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

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

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

主な批判

主な反論

例題

例題として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ビットで表現しきれない整数が出てきて正しく計算できない、などの可性が出てくるので工夫をする必要が出てくるだろう。

傾向

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

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

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

日本語対応あり

英語のみ

関連動画

関連商品

関連項目


【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
ページ番号: 5538354 リビジョン番号: 2632911
読み:キョウギプログラミング
初版作成日: 18/08/11 10:21 ◆ 最終更新日: 18/10/13 09:28
編集内容についての説明/コメント: 批判への反論追加。e-sportsに含むかどうかは微妙なので打ち消し線をひいた。
記事編集 / 編集履歴を閲覧

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

競技プログラミングについて語るスレ


まだ掲示板に書き込みがありません… 以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • 競技プログラミングについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!


急上昇ワード
ニコニコニューストピックス