競技プログラミング用語集 

ICPCやTopcoder,Atcoderなどの競技プログラミング関係の用語のまとめです。

*

ABCD

A+B Problem【-】 Back
標準入力から2つの数値を読み込み,その合計を出力しなさい,という競技プログラミングの入門として題材にされる問題.
ただ足し算をするだけのシンプルな問題だが,標準入力からの読み込み,数値計算の仕方,標準出力への書き出しといった,プログラミングで必要とされる処理の基本的な要素が詰まっている.

問題例
A+B Problem
標準入力から2つの数値を読み込み,その合計を出力しなさい,という競技プログラミングの入門として題材にされる問題. ただ足し算をするだけのシンプルな問題だが,標準入力からの読み込み,数値計算の仕方,標準出力への書き出しといった,プログラミングで必要とされる処理の基本的な要素が詰まっている. [http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1000,問題例]
AC【-】 Back ★1
Accepted.正解.一発で出ると嬉しい.
AC
Accepted.正解.一発で出ると嬉しい.
AOJ【-】 Back
Aizu Online Judge.情報オリンピックや,ICPC国内予選など,主に日本で過去に行われたプログラミングコンテストの問題がまとまっている.
問題に対して回答コードを提出すると,実際に正誤を判定してもらえる.

AOJ
AOJ
Aizu Online Judge.情報オリンピックや,ICPC国内予選など,主に日本で過去に行われたプログラミングコンテストの問題がまとまっている. 問題に対して回答コードを提出すると,実際に正誤を判定してもらえる. [http://judge.u-aizu.ac.jp/onlinejudge/,AOJ]
AtCoder【-】 Back ★1
@chokudai氏の運営するプログラミングコンテストサイト.定期開催型のARC(AtCoder Regular Contest)の他,一部の学生有志主催のコンテスト(WUPC2012、KUPC2012など)にもシステムを提供している.

AtCoder
AtCoder
@chokudai氏の運営するプログラミングコンテストサイト.定期開催型のARC(AtCoder Regular Contest)の他,一部の学生有志主催のコンテスト(WUPC2012、KUPC2012など)にもシステムを提供している. [http://atcoder.jp,AtCoder]
BFS【-】 Back
幅優先探索.キューを用いた実装が一般的である.

See also →DFS
BFS
幅優先探索.キューを用いた実装が一般的である. See also {DFS}
DFS【-】 Back
深さ優先探索.再帰による実装が一般的である.

See also →BFS
DFS
深さ優先探索.再帰による実装が一般的である. See also {BFS}
DP【-】 Back
Dynamic Programming.動的計画法.
自明なところから始めて,規模の小さい部分問題の解を利用して本来求めたい解を順に求めていくテクニック.
競技プログラミングでは頻出.
DP
Dynamic Programming.動的計画法. 自明なところから始めて,規模の小さい部分問題の解を利用して本来求めたい解を順に求めていくテクニック. 競技プログラミングでは頻出.

EFG

gl hf【-】 Back
Good Luck, Have Fun の略.
Topcoder SRM開始直前のArenaのチャットで散見される.
gl hf
Good Luck, Have Fun の略. Topcoder SRM開始直前のArenaのチャットで散見される.

HIJK

ICPC【-】 Back
正式名は ACM International Collegiate Programming Contest.年に一度行われる,大学対抗のプログラミングコンテストの世界大会である.
世界大会に出場するには,6〜7月に行われる国内予選と,11月に行われるアジア地区予選を勝ち抜かねばならない.
ICPC
正式名は ACM International Collegiate Programming Contest.年に一度行われる,大学対抗のプログラミングコンテストの世界大会である. 世界大会に出場するには,6〜7月に行われる国内予選と,11月に行われるアジア地区予選を勝ち抜かねばならない.

LMN

MLE【-】 Back
Memory Limit Exceeded.提出したプログラムが指定された量以上のメモリを使おうとしたため,不正解となった.
MLE
Memory Limit Exceeded.提出したプログラムが指定された量以上のメモリを使おうとしたため,不正解となった.
MST【-】 Back
Minimum Spanning Tree.

最小全域木
MST
Minimum Spanning Tree. {最小全域木}

OPQR

RE【-】 Back
Runtime Error.プログラムが実行時にエラーとなった.
主な原因としては配列のインデックス指定ミスや,0による除算などが挙げられる.
RE
Runtime Error.プログラムが実行時にエラーとなった. 主な原因としては配列のインデックス指定ミスや,0による除算などが挙げられる.

STU

SRM【-】 Back
Single Round Match.Topcoder社による定期開催型コンテスト.「するめ」とも.
75分でeasy, medium, hardの3問を解くコンテスト.コーディングのあと,他の人のコードの間違いを指摘すれば追加点がもらえる「Challenge Phase」があるのが特徴.
SRM
Single Round Match.Topcoder社による定期開催型コンテスト.「するめ」とも. 75分でeasy, medium, hardの3問を解くコンテスト.コーディングのあと,他の人のコードの間違いを指摘すれば追加点がもらえる「Challenge Phase」があるのが特徴.
Standings【-】 Back
順位表のこと.Topcoder SRM では Division Summary と表示される.
多くのコンテストにおいて,競技中は順位表がリアルタイムに更新される.
Standings
順位表のこと.Topcoder SRM では Division Summary と表示される. 多くのコンテストにおいて,競技中は順位表がリアルタイムに更新される.
TLE【-】 Back
Time Limit Exceeded.プログラムが規定時間内に正しい答えを返さなかったため,不正解となった.
アルゴリズムを改善する必要がある.
TLE
Time Limit Exceeded.プログラムが規定時間内に正しい答えを返さなかったため,不正解となった. アルゴリズムを改善する必要がある.

VWXYZ

WA【-】 Back
Wrong Answer.不正解.
WA
Wrong Answer.不正解.
WAになっておどろう【-】 Back ★1
元は楽曲の名前であるが,競技プログラマには不思議と違う意味に聞こえてくる.
WAになっておどろう
元は楽曲の名前であるが,競技プログラマには不思議と違う意味に聞こえてくる.

あきばやべぇ【-】 Back
プログラミングコンテストで素晴らしい成績を収めている秋葉拓哉氏を称える言葉.
蟻本の著者の一人でもある.実際やばい.
あきばやべぇ.

いうぃったー
あきばやべぇ
プログラミングコンテストで素晴らしい成績を収めている秋葉拓哉氏を称える言葉. 蟻本の著者の一人でもある.実際やばい. あきばやべぇ. [http://shindanmaker.com/36663,いうぃったー]
蟻本【ありほん】 Back
プログラミングコンテストチャレンジブック
蟻本
{プログラミングコンテストチャレンジブック}

最小全域木【さいしょうぜんいきぎ】 Back
あるグラフが与えられたとき,辺を自由に削ってできるグラフで,任意の2頂点を連結にする(=どの頂点からスタートしても,グラフの他の頂点にたどり着ける)ような木をあるグラフの全域木という.最小全域木とは,そのような木のうち,辺の重みの和が最小であるものをいう.

最小全域木を多項式時間で求めるアルゴリズムとして,プリム法,クラスカル法が知られている.どちらの手法も計算量は,頂点数をV,辺数をEとおくと O(ElogV) である.
最小全域木
あるグラフが与えられたとき,辺を自由に削ってできるグラフで,任意の2頂点を連結にする(=どの頂点からスタートしても,グラフの他の頂点にたどり着ける)ような木をあるグラフの全域木という.最小全域木とは,そのような木のうち,辺の重みの和が最小であるものをいう. 最小全域木を多項式時間で求めるアルゴリズムとして,プリム法,クラスカル法が知られている.どちらの手法も計算量は,頂点数をV,辺数をEとおくと O(ElogV) である.
写経【しゃきょう】 Back
Topcoder SRMや Codeforces において,撃墜のために相手のコードをそっくりそのまま書き写すこと.撃墜の制度があるコンテストでは,コードのコピー&ペーストが禁じられているため,見てタイプして写すしかない.
撃墜においては,相手が間違った答えを返すような入力を用意しなければならないが,それが目視では困難なときに使われる.

用例:「怪しいコードあったから写経してたけど他の人に取られちゃったよ」
写経
Topcoder SRMや Codeforces において,撃墜のために相手のコードをそっくりそのまま書き写すこと.撃墜の制度があるコンテストでは,コードのコピー&ペーストが禁じられているため,見てタイプして写すしかない. 撃墜においては,相手が間違った答えを返すような入力を用意しなければならないが,それが目視では困難なときに使われる. 用例:「怪しいコードあったから写経してたけど他の人に取られちゃったよ」
女装【じょそう】 Back
女の子の格好をすること.競技プログラミング界隈では何故か時々見かけるワードである.
女装
女の子の格好をすること.競技プログラミング界隈では何故か時々見かけるワードである.
するめ【-】 Back
SRM
するめ
{SRM}

血の海【ちのうみ】 Back
(主に Topcoder SRM において) システムテスト後の順位表が Failed System Testで埋め尽くされているさま.
サンプルとして提示されているケースが弱かったり,問題をよく読まないと気づきにくいコーナーケースがあったりするとこの現象が起こりやすい.
血の海
(主に Topcoder SRM において) システムテスト後の順位表が Failed System Testで埋め尽くされているさま. サンプルとして提示されているケースが弱かったり,問題をよく読まないと気づきにくいコーナーケースがあったりするとこの現象が起こりやすい.

2分探索【にふんたんさく】 Back
2分間探し続け,それでも見つからなかったら諦めるという手法.
2分探索
2分間探し続け,それでも見つからなかったら諦めるという手法.
にぶたん【-】 Back
二分探索
にぶたん
{二分探索}
二分探索【にぶんたんさく】 Back
探索範囲を半分ずつ狭くしていきながら解を求めるテクニック.
二分探索
探索範囲を半分ずつ狭くしていきながら解を求めるテクニック.

ブラインド爆撃【ぶらいんどばくげき】 Back
提出が異様に早かったり,難しい問題をレートにそぐわない人が出していたりするコードを「多分間違っているだろう」と決めつけて撃墜を試みる行為.
ブラインド爆撃
提出が異様に早かったり,難しい問題をレートにそぐわない人が出していたりするコードを「多分間違っているだろう」と決めつけて撃墜を試みる行為.
プログラミングコンテストチャレンジブック【-】 Back ★1
通称蟻本.現役競技プログラマによるアルゴリズムの解説本.
プログラミングコンテストに出てくるアルゴリズムを,基本から応用まで幅広くカバーしている.競技プログラマのバイブル.
上級編の内容はかなり難しい.この本をマスターすれば,レッドコーダーになれるかも!
プログラミングコンテストチャレンジブック
通称蟻本.現役競技プログラマによるアルゴリズムの解説本. プログラミングコンテストに出てくるアルゴリズムを,基本から応用まで幅広くカバーしている.競技プログラマのバイブル. 上級編の内容はかなり難しい.この本をマスターすれば,レッドコーダーになれるかも!
プログラミングコンテストに登場するキャラクター【-】 Back
うさぎのHanako,きつねのCiel,うなぎのTakahashikun,農夫ジョン,toastmanなどが登場する.

参考
プログラミングコンテストに登場するキャラクター
うさぎのHanako,きつねのCiel,うなぎのTakahashikun,農夫ジョン,toastmanなどが登場する. [http://d.hatena.ne.jp/rng_58/,参考]

やるだけ【-】 Back
実装するだけ,とも.問題の要求通りに,素直に実装するだけで答えが得られるような問題に対しての形容.
やるだけ
実装するだけ,とも.問題の要求通りに,素直に実装するだけで答えが得られるような問題に対しての形容.

レッドコーダー【-】 Back
TopcoderやCodeforcesにおいて,一定以上のレーティングを得た者は名前の部分が赤く表示され,レッドコーダーと呼ばれるようになる.
例えばTopcoderでは2200以上のレーティングを持つ者が該当し,その人数は競技人口の上位約3%ほど.
ちなみに,2012年7月現在,日本には26名のレッドコーダーが存在する.
レッドコーダー
TopcoderやCodeforcesにおいて,一定以上のレーティングを得た者は名前の部分が赤く表示され,レッドコーダーと呼ばれるようになる. 例えばTopcoderでは2200以上のレーティングを持つ者が該当し,その人数は競技人口の上位約3%ほど. ちなみに,2012年7月現在,日本には26名のレッドコーダーが存在する.

300【-】 Back
Topcoder SRMにおいて不吉な匂いを漂わせるeasy問題の配点.
通常の 250点 に対して比較的難易度が高いことを表している.
まれに 275 という配点も存在する.
300
Topcoder SRMにおいて不吉な匂いを漂わせるeasy問題の配点. 通常の 250点 に対して比較的難易度が高いことを表している. まれに 275 という配点も存在する.