たのしい競技プログラミング

こんにちは。今年9月にTeamSpiritにジョインした畠山です。
入社からちょうど３ヶ月が経ち、試用期間も終えたところで入社エントリでも書きましょうか......

と思っていましたが趣味の競技プログラミングの布教をします。

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

AtCoderやCodeforcesが主催するアルゴリズム系のプログラミングコンテストです。
各サイトでは定期的にコンテストが開催されています。コンテストでは毎回６問程度出題され、より早く与えられた仕様を満たすプログラムを正確に記述することを競います。

atcoder.jp

誰でも参加できるコンテスト！

とりあえず直近に開催されたAtCoder Beginner Contestの最初のA問題を見てみましょう。

AtCoder Beginner Contest 185 A - ABC Preparationより

問題

高橋くんは、プログラミングコンテストを何回か開くことにしました。
コンテストを1回開くには、100点問題、200点問題、300点問題、400点問題が1問ずつ必要です。
100,200,300,400点問題の案がそれぞれ $A_1$ , $A_2$ , $A_3$ , $A_4$ 個あるとき、コンテストを最大で何回開けるでしょうか？
なお、同じ問題案は1度しか使えません。

制約

・ $1 \leqq A_i \leqq 100 ( 1 \leqq i \leqq 4 )$
・入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。
$A_1$ $A_2$ $A_3$ $A_4$

どうでしょうか？解けそうな気がしませんか？
この問題は標準入力から受け取った4つの整数のうち最小のものを標準出力から出力するとで正解できます！

# 正解できるコード例 (python) 
print(min(map(int, input().split())))

このようにコンテストといっても最初の問題はプログラムを覚えたばかりの人でも楽しめるようになっているので、興味を持ったらとりあえずコンテストに参加してみましょう！

これ以降ののhow toは先人たちの知恵がたくさんあるので是非調べてみてください。特に@drkenさんのブログとQiitaは必見です！。

何が身につくの？

計算量の見積もりができるようになります！
競技プログラミングにおいて、計算量はとても重要な概念です。試しに少し難しい以下の問題を見てみましょう。

AtCoder Beginner Contest 085 C Otoshidamaより

問題

日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が $N$ 枚入っていて、合計が $Y$ 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約

・ $1 \leqq N \leqq 2000$
・ $1000 \leqq Y \leqq 2 * 10^7$
・ $N$ は整数である
・ $Y$ は1000の倍数である

入力

$N$ $Y$

出力

$N$ 枚のお札の合計金額が $Y$ 円となることがありえない場合は、-1 -1 -1 と出力せよ。
$N$ 枚のお札の合計金額が $Y$ 円となることがありうる場合は、そのような $N$ 枚のお札の組み合わせの一例を「10000 円札 $x$ 枚、5000 円札 $y$ 枚、1000 円札 $z$ 枚」として、 $x$ 、 $y$ 、 $z$ を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

この問題を簡単に言い換えると、「制約下で $10000x + 5000y + 1000z = Y$ かつ $x + y + z = N$ となるような $x$ , $y$ , $z$ の組み合わせが存在するならばどれか1つを出力せよ。」となります。
なんだか数学みたいな問題ですが、これは競技プログラミングなのでプログラムでシミュレーションする方法を考えます。

以下はC#で書いた回答コードの一部です。

for(int x = 0; x <= N; x++)
{
    for(int y = 0; y <= N - x; y++)
        {
            for(int z = 0; z <= N - x - y; z++)
            {
                if(10000 * x + 5000 * y + 1000 * z == Y)
                {
                    Console.WriteLine(x + " " + y +" " + z );
                    return;
                }
            }
        }
}

このコードは正確な答えを出力できますが、残念ながらコンテストで正解をもらうことは出来ません。改めて制約を見てみると $N$ は最大2000を取る可能性があるので、このコードの3重ループはおおよそ $2000 ^3 = 8*10^9$ 回実行されてしまい数秒かかってしまいます。(実際には枝刈りをしているのでこれより少ないですが、それでも $10^9$ 回を超えています。)
AtCoderのジャッジシステムはプログラムの実行時間が2秒を超えると不正解となるので、もうひと工夫しましょう。
よく考えると $x$ と $y$ が決まった時点で条件を満たす $z$ が確定するので、3つ目のループは必要ありません。

for(int x = 0; x <= N; x++)
{
    for(int y = 0; y <= N - x; y++)
        {
            var z = N - x - y;
            if(10000 * x + 5000 * y + 1000 * z == Y)
            {
                Console.WriteLine(x + " " + y +" " + z );
                return;
            }
        }
}

最初のアルゴリズムではNに注目すると $N^3$ のステップがかかっていましたが、修正後のアルゴリズムは $N^2$ のステップで実行することが出来ます。
このようなある値に対して実行時間がどれだけ大きくなるかを表し、アルゴリズムの性能を示すものが計算量という考えです。一般にランダウの記法を用いて $O(n^2)$ の用に書きます。

今回の例ではforループがたくさんネストしているので明らかに時間の掛かりそうな処理でした。ですが、見た目によらず計算量を把握すること重要です。例えばハッシュセットの検索(HashSet.Containts)は $O(1)$ ですが、リストからの検索(List.Containts)は $O(n)$ です。他にも配列のインデックスアクセス(list[i])は $O(1)$ ですが、連結リスト(linkedList[i])は $O(n)$ などがあります。

このように常に計算量を意識しながらアルゴリズムを組み立てていくので普段のプログラミングにおいても効率的なコードを書く意識がつくようになります！

競技プログラミングの面白さ

コンテストには上で説明したような簡単な問題から数人しか解けないような超難問まで様々な良問が毎週提供されています。もちろん、コンテスト中は答えを見ることができないので時間いっぱい考えます。これで解けたときはもちろん嬉しいのですが、時間内に解けなかったとしてもコンテスト直後に解説が見れるので、それを見て「なるほどそいういうことか〜」となる瞬間が気持ちいいです！
他にも、リアルタイムでコンテストに参加すると成績に応じたレーティングが付与されます。この数値の上下に一喜一憂しながらゲーム感覚で友人たちと競い合うことも出来ます。

ここまでで少しでも興味をもてた方はは是非コンテストへ参加してみてください！
次回のコンテストは12/19(土) 21:00 ~です！以下から参加登録をどうぞ！
atcoder.jp