競技プログラミングのすすめ - 弥生開発者ブログ

はじめに

こんにちは。弥生のミズタカです。
この記事は、Misoca+弥生 Advent Calendar 2019の13日目の記事です。
私は競技プログラミングを少々かじっており、せっかくなので記事にしてみました。
競技プログラミングは特にプログラミング初心者におすすめだと思います。

競技プログラミングって？？

競技プログラミングとは、主にオンラインで開催されるプログラミングコンテストの一種です。
参加者全員に同じ問題が出題され、いかに「早く」「正確に」問題を解くコード（コンソール出力アプリ）を書き、多くの点を取得できるか競います。
コンテストを開催するサイトは多々ありますが、どこも問題の出題方式はほとんど変わりません。
問題は「問題文」「制約」「入力形式」「出力形式」「入出力例」で構成されています。

以下に、多くの人がプログラミングを勉強し始めに目にしたであろうフィボナッチ数列を例に、問題のイメージを作ってみました。

■問題
入力として整数a,bが与えられます。
フィボナッチ数列のn番目の項をFnとして、「Fa+Fb」の値を出力しなさい。

■制約
1 <= a < b <= 100

■入力形式
以下の形式で入力が与えられる。
a b

■出力
Fa+Fbを1行で出力し、末尾には改行を入れること。

■入出力例①
入力：2 4
出力：4

■入出力例②
入力：3 7
出力：15

競技プログラミングのポイント

競技プログラミングでは、いかに「早く」コードを書くかが一つのポイントですが、早く書き上げれば何でもいいというわけではありません。
そのコードの「実行時間」や「メモリの使用量」なども判断基準となり、効率的なコードでないと得点が取得できなかったり、減点の対象になってしまいます。

例えば、前述の問題を解くのに、以下のような再帰メソッドを用意したとします。
この再帰メソッドは、フィボナッチ数列の漸化式を単純に再現したものです。

// Fnを求める再帰メソッド
public int fibonacci(int n)
{
    if(n == 0)
    {
        return 0;
    }
    if(n == 1)
    {
        return 1;
    }

    return fibonacci(n-1) + fibonacci(n-2);
}

これは処理速度が遅くて有名な再帰メソッドですが、実際にコードを動かしてみると、a,bの数字が大きくなるほど計算が終わるまでに果てしない時間がかかってしまい、使い物になりません。
なぜかというとメソッドを実行する度に基底のF0までさかのぼって、Fnまでの項をすべて再計算しているから。一度求めた項の値を再利用せずに、何度も計算しなおすため非常に非効率です。
もしこれが本当の出題だったら、この回答で点数は取れません。

もっと処理速度を高速化して問題を解くためには、以下のようにメモ化再帰を利用するなどしてメソッドを用意する必要があります。

public int fibonacci(int n)
{
    // あらかじめarray[0]=0、array[1]=1、array[2]=null、… 、array[n] = nullの配列を作っておく
    // n番目の項を計算したら答えを配列に記録するようにし、2回目からは配列の値を直接返す
    if(array[n] != null)
    {
        return array[n];
    }
    
    array[n] = fibonacci(n-1) + fibonacci(n-2);
    return array[n];
}

上記は簡単な例ですが、競技プログラミングではこういった「ロジックを工夫して効率化する力」を求められます。
レベルの高い問題になるほど単純なコード化やバックトラック（総当たり）では点数が取得できなくなるので、アルゴリズムやデータ構造の組み立ての勉強になります。

競技プログラミングは初心者にもやさしい！

競技プログラミングは以下の点で始めるハードルが低いので、おすすめです。

●コンテストはオンライン開催
コンテストは各競技プログラミングのサイトにてオンラインで開催されるため、自宅からでも気軽に参加することができます。

●短時間で行うことができる
コンテストに参加する場合は決められた時間に1～3時間ほどかかりますが、過去の問題を1問ずつ解くこともできます。その場合は問題のレベルにもよりますが、10～20分といった短時間で解いたり、隙間時間で少しずつ進めることも可能です。問題の解答を提出すると瞬時にオンラインジャッジが行われ、結果がすぐにわかるのもうれしいところです。

●問題のレベルが幅広い
競技プログラミングで出題される問題レベルは幅広く、ちょっとやそっとじゃ解けない難問もありますが、逆に四則演算さえ分かれば解けるやさしい問題もあります。自分のレベルに合わせて問題を選ぶことができます。

●自分が得意なプログラミング言語で参加可能
問題を解くための言語は特定の言語に決まっておらず、各サイトやコンテストが定めた言語から好きなものを選んで参加できます。言語の例としてはJava、C++、C#、D、Ruby、Phython、COBOL、などです。最初から自分が慣れ親しんだ言語で参加できます。

●他の参加者の提出コードを確認できる
コンテスト終了後は他の参加者が提出したコードを見ることができます。他の人がどのように問題を解いているのか参考になりますし、自分のコードと比較してみると、自分の癖や好みが見えたりして面白いですよ。

いろんな言語で問題を解いてみよう！

個人的におすすめする競技プログラミングの使い方の1つは、新しいプログラミング言語を勉強する1つの方法として同じ問題を複数のプログラミング言語で解いてみることです。

まずはじめは自分が使い慣れた言語で解き、2回目以降は学習中の言語で解きます。
2回目以降はロジックの内容を理解した上での作業になるので、未習熟な言語でも構文に集中して比較的スムーズにコードを書けます。
過去に提出した解答は履歴として保存されるため、異なるプログラミング言語による同じ内容のコード同士を比較することも容易です。履歴にはコード長、実行時間、メモリ使用量などが保存されるため、そういった点でも簡単に言語間の違いを感じることができます。