競技プログラミングへの誘い

シェアする

  • このエントリーをはてなブックマークに追加

私はいつからだか忘れましたが、ちょくちょく「競技プログラミング」あるいは「プログラミングコンテスト」というものに参加しています。

先日、「プログラミングコンテストチャレンジブック」という、競技プログラミング界で有名な秋葉拓哉先生などによって書かれた競プロの本を買いましたが、動的計画法やグラフ問題について詳しく書いていてとても良い本のようです(まだちゃんと読めていません)。

競技とかコンテストとか聞くと、なんかめんどくさそうなものに感じるかもしれませんが、実際は全然そんなことありません。かなり気楽に参加できます。

私は、プログラミングが苦手(だけどやらないといけない)という学生こそ、プログラミングコンテストに参加するべきだと思っています。日常的にたくさんプログラミングをすることで勘のようなものが養われていくと思うので。

そこで、今回はプログラミングコンテストの魅力を紹介してみます。

まず、「コンテスト」と言いますが、外出して会場へ行く必要も事前に参加登録をする必要もありません。(アカウントを作成する必要はあります)

自宅のPCで、インターネットにつないでWebページを開き、テキストボックスにコードをコピペして送信ボタンを押すだけです。

世界規模のプログラミングコンテスト(略してプロコン)は英語を読む必要がある上に開催時間が時差の影響で日本時間午前2時とかになることがあるので、とりあえず日本のプロコンについて見ましょう。

プロコン入門におすすめなのがAtCoderというサービスです。

不定期(月2,3回ぐらい?)にAtCoder Regular Contest(ARC)やAtCoder Beginner Contest(ABC)を開催しています。

しかも、多くのプロコンサイトと同様に、過去問をいつでも自由に解くことができます。判定は全て機械によって自動的に行われるので、どんな時間に提出しても採点してくれます。

さらに、終了したコンテストであれば、他人の解答を(正解したのも不正解だったのも含めて)自由に見ることができます!「はあ?こんなんどう書いたらええねん!」ってなっても、自分が使う言語で書かれた、正解したコードを見ることで「なるほど!そうやるのか!」ってなります。

今回は、AtCoderの問題を例に解答の仕方を解説します。

AtCoderに参加する方法

参加するには、トップページの過去のコンテスト一覧(AtCoder Beginner Contest #031(ABC #031)とかいっぱい並んでるやつ)をクリックして、右上の「新規登録」をクリックしてアカウントを作成します。

ユーザIDは登録後に変更できないので注意してください。

登録した場合は、試しに「AtCoder Beginner Contest #026(ABC #026)」をクリックしてみてください。(登録していない場合は記事の続きを読んでみてください。)

「参加する」みたいなボタンがあればクリックしてください。無ければいいです。

画面上部の「問題」タブをクリックすると、4つの問題のタイトルが表示されます。

「掛け算の最大値」という問題をクリックすると、問題が表示されます。

問題文
正の偶数 A が与えられる。

x+y=A となる正の整数 x, y のうち、 x×y が最大となるものを選び、その値を出力しなさい。

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

A

1 行目には、正の偶数 A(2≦A≦100) が与えられる。

出力
x×y の最大値を出力しなさい。 出力の末尾には改行を入れること。

この下に入出力例が記載されています。

以下、答えを書いていくので、考えてみたい場合は一度立ち止まってみて下さい。

C言語で解いてみましょう。

main()関数の中で、まず、Aという値を受け取る必要があります。

int A;
scanf("%d", &A);

つぎに、x+y=Aとなる正整数x,yに関して、x*yを計算していき、その最大値を求めます。

xの最小値は1、最大値はA-1となります(正整数のため)。このとき、yはA-xとなります。

int x;
int max = 0;
for(x = 1; x < A; x++){
	if(x * (A - x) > max){
		max = x * (A - x);
	}
}

最後に、得られた最大値を標準出力に表示します(すなわち、printf()します)。

printf("%d", max);

以上で完成です。全体をちゃんと書くと、

#include <stdio.h>

int main(void){
	int A, x, max = 0;
	scanf("%d", &A);
	for(x = 1; x < A; x++){
		if(x * (A - x) > max){
			max = x * (A - x);
		}
	}
	printf("%d", max);
	return 0;
}

これを提出します。

ページの最下部にある「提出」ボタンをクリックします。

problem

「言語」の欄は「C++ (GCC 4.9.2)」となっていますが、C言語でもC++として提出することになっているのでこのままで大丈夫です。別の言語で提出する場合は変え忘れないように注意してください。

次に、「ソースコード」のテキストボックスに、上記のソースコードまたは自作のプログラムのソースコードをコピペしてください。

submit1

そして、下部の「ソースコードを提出する」ボタンをクリックしましょう。

submit2

すると、自動的にジャッジが始まります。

上記のソースコードでは[WJ](Waiting Judge:判定完了待ち)と表示されたのち、何度かページを再読み込みすると[AC](ACcepted:正しいコードとして認められました)と表示されるはずです。これで解答完了です。

(数学ができる人なら、これが最前のアルゴリズムではないと気付くと思います。このアルゴリズムはO(n)時間なので問題はありませんが、O(1)時間で終了するアルゴリズムも簡単に作れます。Aが偶数であることが保障されているのもポイントです。ぜひ考えてみて下さい。)

以上が、AtCoderに参加する方法です。

また、AtCoderの良いところは、コンテスト終了後に解説がSlideShareにて公開されるだけでなく、コンテスト終了後に解説生放送をニコニコ生放送にて行ってくれるところです。

AtCoderには、Beginner ContestのA問題のような、プログラミング経験3日でも解けるような問題から、Regular ContestのD問題のような、1年以上経験があっても難しい問題まで、幅広い難易度の問題があるので、ここだけでかなりスキルアップができると思います。

また、AtCoderのサイトで他の企業が主催するコンテストが開かれることもあります(来年にドワンゴ主催のコンテストがあったり、リクルート主催のCODE FESTIVALの予選があったり)。

興味のある人は、twitterアカウントを持っていれば「AtCoder公式アカウント(@atcoder)」や株式会社AtCoder社長であり有名なプログラマーである「chokudai(高橋直大)(@chokudai)」さんをフォローしてみましょう。コンテスト情報がたくさん得られます。

大学の課題や将来の仕事でプログラミングをするかもしれない人は、とても手軽なのでぜひ参加してみて下さい。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする