競プロをやろう

こんにちは。traP競プロ担当の@_n_ariです。
今回はtraPの皆さん、および外部の皆さんに、競プロの素晴らしさを布教するためキーボードを叩きました。

競プロとは

競プロとは「競技プログラミング」の略で、その名の通りプログラミングで競い合うことです。
とはいってもどうやって競うのか想像がつかないと思います。
競プロでは、与えられた課題を適切に処理して返すプログラムを素早く提出することで競います。
例えば次のような問題が考えられます。

問題

整数Bと、長さB(bit)の2進数Nが与えられる。
Nが素数であれば"Yes"、素数でないなら"No"と1行に出力せよ。

制約

1<=B<=30
(Nの文字数)=B
Nの各文字は0または1
Nの最初の文字は1

この問題を解くのに必要なプロセスはどのようなものでしょう？
まず、Bは最大でも30であるため、Nは大きくとも2の30乗程度であるため、int型の整数に入ります。
次に、2進数で渡されても、そのままint型の変数には入れられないため、これを整数に戻してあげる必要があります。
2の冪乗と各桁を掛け算してそれぞれ足し合わせることで、整数に戻せます。
最後に、Nが素数であるかどうかを判定します。これは x*x<=N であるxで試し割りをしていけば十分で、xの候補は√N程度、だいたい3万通りです。
なお、x*x>N であるxについて万が一Nが割り切れた場合、x*y=N というyが存在するはずですが、y=N/x で、
y*y=(N*N)/(x*x)<N であるため、x*x<=N で十分であることが分かります。
これをプログラムで書くと、以下のようになります。

// binary_prime_check.cpp
#include <stdio.h>

using namespace std;

int main(){
  // 入力
  int B;
  char s[31];
  scanf("%d",&B);
  scanf("%s",s);
  // int型変数に代入
  int N = 0;
  for(int i=0;i<B;i++){
    if(s[i]=='1') N += 1<<(B-1-i);  // 1<<(B-1-i) は2の(B-1-i)乗です
  }
  // 素数判定
  bool flag = true;
  for(int x=2;x*x<=N;x++){
    if(N%x==0){
      flag = false;
      break;
    }
  }
  // 出力
  if(flag){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

以上が割と簡単な方ですが競プロの問題の一例です。
さて、ここでプログラムを書くのに使ったことは以下のとおりです。

• 入力を適切に受け取る
• 処理をする
  • 2進数の文字列を整数に直す
  • 素数判定をする
• 出力を問題文通りに行う

入力と出力は体裁と改行に気をつければ問題無いですが、重要なのは処理をする部分です。
例えば、素数判定で x*x<=N ではなく x<N としたらどうでしょう？
Nは最大で2の30乗、10の9乗ぐらいになります。
実は、これは3秒ぐらいかかる処理になります。
というのは、現代の一般的なコンピュータでは、1秒に大体10の8乗ぐらいの処理しかできません。(環境に依存します)
また、競プロの問題にはTime Limit(実行時間制限)が設けられており、大体が2秒程度です。
そのため、x<N とする素数判定は、TLE(Time Limit Exceeded)となってしまいます。
よって、正しいことは前提として、処理を時間内に収める工夫が必要となります。
この「時間内に収める」というところで非常に頭を使うこととなりますが、ここが競プロの醍醐味と言えます。
さて、こうして1問解くことが出来ました。実際の競プロのコンテストでは3問～10問程度の多種多様な問題を1時間～5時間で解き、
問題の難易度に応じて変わる点数の合計、さらには正解した時間の早い順に順位が付けられ、そこで競うことになります。
以上が競プロの大雑把な説明となります。

競プロは勉強になる

さて、こんなことをして一体何に役立つというのでしょう、というのが最初に湧いてくる疑問だと思います。
素数判定はちょっとだけ役に立つパターンが分かりづらいので、もっとお役所仕事っぽい問題を考えてみましょう。

問題

A市役所では1ヶ月毎の収支を(収入-支出)という値で管理していました。
しかし役所に勤めるSobayaさんは、2015年のデータの内、ある1ヶ月分のデータを紛失してしまいました。
これでは上司のJunNaruseさんに怒られてしまいます。
幸い、1年の収支の平均値の小数点以下を切り捨てた数値が残っていました。
紛失したデータとして考えられる最小値および最大値を、空白区切りで1行に出力してください。
なお、この問題で切り捨てとは、小数点以下を無視することであり、
N>=0 として、N<=x<n+1 のxに対してはnを、-(n+1)<x<=-n のxに対しては-nを、それぞれxの小数点以下を切り捨てた値とする。

制約

1行目に12個空白区切りでデータが与えられる。
紛失したデータが1つだけあり、その月のデータは'-'1文字で表される。
紛失していないデータは符号付き整数で与えられ、絶対値は1000000以下である。
2行目に平均値のデータが符号付き整数で与えられる。

まさにお役所、という感じの問題になりました。
このように書くと、実際に役に立ちそうな気がしますね？
もう少し難しい問題を考えてみましょう。

問題

B市役所ではデータの整理を行っていました。
N個の文字列S_i(1<=i<=N)が与えられます。
B市役所のdeka0106さん(通称「全強のDEKA16」)はこの中からQ個の目的の文字列T_i(1<=i<=Q)を探したいです。
とりあえず、調べるのにどれぐらい時間がかかるかを調べたいので、文字列T_iが、何回N個の文字列S_i全体に登場するかを数えたくなりました。
全強のDEKA16さんを手伝ってあげるプログラムを書いてください。
出力は、T_i(1<=i<=Q)が登場する回数を順に1行ずつ、合計Q行にわたって出力してください。

制約

1行目に空白区切りでNとQが与えられます。N,Qはそれぞれ1以上1000以下です。
2行目からN+1行目までに、探される文字列であるS_iがN個与えられます。S_iの全ての文字列の長さの合計は100000を超えません。
N+2行目からN+Q+1行目までに、探す文字列であるT_iがQ個与えられます。Q_iのすべての文字列の長さの合計は100000を超えません。

(少し厳密ではないですが、雰囲気だけ伝わると良いです。鉞は困ります＞＜)
これも実際にありそうです。しかも少し難しいことが分かると思います。
というのは、長さLの文字列から長さMの文字列を探すことを考えてみると、Lの文字列の各文字からM文字が探す文字列に一致しているか、
というのを愚直に調べることになりますが、そうすると単純に考えて M*L だけのループが回ることになります。
今回の問題では合計で10万と10万ですから、10の10乗になります。これでは間に合いません。
また、ここで今回考えたことの規模をかなり大きくすると、まさにGoogle検索になります。
効率よく設計されたプログラムの流れを「アルゴリズム」と呼んだりします。
またアルゴリズムを適用するために設計された効率のよいデータの配置の仕方をデータ構造と呼んだりします。
例えばこの検索に使うアルゴリズムでは「二分探索」や「Aho-Corasick法」、「Rabin-Karp法」などがあり、
データ構造としては「Trie木」「Suffix Array」「ローリングハッシュ」などがあります。
これらのアルゴリズムやデータ構造を駆使することで、競プロでは制限時間内にプログラムが終わるような速いコードを書いていくのです。
これらはいわゆる「情報科学科」や「情報工学科」の分野の勉強となります。
競プロをすることで、競技ということで楽しみつつ切磋琢磨しつつ、学習をすることができるということです。
もちろんプログラミングすらやったことのない人にとっては、プログラミングを実際に書いてみて、
動くかどうか、正しいかどうか、評価してもらえる場所が与えられるのは非常に有意義であると考えます。

競プロは楽しい

さて、ここまで話してきましたが、多分「こんなのを楽しいと思うのはおかしい」という人も多くいると思います。
競プロはどうしても理論が出てしまうので、実際に参加してみるのが速いと思います。
日本語で開催されているコンテストとして、AtCoder社がおよそ隔週の土曜夜で行っている
AtCoder Beginner Contest(通称ABC)というものがあります。
これはその名の通り、競プロ初心者に向けたコンテストのため、気軽に参加することが出来ます。
次回は5月7日(土)21:00～23:00を予定されています。
是非参加してみてください。ただし、コンテスト中にTwitter等に問題について言及するのは禁止されています。注意してください。
リンク : AtCoder Beginner Contest 037
また、過去に行われた問題を解くこともできます。実際に解いてみて、入出力が正しくできるかどうか確認しておくことをオススメします。
過去の問題について言及することはAtCoderにおいては問題がありません。ググると解説記事も出てきたり解説スライドも公式で上がってたりします。
リンク : AtCoder (アットコーダー)

競プロもっとやりたい

競プロはいいぞ。
ということで、ここではいくつか、有名な競プロサイトを紹介します。

AtCoder

まず、上でも説明したAtCoderは日本最大のコンテストサイトです。?が食べられるコンテストや、
就活に繋がるようなコンテスト、泊まりで?が食べられるコンテストなどを開催しておりなかなかアクティブに活動しています。
AtCoderでは過去に開催されたコンテストの問題も解くことができるのは上で説明したとおりですが、
その際にAtCoder Problemsというサイトを使うと、自分がどれだけ過去問を解いたかが分かりやすくなるため便利です。
リンク : AtCoder Problems

yukicoder

こちらは有志が運営するサイトで、気軽に問題を出題する側に回れたりします。
大体隔週金曜の夜にコンテストを行っています。解説が付いてたり資料が豊富だったりととても勉強になります。
リンク : yukicoder

Aizu Online Judge

Aizu Online Judge(略称AOJ)は会津大学の運営するコンテストサイトです。
コンテストと言っても年に数回ICPCオープンコンテストや競プロ合宿で開催される程度ですが、AOJの魅力は問題の量にあります。
競プロ勉強用の入門問題から、パソコン甲子園、情報オリンピック、ICPCの過去問が大量にあり、いつでも解くことができます。
リンク : AIZU ONLINE JUDGE: Programming Challenge

TopCoder

TopCoderは世界で一番と言っても良い競プロのコンテストです。
不定期ですが月に2回程度TopCoder Single Round Match(略称SRM、するめ)が行われます。
TopCoderではレーティングにより、Target-Red-Yellow-Blue-Green-Grayと、色でランクが付けられます。
そのうちTargetは世界でも一握り程度しかなれず、Redでもレッドコーダーと呼ばれ強い競プロerである証となります。
SRMでレッドコーダーを目指すというのは全世界の競プロ勢共通の目標だと思います。
ただ、英語で問題が出されること、システムが初心者には難しいことがあり、なかなか敬遠されている気がします。。。
リンク : topcoder

CodeForces

CodeForcesも世界的に開催されている競プロのコンテストです。
こちらはTopCoderとは違いAtCoderのようにブラウザでコードを提出するタイプのため、こちらのほうが馴染みやすいかもしれません。
ただ、英語の問題文がTopCoder以上に読みづらかったり、開催時間が深夜1時過ぎであることがほとんどであるため、
TopCoder以上に敬遠されたりします。というか単位と体調が崩れる。
リンク : Codeforces

最後に

いかがでしたでしょうか。競プロの魅力が伝わったでしょうか。
競プロに少しでも興味を持ってくれたら嬉しいです。
ここで一つお知らせがあります。
競プロの学生コンテストとして、日本国内高校生向け「パソコン甲子園」、国際高校生向け「情報オリンピック」がありますが、
もう1つ、国際大学生向け「ACM-ICPC」というものがあります。
ICPCは国際大学対抗プログラミングコンテストで、大学生のみが参加できるプログラミングコンテストとなっています。
ICPCでは、同じ大学に在籍する3人チームで、まず日本国内で「アジア地区予選つくば大会」に出るための「国内予選」に参加します。
「国内予選」で上位になると、「アジア地区予選つくば大会」に出ることが出来るようになります。
「アジア地区予選つくば大会」でさらに上位になることで、晴れて「ICPC World Finals」に出られます。
東工大からWorld Finalsに出たのは、最近では2014年のことです。
リンク : 本学学生チームがACM-ICPC世界大会に出場決定 | 東工大ニュース | 東京工業大学
チームで行う競プロであるため、AtCoderとは違い戦略も大事になってきます。
traPからも数チーム、国内予選に出場させるつもりです。昨年度はtraPから「Arrows16」を含めた3チームが健闘しましたが、
「Arrows16」が25位に入るものの惜しくも地区予選出場ならずとなりました。
(25位は十分出場圏内ですが、ICPCはあくまで「大学対抗」であるため、同大学から多くチームが出場できないという制約があります。)
興味を持った人は、ぜひ今後traPにて行われる「競プロ勉強会」に参加してスキルを学んでみてください。
そして全国、世界と戦いましょう！
参考 : yosupot : 東京工業大学 ロボット技術研究会
(rogyに所属するレッドコーダーの先輩の記事です)