競技プログラミングとは

出題されたお題をデータ構造とアルゴリズム（+数学 etc...）を駆使して解く競技です。

実際のコンテストでは制限時間内に難易度の違う問題が複数出題されるので、それらをいかに早く解くかを競います。

例えばこんな問題が出題されます。

自然数 n （1 <= n <= 1000）が与えられたとき、1からnまでの和を求める calcSum() を実装せよ

まず naive に brute force でこの問題のアルゴリズムを実装してみましょう。

brute force は、パスワードを一文字ずつ変えながらログインを試みる攻撃手法 brute force attack の名前などに使われており、「強引に何かを行う」といった意味をもつ単語です。

競技プログラミングにおいては、「総当りで計算する」といった意味合いがあります。

func calcSum(n int) int {
    rev := 0
    for i := 1; i <= n; i++ {
        rev += i
    }
    return rev
}

このとき、時間計算量は O(n) 、空間計算量は O(1) です。

時間計算量は、ざっくり言うと必要な手順の回数を指します。上記のアルゴリズムでは n 回ループが実行されるので、O（オーダー）記法で O(n) になります。

空間計算量は、ざっくり言うと必要なメモリの量を指します。上記のアルゴリズムでは、返り値の変数 rev 以外はメモリを使っていないとみなすと、O(1)（常に一定）と表せます。

この問題、時間計算量 O(1) で解くことができます。

問題は 1~n までの和を求めているので、初項 1、公差 1 の等差数列の和を求めればよいことになります。

初項 a、公差 d、項数 n、末項 l の等差数列における初項から第 n 項までの和 S は、以下の式で求められます。

S = n * (a + l) / 2 =  n / 2 * (2 * a + (n - 1) * d)

今回は a = 1, d = 1, n = n, l = n であるため、上記に代入すると

S = n / 2 * (2 * 1 + (n - 1) * 1) = n * (n + 1) / 2

この公式を利用することで空間計算量は O(1) 、今回のように n が大きくない（n <= 1000）場合は、時間計算量 O(1) で計算することができます。

func calcSum(n int) int {
    return n * (n + 1) / 2
}

競技プログラミングの楽しさ

上記の問題だけでは少し物足りなかったかもしれません。

もっと本格的な問題を考えてみましょう。

ローマ数字は I, V, X, L, C, D, M （それぞれ 1, 5, 10, 50, 100, 500, 1000）を組み合わせて数を表す
通常は左から右に向かって大きい数から順に表すが、以下のケースは例外となる

・I は V(5), X(10) の前に書くことで IV(4), IX(9) を表せる
・X は L(50), C(100) の前に書くことで XL(40), XC(90) を表せる
・C は D(500), M(1000) の前に書くことで CD(400), CM(900) を表せる

自然数 num (1 <= num <= 3999) が与えられたとき、そのローマ数字を文字列で返す convertToRoman() を実装せよ

私は最近この問題を解いたのですが、最初の回答が以下です（ワントゥスリィ！）

var m map[int]string = nil

func convertToRoman(num int) string {
    m = make(map[int]string, 0)
    m[1] = "I"
    m[2] = "II"
    m[3] = "III"
    m[4] = "IV"
    m[5] = "V"
    m[6] = "VI"
    m[7] = "VII"
    m[8] = "VIII"
    m[9] = "IX"
    m[10] = "X"
    m[20] = "XX"
    m[30] = "XXX"
    m[40] = "XL"
    m[50] = "L"
    m[60] = "LX"
    m[70] = "LXX"
    m[80] = "LXXX"
    m[90] = "XC"
    m[100] = "C"
    m[200] = "CC"
    m[300] = "CCC"
    m[400] = "CD"
    m[500] = "D"
    m[600] = "DC"
    m[700] = "DCC"
    m[800] = "DCCC"
    m[900] = "CM"
    m[1000] = "M"

    rev := ""
    for num >= 1000 {
        q := num / 1000
        num %= 1000
        rev += strings.Repeat(m[1000], q)
    }
    num, rev = calc(rev, num, 100)
    num, rev = calc(rev, num, 10)
    _, rev = calc(rev, num, 1)
    return rev
}

func calc(rev string, num, d int) (int, string) {
    q := num / d
    num %= d
    rev += m[q * d]
    return num, rev
}

ゴリ押し感満載で、前半のローマ数字を打ち間違えたらそれだけで不正解となりそうなコードですね。実装も大変だった記憶があります。

ただ、上記のコードでも正解として通過はしました。

後ほど比較するためにざっくりで時間計算量を出すと、

num を 1000 以下にするのに for で記載してますが、1000 で modulo を取っているのでループは1回しか回らず
strings.Repeat() は O(log2(q)) とすると

最終的には O(log2(q)) でしょうか。

このコードをより改善しようと試みて書いたのが次のコードです。

var m map[int]string = nil

func convertToRoman(num int) string {
    m = make(map[int]string, 0)
    m[1] = "I"
    m[5] = "V"
    m[10] = "X"
    m[50] = "L"
    m[100] = "C"
    m[500] = "D"
    m[1000] = "M"

    rev := ""
    for num >= 1000 {
        q := num / 1000
        num %= 1000
        rev += strings.Repeat(m[1000], q)
    }
    num, rev = calc(rev, num, 100)
    num, rev = calc(rev, num, 10)
    _, rev = calc(rev, num, 1)
    return rev
}

func calc(rev string, num, d int) (int, string) {
    q := num / d
    num %= d

    if q == 9 || q == 4 {
        rev += m[d] + m[(q+1) * d]
    } else if 6 <= q && q <= 8 { // 8,7,6
        rev += m[5 * d] + strings.Repeat(m[d], q % 5)
    } else if 2 <= q && q <= 3 { // 3,2
        rev += strings.Repeat(m[d], q)
    } else if q == 5 || q == 1 {
        rev += m[q * d]
    }

    return num, rev
}

より短い行数で書けましたが、桁に 6,7,8 が登場する場合は strings.Repeat() も呼ばれるため、時間計算量は先程のものから悪化してしまっています。

どうにかならないものかと、他の方が提出した回答を眺めていると、次のような考え方で実装されていて驚愕でした（別の言語だったため、Go で再実装しています）。

今回の問題の num は num <= 3999 の制約があります。つまり千の位はたかだか 3 までということです。そこから次のような考え方が生まれたのでしょう。

func convertToRoman(num int) string {
    M := []string{"", "M", "MM", "MMM"}
    C := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    X := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    I := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
    return M[num/1000] + C[(num%1000)/100] + X[(num%100)/10] + I[num%10]
}