gotutiyan’s blog

競技プログラミングをやったりopenframeworksでお絵かきをしたりしています。

競技プログラミング入門(仮

はじめに
言語は基本的にC++を使っています。プログラムの簡単な説明もある程度行いながら進めていきます。C言語などの予備知識があると読みやすいかもしれません。

競技プログラミングとは
競技プログラミング(以下競プロ)とは、プログラミングを用いて様々な問題をできるだけ速く、正確に解くことを目指すものです。後に列挙するようなサイトで、日々プログラミングコンテストが開かれています。このコンテストは2時間程度で開催され、解けた問題の数や解けた時間で順位がつき、それによりレートの変動があります。レートを見ることで、自分がどれくらいの力を持っているかを知ることができ、以降の実力の向上に役立ちます。

プログラミングコンテストが開かれているサイト
Atcoder(日本語、週1,2回程度)
・yukicoder(日本語、週1程度)
・AOJ(日本語、コンテストはごく稀で、問題集としての利用が多い)
Codeforces(英語、週3程度)
・CSAcademy(英語、週1程度)
Topcoder(英語、週2程度)
Atcoderとyukicoderは問題の解説が充実しているのでおすすめです。他のサイトの問題も、有志が日本語解説を書いてくれていることがあります。

競プロをやってみよう
以下では「Atcoder」のサイトで感触を掴んでいきましょう。Atcoderでは問題ごとに問題の難易度を示す配点があり、100点から始まり200,300.... のように100点区切りで用意されています。まずはAtcoderに登録をして、一番簡単な部類である100点問題をやってみます。

100点レベル
一番簡単な100点レベルでは、以下のことができると大体解けます。
・整数、文字、文字列型の変数を宣言する
・宣言した変数に値を代入する
・値の演算(足す、引く、掛ける、割る、余りを求める)ができる
・標準入出力をする
・if文が書ける

では、実際に問題を5問ほど解いてみましょう。
以下のリンクの問題をやってみます。
A - 積雪深差
2つの値が与えられるので、2つの値の差を求める問題です。
使う知識は整数型のint型と、引き算、cin>>による入力、cout<<による値の出力です。
答えのコードは以下の通りです。

#include <iostream>
using namespace std;

int main() {
    int h1,h2;  //整数型の変数を2つ宣言
    cin>>h1>>h2;  //入力を受け取る
    cout<<h1-h2<<endl;  //引いた値を出力
    
    return 0;
}

それぞれの問題には、解答のコードが正しいかどうかを判定するための「テストケース」が存在し、「入力例」と「出力例」の答え合せのデータがあらかじめ用意されています。上のコードでは、[cin>>]で入力を受け取った後、処理をしてから[cout<<]で自分の答えはこうなりました、と言うことを示し、これがテストケースの出力と合っていれば晴れて正解となります。



次の問題に行きましょう。
A - Between Two Integers
3つの整数を読み込んで、CがA以上B以下であるかを判定する問題です。
ここではint型、ifを使った条件分岐を扱います。
答えのコードは以下の通りです。

#include <iostream>
using namespace std;

int main() {
    int a,b,c;  //int型変数を3つ用意
    cin>>a>>b>>c;  //入力を受け取る
    if(a<=c&&c<=b)cout<<"Yes"<<endl;  //条件を満たせばYes
    else cout<<"No"<<endl;  //満たさなかったらNo
    
    return 0;
}

先ほどの問題では、出力するものが「数字」でした。しかし今度はYes,Noという文字列を出力しなければなりません。
この場合も、同じように[cout<<]で出力することができます。一つ注意するのは、文字列はダブルクオーテーション[" "]で囲まなければならないことです。

int Yes=5;
cout<<Yes<<endl;
cout<<"Yes"<<endl;

とした時、出力は順に5、Yesとなることから、ダブルクオーテーションは必須です。

さらに、if文も登場しました。数学のようにa<=c<=bとはできないので、2つに分けて、&&を使って「両方を満たす」という書き方にします。{以上, 以下, 未満, より大きい}などの言葉に十分注意します。条件を満たす時、"Yes"、そうでなければ"No"を出力します。



次です。
A - Addition and Subtraction Easy
2つの整数と+,-のどちらかの記号が与えられるので、+なら足したものを、-なら引いたものを出力する問題です。
ここでは文字を扱うためのchar型を使います。
答えのコードは以下の通りです。

#include <iostream>
using namespace std;

int main() {
    int a,b;  //2つの整数型変数を用意
    char op;  //char型変数も用意
    cin>>a>>op>>b;  //入力の順番を守って入力を受け取る
    if(op=='+')cout<<a+b<<endl;  //受け取った文字列が'+'なら足して出力
    else cout<<a-b<<endl;  //そうでなければ引いて出力
    
    return 0;
}

受け取った文字が'+'なら足して、'-'なら引いて出力します。'+'でない時点で'-'であることがわかるので、わざわざif(op=='-')と書く必要はなく、elseだけで事足ります。

一般に、「文字」は1文字だけを指していて、シングルクオーテーション[' ']で囲みます。また「文字列」は2文字以上のものを指していて、ダブルクオーテーション[" "]で囲みます。

'a'  'g'  '1'  //文字
"ie" "aiueo" "3667"  //文字列



次です。
A - Placing Marbles
この問題では3つの数字がくっついたものを扱います。ここでは「文字列」を使えば簡単です。
この解法では文字列を扱うstring型を使います。これを使うには、#include < string>が先頭に必須です。
int型に整数を代入できるように、string型には文字列を代入できます。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;  //string型変数を用意
    int ans=0;  //解答用の数えるための変数を用意、0で初期化
    cin>>s;
    //1ならansが増えていく
    if(s[0]=='1')ans++;
    if(s[1]=='1')ans++;
    if(s[2]=='1')ans++;
    cout<<ans<<endl;
    
    return 0;
}

for文はまだ使わずに解いています。(A問題はループを使わないつもりで作られているため、一応です。)
入力をstring型変数に代入します。代入された文字列は配列になっていて、s[0],s[1]...のように1文字ずつ見ることができます。1文字ずつ見たとき、これは「文字列」ではなく「文字」になるので、シングルクオーテーション[' ']で囲みます。3つの文字を見ていき、それが1であればans++;で1増やします。3つとも調べ終わった後のansの値が、そのまま答えになります。


最後です。
A - ABCxxx
整数が入力されるので、それをABCの後に続けて出力する問題です。
今まで、cout<< x<< endl;のようにendl;を当たり前のようにつけてきましたが、前述した通り、これは改行を表します。endl;をつけなければ改行されませんし、出力したものはひたすら横に連なっていきます。
答えのコードは以下の通りです。

#include <iostream>
using namespace std;

int main() {
    int x;
    cin>>x;
    cout<<"ABC";  //まだ横に繋げたいのでendl;は書かない
    cout<<x<<endl;
    return 0;
}

さらに、問題文では数字との表記がありますが、string型を使って文字列として受け取ることもできます。
この問題でやることは変わりませんが、問題によって数字をint型で受け取るか、string型で受け取るかで、解法の易しさが変わってくることがあります。
以下はstring型での解法です。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin>>s;
    cout<<"ABC";
    cout<<s<<endl;
    return 0;
}

この5問で、整数、文字、文字列を扱うことができるようになれば良いですね。正直これだけで、100点レベルの問題は大体解くことができます。