第2章　「競技プログラミング入門」 by 井上誠大 (73)

2.1　まえがき&競技プログラミングとは(小冊子の内容)

こんにちは、73回生の井上誠大です。73回生なので中学3年生ですね…(自覚が…)去年は旧中1らしくゲーム制作をしていたのですが、かなり苦労しました><去年はプログラミング初心者の登竜門(?)、TE*RISを作っていたのです。が、判定はガバガバ、描画もかなり簡素なものになってしまい、いかにゲーム作りが大変か思い知らされました^^;昔の話はこのくらいにして、今年は部誌を書くことになりました!わーい!NPCAの部誌を書くのは初めてどころか、入っていた他の部でも部誌はまだ書いたことがないので、不慣れなところ、日本語が多少不自由なところもあると思いますがよろしくお願いします。

僕は、今回の部誌で「競技プログラミング」について書きます。ひとまず「競技プログラミング」って何ぞや…と思われている方が相当数だと思うので、ここではそれを簡単に説明しようと思います。

競技プログラミングは、簡単に言うとプログラミングを競技化したものです。と言ってもお前それ語順入れ替えただけやろ、と怒られそうなのでもうちょっと具体的に言います。短時間(だいたい1.5-8時間)で何問か出題されるプログラミングやアルゴリズムに関する問題をプログラムを組んで解く、というのが競技プログラミングです。

プログラミングだのアルゴリズムなど難しそうな語句が並んでいますが、実際はプログラムを組む最低限の知識と環境、多少の算数力があれば充分楽しめます。実際、僕の場合、ゲームやWeb系統のものを開発するための知識をつけるのには挫折しましたが、競技プログラミングはすぐに慣れました。

具体的にどういった問題が出題されるのか、そのバリエーションは様々で、例えばある値を計算する、あることが可能か、条件を満たすものは何通りか、条件を満たす確率はどのくらいか、最短の距離はどのくらいか、中にはゲームの必勝法を考察するものまであります。全体的に算数や数学らしい内容です。

実際の競技は意外と短時間で、いかに速く解法を閃き、正確かつ迅速に正解を導き出すかも重要な要素になります。しかし、あまり速く解きすぎても誤答なら解答時間、つまり速度に多少のペナルティが科せられたりもします。

競技は主にインターネット上でオンラインで開催されるので、世界中のライバルと競うことも可能です。問題文が英語…なんてこともあったりしますが今回扱う競技プログラミングのサイトは大半が日本語なので心配不要です。

今回の部誌では、

この2つの競技プログラミングのWebサイトのうち初心者でも充分解くことができるような簡単な問題について解説しながら、競技プログラミングの基本中の基本を書きました。僕はC言語使いなのですが、その言語の基本も併せて多少は解説を挟むので、プログラミングに関する知識を僅かしか持っていない、そんな方でも内容を理解できるように努力したつもりです><

早速実際にC言語を利用して競技プログラミングの基本中の基本になる問題を解いていこうと思います。

ここから扱う問題が掲載されている、主にAizu Online Judgeのアカウントは登録・設定から情報を入力すれば新規アカウントが作成できます。ここからはアカウントを持っている前提で書いてます><それと、この解説がわかりづらかった場合やここに解説していない問題を解きたい、という場合はIntroduction内の多数の問題には公式で解説が付いているのでそちらを参照してください。

2.2　Hello World

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A

この問題、要は"Hello World"を出力する問題です。まず、解答例を書きます。(次の章以降も先に正解を書いてからそれを解説します)

1 #include<stdio.h>
2 int main(void){
3         printf("Hello World\n");
4         return 0;
5 }

1行目

#include<stdio.h>

これはおまじないだと思ってください。(これを詳しく解説するまでこの部誌では到達しません><)

2行目と4,5行目

int main(void){
...
        return 0;
}

C言語ではこの{}の中の...の部分が実行される、という認識で構いません。

そして3行目

printf("Hello World\n");

この命令は""で囲まれた文章を表示するものです。今回のプログラムだと、Hello Worldと出力しろ、という命令になります。最後の\nは改行を表します。この後ろ向きのスラッシュ、バックスラッシュは円￥マークと同じ方法で入力できます。(競技プログラミングでは大抵出力の最後に改行が求められたりするので、これを忘れないように癖づけることを推奨します。)

今回はプログラムを試しに実行するのにIdeoneを利用します。

http://ideone.com/

まず、上の大きい四角にプログラムを貼り付け、下の押すといろいろ出て来る中からpopularの中にあるCを選び、最後にRunボタンを押します。(アカウントは不要ですが、あるとプログラムが保存できて便利です)

すると、こんな感じの画面が出てきます。stdoutと書かれた場所にあるのが出力で、問題無く出力されているのが確認できました。

さて、解答が書き上がりましたが、書き上げただけでは勿論何も起こりません。解答を提出しなければなりません。

まず、この丸をつけた所をクリックします。

すると、このような画面が出てきます。今回は、言語にCを選択して、ソースコードの所に書いたプログラムを貼り付け、最後に矢印で指したところから提出します。

そこから現れる画面で自分の提出の所にこのようなチェックが入れば正解です。おめでとうございます!

2.3　X Cubic

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_B

この問題は、入力から数値を受け取り、その3乗を出力する問題です。

1 #include<stdio.h>
2 int main(void){
3         int x;
4         scanf("%d",&x);
5         printf("%d\n",x*x*x);
6         return 0;
7 }

1,2,6,7行目は先ほどと変わりません。

3行目

int x;

これはint型の変数xを宣言する、という命令です。はい、(プログラミング未経験であれば)何言ってるか分かりませんよね。

まず、変数、これは数字などを入れておける箱、と思ってください。(次のページの図も参考にしてください)int型、とは整数、厳密にいうと±21億くらいまでの整数を入れておける箱の種類のことです。つまり、xって名前の整数を入れておく箱を用意するよ～、という命令になります。ちなみに(とは言ったもののここはとても重要)このxに何らかの数値を入れておきたい場合は、

int x = 5;

や

int x;
x = 5;

などとするとxに5が入った状態になります。このように、x = y;と書くと変数xに数値yまたは変数yの値が入った状態になり、これを代入と呼びます。

4行目

scanf("%d",&x);

()の中身の左側、%dはint型、つまり整数の箱1つを表し、右側、&xは箱xのある場所を表します。&を忘れないようにしましょう(厳密にはポインタというのですが、今回は簡単のため詳しい説明はしません><)このscanfという命令にこの情報を教えることで、この命令は箱xに、入力から整数1つを受け取れ、というものになります。

5行目

printf("%d\n",x*x*x);

勘の良い方ならお気づきだと思いますが、さっきのHello Worldの時に使った命令の進化形です。()の中身の左側、%dはint型、つまり整数の箱1つを表しその後の\nは改行です。右側x*x*xはxを3つ掛けたもの、つまりxの3乗です。

ちなみに、

a+bでaとbの和
a-bでaからbを引いた差
a*bでaにbを掛けた積
a/bでaをbで割った商
a%bでaをbで割った余り

を表します。計算の順序は3+2*4なら2*4が優先されて11になります。

このprintfという命令で、箱xに入っている数値のの3乗を出力して最後に改行せよ、という意味になります。出力したからと言ってxの中身が無くなってしまう訳ではありません。

先ほどのIdeoneでプログラムに入力を渡したい場合は、stdinの枠内に書き込みます。今回は"2"と書き込んで実行してみます。

無事に2の3乗、8が出力されていることが確認できたので先ほどのように提出します。

2.4　Rectangle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_C

この問題は、縦a(cm)横b(cm)の長方形の面積と周の長さを求める問題です。面積はa*b、周の長さは2*(a+b)で求められます。それさえ分かれば殆ど先ほどと同じコードで正解できます。

1 #include <stdio.h>
2 int main(void){
3         int a,b;
4         scanf("%d%d",&a,&b);
5         printf("%d %d\n",a*b,2*(a+b));
6         return 0;
7 }

3行目

int a,b;

,で区切って書くと複数の変数を同時に宣言することができます。

4行目

scanf("%d%d",&a,&b);

入力が空白区切りで与えられるので、このように書くことでデータを2つ受け取ることができます。

5行目

printf("%d %d\n",a*b,2*(a+b));

2つの%dを空白で区切ると空白区切りの出力ができます。出力させたいものは,区切りで書きます。他にも"[%d]"と書くとと数値を[]で囲んだり"a:%d"と書くとa:12345のように表示させたりできます。(ここからは実行は省略します><)

復習問題 Watch

ここまでの内容で解ける問題です。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_D

是非自力で解いてみてください(ここでは解答のみを挙げますが解説は公式にあります)

 1 #include <stdio.h>
 2 int main(void){
 3         int h,m,s;
 4         scanf("%d",&s);
 5         m = s/60;
 6         s = s%60;
 7         h = m/60;
 8         m = m%60;
 9         printf("%d:%d:%d\n",h,m,s);
10         return 0;
11 }

2.5　Small, Large, or Equal

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_A

2数の大小関係を求める問題です。

1 #include <stdio.h>
2 int main(void){
3         int a,b;
4         scanf("%d%d",&a,&b);
5         if(a < b){printf("a < b\n");}
6         else if(a > b){printf("a > b\n");}
7         else{printf("a == b\n",a,b);}
8         return 0;
9 }

5行目

if(a < b){printf("a < b\n");}

if(~){...}は、()の中の条件が正しければ{}の中を実行する文です。これをif文と呼びます。

a < b ならbがaより大きい
a <= b ならbがa以下
a == b ならaとbが等しい
a != b ならaとbが等しくない

時に{}の中が実行されます。

ちなみに、

a < b && b < c ならa < b かつ b < c
a < b || a < cならa < b または a < c

というように、&&で「かつ」、||で「または」を表すことが出来ます。

6行目

else if(a > b){printf("a > b\n");}

elseが付いている部分は、先ほどの条件を満たさなかった場合に実行される部分です。今回はa >= bの場合です。そのあとに先ほどと同じ、条件がa > bになった文が書かれており、それを満たすと{}の中が実行されます。

7行目

else{printf("a == b\n",a,b);}

またしても条件を満たさなかった場合、つまりa == bの場合、この{}の中が実行されます。

復習問題 Range

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_2_B

a < b < cかどうか判定する問題です。

1 #include <stdio.h>
2 int main(void){
3         int a,b,c;
4         scanf("%d%d%d",&a,&b,&c);
5         if(a < b && b < c){printf("Yes\n");}else{printf("No\n");}
6         return 0;
7 }

2.6　Print Many Hello World

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_A

"Hello World"を1000回出力する問題です。

1 #include <stdio.h>
2 int main(void){
3         int i;
4         for(i = 1;i <= 1000;i++){
5                 printf("Hello World\n");
6         }
7         return 0;
8 }

お察しの通り、1章のプログラムを少し書き換えただけで正解できます。

4行目、6行目

for(i = 1;i <= 1000;i++){
...
}

for(~){…}、これをfor文と呼びます。今回の場合は、iを1から1000まで、iを1ずつ加えながら{}の中身を実行という意味になります。

具体的なイメージとしては

printf("Hello World\n");//i == 1
printf("Hello World\n");//i == 2
printf("Hello World\n");//i == 3
...
printf("Hello World\n");//i == 1000

といった感じです。i++はiに1加える、i--ならiから1引くという意味になります。

2.7　Print Test Cases

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_3_B

いくつか分からない入力を最後まで受け取って形式を変換する問題です。入力の終端が0で表されます。

1 #include <stdio.h>
2 int main(void){
3         int x,i=1;
4         while(scanf("%d",&x) , x != 0){
5                 printf("Case %d: %d\n",i,x);
6                 i++;
7         }
8         return 0;
9 }

4行目、7行目の

while(scanf("%d",&x) , x != 0){
        ...
}

while(~){...}をwhile文と言います。()の中の条件を満たしている間{}の中を実行し続けます。今回は、xが0でない間入力からxを受け取り続ける、という意味になります。入力が1234560なら、

(x != 0なので)"Case 1: 123\n"と出力
(x != 0なので)"Case 2: 45\n"と出力
(x != 0なので)"Case 3: 6\n"と出力
(x != 0ではなくなったので終了)

というような感じで実行されます。

2.8　Reversing Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_6_A

与えられる数値を逆順に出力します。

1 #include <stdio.h>
2 int main(void){
3         int a[128],n,i;
4         scanf("%d",&n);
5         for(i = 1;i <= n;i++){scanf("%d",&a[i]);}
6         for(i = n;i >= 1;i--){if(i != n){printf(" ");}printf("%d",a[i]);}
7         printf("\n");
8         return 0;
9 }

4行目

int a[128]...

また見慣れないものが出てきましたね。これは配列と言って、変数の箱をいくつか並べたものをイメージすると分かりやすいです。今回は[128]なので箱128個、0番から始まって127番まで用意されます。

6行目

for(i = 1;i <= n;i++){scanf("%d",&a[i]);}

で1番からn番の箱に入力から数値を受け取り、

for(i = n;i >= 1;i--){if(i != n){printf(" ");}printf("%d",a[i]);}

でn番から1番の箱の順に読み込んで出力します。この問題は空白区切りで出力する問題ですが、for文{}内のif文で出力の最初以外に空白を出力して入力が区切られるようにしています。(無理矢理1行に収めたのは許してください><)

2.9　QQ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0000&lang=jp

九九を出力する問題です。

 1 #include <stdio.h>
 2 int main(void){
 3         int i,j;
 4         for(i = 1;i <= 9;i++){
 5                 for(j = 1;j <= 9;j++){
 6                         printf("%dx%d=%d\n",i,j,i*j);
 7                 }
 8         }
 9         return 0;
10 }

4~8行目、for文の中にfor文が書かれています。

1x1=1 (i = 1,j = 1)
1x2=2 (i = 1,j = 2)

…

1x9=9 (i = 1,j = 9)
2x1=2 (i = 2,j = 1)

…

9x9=81 (i = 9,j = 9)

という風に実行されます。

for文の中にfor文、while文の中にwhile文、for文の中にwhile文、while文の中にfor文…というような書き方もできます。

ここまではAizu Online Judgeの問題について解説しました。他にも様々なレベルの問題があり初心者でも十分楽しめるので是非いろいろ解いてみてください!

2.10　AtCoderに挑戦してみよう!

ここからはAtCoderという日本の競技プログラミングのサイトを紹介します。

https://atcoder.jp/

毎週土曜日の21時に大抵何らかのコンテストが行われます。コンテストには、コンテストのページから「~に参加する」ボタンを押すと参加できます。

せっかくなので、practiceコンテストの問題を1問解いてみましょう。

http://practice.contest.atcoder.jp/tasks/practice_1

整数a,b,cと文字列s(文字の並び)が与えられるので、a+b+cとsを1行に出力する問題です。

1 #include <stdio.h>
2 int main(void){
3         int a,b,c;
4         char s[128];
5         scanf("%d%d%d",&a,&b,&c);
6         scanf("%s",s);
7         printf("%d %s\n",a+b+c,s);
8         return 0;
9 }

4行目

char s[128];

charは文字を入れて置ける箱を表し、今回はその配列を用意します。

6行目

scanf("%s",s);

%sは文字列を表します。文字列を文字の配列sに受け取ります。今回は&は不要です。

具体的には受け取る文字列が"test"だとしたら、

sの0番の箱に't'
sの1番の箱に'e'
sの2番の箱に's'
sの3番の箱に't'
sの4番の箱には文字列の終わりを表す記号が入れられます。

8行目

printf("%d %s\n",a+b+c,s);

文字列も整数の時と同じように出力できます。

2.11　あとがき

今回は競技プログラミングの簡単な、プログラミングの基礎を扱う問題を紹介しましたが、少しは競技プログラミングに興味を持って頂けたでしょうか?今回紹介した問題はまだまだ第一歩に過ぎません。まだまだこの先には沢山の難しい、楽しい問題が待ち構えています。是非挑戦して頂けると競技プログラミングをやっている身としてありがたいです。それでは、また来年の部誌にご期待ください!

第2章 「競技プログラミング入門」 by 井上誠大 (73)

2.1 まえがき&競技プログラミングとは(小冊子の内容)

2.2 Hello World

2.3 X Cubic

2.4 Rectangle

復習問題 Watch

2.5 Small, Large, or Equal

復習問題 Range

2.6 Print Many Hello World

2.7 Print Test Cases

2.8 Reversing Numbers

2.9 QQ

2.10 AtCoderに挑戦してみよう!

2.11 あとがき