競技プログラミング単語

キョウギプログラミング
  • 3
  • 0pt
掲示板へ

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

概要

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

プログラミングコンテストあるいは競技「プログラミング」と名乗ってはいるが、「プログラミング」の技術が必要になるのは分岐・反復からせいぜい配列クラスまでとごく基本的な部分で、デザインパターンのようなプログラミング手法や、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 - Coinsexit より

解答例

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

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

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

日本語対応あり

英語のみ

関連動画

関連商品

関連項目

【スポンサーリンク】

  • 3
  • 0pt
スマホ版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

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

お絵カキコがありません

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

ピコカキコがありません

競技プログラミング

1 ななしのよっしん
2018/12/16(日) 18:56:49 ID: qtBKWS5OF3
AtCoderやってるけどサイトの説明が不親切に感じる
GP30スコアとは?殿堂入りとは?退会の方法は?(弊社所定の方法)
問題はいいんだがこの辺りがちょっとね・・・
2 ななしのよっしん
2019/02/03(日) 15:55:31 ID: W2LBrDFJ+j
ABC何回かやったけど、せいぜい時間内にC問題が解けるかどうかってとこだった
プログラマにならなくてよかったと痛感
3 ななしのよっしん
2019/10/24(木) 18:09:35 ID: qtBKWS5OF3
>>1
に関しては現在は良くなっているので撤回します
4 ななしのよっしん
2020/01/25(土) 12:34:53 ID: Ov8s7ijL53
プログラミングアルゴリズムを組むは大事かもしれないけど、
クラスの設計とかが出来た後に、その中のメソッドの中ではじめてアルゴリズムが実行される。
実務で競技プログラミングのような難しいアルゴリズムを組む課題が出たことがないので、競技プログラミングスルーしているわ。解けるようになったらいいなぁと思ってるが。

速度アルゴリズムよりも実装の設計や保守性も問われるような問題があればいいんだけど。
問題例としては、何度も仕様変更があって、そこからどう機を追加実装してもバグを出さなくするとか。

急上昇ワード

2020/01/30(木)06時更新