競プロ - hiryuN’s blog

こんにちは hiryuN ないしはひりゅーです。

今回は競技プログラミングという今僕がハマっているオンラインゲームについて紹介して行きたいと思います。

現在日本において一番有名だと思う競技プログラミングサイトAtCoderのリンクを貼っておきます。この記事を見て興味を持ってくださった方はぜひ登録して競技プログラミングの世界に突入してみてはいかがでしょうか?

atcoder.jp

競技プログラミングとは

決められた条件のもとで与えられた問題、課題をプログラミングを用いて解決し、その過程や結果を競うものを競技プログラミングといいます。
様々なジャンルの出題がされますが、プログラミングや思考力、数学力、知識を活用します。

競技プログラミングとは？ - AtCoderInfo より抜粋

これはAtCoder 公式ページに書いてある競技プログラミングについての説明です。

抽象的でとっつきにくいかと思うので例題を挙げてみます

atcoder.jp

問題概要を説明しますと 6 桁の整数が与えられるのでその中に 1 が 1 つ、2 が 2 つ、3 が 3 つ含まれているかどうかを判定して「Yes」か「No」を出力せよという問題です。

要するに「122333」や「321233」みたいなのには「Yes」を「111111」や「123456」みたいなのには「No」を出力すれば正解となります。

この問題に対するアプローチはいくつかあり一番すなおな方法は純粋に"1"、"2"、"3"の数を数えていく方法だと思います。プログラミングに触れたことのある人であればご存じかと思いますが多くの言語には for 文と呼ばれる繰り返し処理を行える機能がありそれを用いてこの問題を解くことができます。

他にもテクニカルな方法として数字の列をソートしてみるという方法があります。Yesを出力するような整数は各桁の数字が小さい順に並び替えたとき全て「122333」という数字となるので一致するかの判定を行えばそれで終了となります。

Pythonで書いてみたものがこちらになります

s = input()
if "".join(sorted(s)) == "122333":
    print("Yes")
else:
    print("No")

これをAtCoderの提出ページにコピペして提出することでこの問題に正解することができます。

画面下部の「AC」という文字が正解している証拠となります。

単純に答えの出力を間違えた場合「WA」にコードを実行した際にエラーが出た場合は「RE」や「CE」と出てきます

そして競技プログラミングでは正しい出力を出す以外にも満たすべき要件があり、最も重要なことの一つに実行時間制限というものがあります。これは提出したプログラムが実行に使って良い時間の制限であり大体 2秒だったり 3秒だったりします。これを超過すると「TLE」と出てきてしまい、これもまた不正解として扱われてしまいます。

では次にこの実行時間制限について詳しく書いていけたらなと思います。

実行時間とアルゴリズムについて

実行時間について説明するためにまた別の問題を挙げたいと思います。（これはさっきの問題よりも難しいと思います)

atcoder.jp

問題概要を説明しますと正整数 $N$ が与えられます。( $N$ の最大値は 200,000 )

このNに対して $a \times b + c \times d = N$ となるような $(a,b,c,d)$ の組み合わせが何種類あるかを答えてくださいという問題です。（ $a,b,c,d$ は全て正整数)

例えば $N = 5$ のとき $(a,b,c,d) = (1,1,2,2)$ は $1 \times 1 + 2 \times 2 = 5$ となるため条件を満たします。他にも 13 種類の組み合わせがあり、答えるべき数字は 14 となります。

方針A

さて、いきなりこんな問題を出されたとて何から始めれば良いのやらといった感じの方も多いことでしょう。

右辺の1 変数の情報から左辺の4 変数の情報を得ようとしてるので難しいのは当たり前です。

逆に左辺の情報から右辺について考えるのは簡単でただ単に四則演算の計算を行えば良いだけです。

そこで $a,b,c,d$ に対して色々な値を当てはめてみたときに $N$ の値がいくつになるのかを考えてその値が正しい値かを判断して、正しい値となるようなケースが何通りあるかを調べてみようという方針が立ちます。

この方法で正しい答えを得るには $N$ の値が正しい値になる可能性のある $a,b,c,d$ の組み合わせ全てについて考える必要があります。

少し考えると $a,b,c,d$ のうちどれか一つでも $N$ を超えた場合には等式が成り立たないことがわかりますので、 $a,b,c,d$ それぞれについて $1$ 〜 $N$ までの数字を全て確かめていくという方法が思い付きます。

これを先ほども紹介した for 文を使って書いてみることを考えてみましょう。

N=int(input())
count = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            for d in range(1, N+1):
                if a*b + c*d == N:
                    count += 1
print(count)

さてこのプログラムは「AC」を勝ち取ることができるでしょうか？

試してみましょう

結果はTLEとなってしまいました。何がいけなかったのかプログラムの中身について触れていきましょう

方針A のプログラムでは $1$ 〜 $N$ までの数字を試すという作業を 4 重に行っています。これは $N \times 4$ 回の作業を行っているわけではなく九九の表のように 2 重の処理を行うだけでも $N × N$ 回分の作業量となり、4 重で行うことでなんと $N \times N \times N \times N$ 回もの作業量となってしまいます。

これに冒頭に挙げました $N$ の最大値である 200,000 を入れて計算してみますと脅威の

1,600,000,000,000,000,000,000( $=1.6 \times 10^{21}$ )回*1となります。

電子計算機というものは人間と比べて計算がはるかに得意で、言語にもよりますが 1秒間に $10^8$ 回程度の処理をすることができます。しかしそんな電子計算機にも限界というものがあり今回のプログラムでは 1秒間に $10^8$ 回もの処理を行えたとしても単純計算で $1.6 \times 10^{13}$ 秒もの時間がかかります

これは約50万年*2であり北京原人が現代人にまで進化できるほどの途方もない時間です。

そんな時間がかかってしまうプログラムは実用的なプログラムであるとは言えないですね

AtCoder内で「AC」を勝ち取るためにはこの問題の場合 2秒以内にプログラムが終了しなければいけないので逆算すると大体 $2 \times 10^8$ 工程以下で答えを出さなければいけない訳です。

ここで競技者たちの工夫が必要になってくるわけです。

例えば今は $a,b,c,d$ 全てについて毎回調べていますが本当に全て調べる必要があるのでしょうか？これについて考えていきます。

方針B

実は $a,b,c$ について値が決まった時 $a \times b + c \times d = N$ という式を満たすと仮定すると式変形を行うと $d = \dfrac{N-a \times b} {c}$ となり、残りの $d$ の値も定まってしまうことがわかります。

この $d$ の値が正整数という条件を満たしているなら count を +1 するといった方法をとるとさっきは $a,b,c,d$ の4つの変数に対して行っていた繰り返しを $a,b,c$ の3つの変数に対して行うだけで良くなり、作業量が $N \times N \times N$ 回まで減ります。 $N$ に 200,000 を代入すると

8,000,000,000,000,000( $=8 \times 10^{15}$ )回となります。

#これは p/q が正整数になるかを判定する関数
def Is_PositivInt(p, q):
    if p % q == 0:
        if p // q > 0:
            return True
        else:
            return False
    else:        
        return False

N = int(input())
count = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            if Is_PositivInt(N - (a*b), c):
                count += 1
print(count)

これを実行するには約460日かかります。北京原人は北京原人のままですがさすがに誕生日を 1, 2 回迎えられるような時間をこのような単純な問題に費やすのはいかがなものかと思います。

方針C

そこで更なる高速化ができないかを考えるわけです。

そのための下準備として新たに変数を 2 つ増やし、

$a \times b = x$ , $c \times d = y$ , $x + y = N$

とします。正整数同士を掛け合わせたものなので $x$ と $y$ も正整数となります。

考える変数を増やしてどうするんだと思われるかもしれませんが容赦なく増やします。考えるべき式も 3 つに増えました。

1 つずつ順番に見ていきたいと思います。

まずは $x + y = N$

新たに増やした変数が 2 つも入っており非常にわかりにくそうですが一旦 $x$ や $y$ が新たに増やした変数ということを忘れて単純に正整数を入れて等式が成立する条件を考えてみるとただの足し算であるこの式は単純明快で

$(x,y) = (1,N-1),(2,N-2),...,(N-1,1)$

の $N - 1$ 個の正解の組み合わせがあります。

もちろんこの問題の正解として $N - 1$ を出力すれば良いわけではないです。

例えば $x = 4$ の場合 $(a,b) = (1,4),(2,2),(4,1)$ の3種類の組み合わせが考えられ $y$ の値も $x$ と同様に $y = 4$ であれば $(c,d)$ の値に関しても 3種類の組み合わせが考えられます。よってこの場合は $(a,b,c,d)$ の値の組み合わせは 3通り $\times$ 3通りで 9 通り考えられることになります。

このようにある $x$ についてその値のとき条件式を満たす $(a,b)$ の値の組が何通りあるかと、ある $y$ についてそれを満たす $(c,d)$ の値の組が何通りあるかが分かればある $(x,y)$ を満たす $(a,b,c,d)$ の値の組が全体で何通りあるかがわかります。これを $(x,y) = (1,N-1),(2,N-2),...,(N-1,1)$ の $N - 1$ 個の組み合わせについて全部考えてそれを足し合わせてやれば答えが出てきます。

例えば $N = 5$ のときであれば考えるべき $(x,y)$ の組は $(1,4),(2,3),(3,2),(4,1)$ の 4つであり、 $x,y$ がそれぞれの値のときありうる値の組が何通りあるかを調べてみると答えが

$1 \times 3 + 2 \times 2 + 2 \times 2 + 3 \times 1$

の式で求められることがわかります。当然計算した答えは 14 です。

この部分は $N-1$ 回の掛け算を行った後 $N-1$ 個の数字の合計を求めるので最低でも合計で $2 \times N - 3$ 回の演算が必要です。これは最大で399,997回となります。

X= #ここに x を固定したときの(a, b)の組の数を記録する配列を作る
Y= #ここに y を固定したときの(c, d)の組の数を記録する配列を作る
count = 0
for i in range(1, N):
    count += X[i] * Y[N-i]
print(count)

次に $a × b = x$ の式について考えます。

まず $x$ については前述の通り $1$ 〜 $N - 1$ 　の $N-1$ 個の値を代入してみたものそれぞれについて考え、その値を代入したときの式を成り立たせる $(a,b)$ の組み合わせを考えます。

これには前述の $(a,b,c)$ が定まれば $d$ が自動で定まるのと同じ考え方が適用でき、 $a$ の値を定めると $b = \frac {x} {a}$ と式変形でき $b$ の値が自動で定まります。

$a$ の値については $x$ の値を超えると解がなくなるので $1$ ~ $x$ の範囲で考えてあげればOKです

ですので各 $x$ について調べなければいけない $a$ の種類数は $x$ 個であり、それらを合計すると

$1 + 2 + 3 + ... + (N - 1) = \displaystyle \sum_{i=1}^{N-1} i = \frac {(N-1) \times (N)}{2}$

であり、最大で 19,999,900,000( $\simeq 2.0 \times 10^{10}$ ) 回です。

X = [None] + [0] * (N-1)
for x in range(1, N):
    for a in range(1, x+1):
        if Is_PositivInt(x, a):#b = x/a が正整数かどうかの判定
            X[x] += 1

最後に $c × d = y$ の式についてですが、　見ての通り $a × b = x$ の式と同じ形式であり、 $a × b = x$ の式について考えたときに得た結果をそのまま流用することができます。操作回数は 1 です。

Y = X

最後に全ての工程で必要な操作の回数を足し合わせてみると

20,000,299,998( $\simeq 2.0 \times 10^{10}$ )回となります。

#これは p/q が正整数になるかを判定する関数
def Is_PositivInt(p, q):
    if p % q == 0:
        if p // q > 0:
            return True
        else:
            return False
    else:
       return False

N = int(input())

X = [None] + [0] * (N-1)
for x in range(1, N):
    for a in range(1, x+1):
        if Is_PositivInt(x, a):#b = x/a が正整数かどうかの判定
            X[x] += 1
            
Y = X

count = 0
for i in range(1, N):
    count += X[i] * Y[N-i]
print(count)

これを実行するのにかかる時間は約 200 秒です。カップラーメンが作れるくらいの時間

今まで出てきた数字から考えるとお手頃で現実的なかわいい数字ですが、今回の制限時間である 2 秒には遠く及びません。

最後にもう少しだけ作業を効率化する必要があります。

方針D

ここで注目するのは $a × b = x$ の式について考えた際の「各 $x$ について調べなければいけない $a$ の種類数は $x$ 個であり」という部分です。

具体的に $x = 24$ としてみます

このとき $(a,b)$ としてあり得る組み合わせは $(1,24),(2,12),(3,8),(4,6),(6,4),(8,3),(12,2),(24,1)$ の 8 個です。

ここで注目して欲しいのは $(3,8)$ と $(8,3)$ の組のようにある組に対してそれの $a$ と $b$ の値を交換したものもまたあり得る組となるという所です。

これは掛け算が可換*3であることから正しいとわかります。

このことから $a \leq b$ となるような組についてだけ考えて $a$ < $b$ *4となる組の数だけ 2 倍すると正しい答えとなります。

例えば $x = 24$ の例であれば $a$ < $b$ となる組が $(1,24),(2,12),(3,8),(4,6)$ の部分まで数えると 4 個なのでこの部分だけでこれを 2 倍した 8 個が正しい答えとなることがわかります。

$a \leq b$ となる組み合わせを全て考えるために $a$ をどの範囲にして調べる必要があるかについてですが $a$ の値が $\sqrt{x}$ を超えると $a \leq b$ より

$x = \sqrt{x} \times \sqrt{x}$ < $a \times a \leq a \times b$

となって $x$ と $a \times b$ の間に等号が成立しなくなってしまうことがわかります。

よって各 $x$ に対して調べなければいけない $a$ の範囲は $1$ 〜 $\lfloor \sqrt{x} \rfloor$ ( $\sqrt{x}$ を超えない最大の整数)までであり、その個数の総和は $\displaystyle \sum_{i=1}^{N-1} \lfloor \sqrt{i} \rfloor$ となります。

これに $N$ の最大値を代入すると

59,528,927( $\simeq 6 \times 10^7$ ) となります。

X = [None] + [0] * (N-1)
for x in range(1, N):
    for a in range(1, x+1):
        if a * a > x:
            break
        elif a * a == x:
            X[x] += 1
        else:
            if Is_PositivInt(x, a):
                X[x] += 2

これに $x+y=N$ の式について考える工程で必要な操作回数399,997を足すと

59,928,924( $\simeq 6 \times 10^7$ )

となります

def Is_PositivInt(p, q):
    if p % q == 0:
        if p // q > 0:
            return True
        else:
            return False
    else:
       return False

N = int(input())

X = [None] + [0] * (N-1)
for x in range(1, N):
    for a in range(1, x+1):
        if a * a > x:
            break
        elif a * a == x:
            X[x] += 1
        else:
            if Is_PositivInt(x, a):
                X[x] += 2
            
Y = X

count = 0
for i in range(1, N):
    count += X[i] * Y[N-i]
print(count)

これを実行するのにかかる時間はだいたい 0.6 秒程度であり、これにて目標であった 2 秒を切ることができめでたくAC を勝ち取りました。やったね

このように計算の仕方を工夫してただ何も考えずにプログラムを作ったときよりも格段に速く動作するプログラムを作る過程こそが競技プログラミングの醍醐味です。少しでも競技プログラミングの楽しさが伝わっていたらいいなと思っています。

少しでも興味がある方はぜひ競技プログラミングを始めてみてください！

*1:どこまでを1つの処理とみなすかなどによってこの回数は変化する上、操作の種類が複数種ある場合操作ごとに実行時間にバラつきがあるため操作回数と実行時間は完全に比例するわけではないため1の位まで操作回数を出すことにあまり意味は無く指数表記のみで充分なのですが見たときのインパクトのためだけにあえてこのような表記をしていますし、これ以降もします。

*2:この実行時間はあくまで目安であってプログラミング言語の種類やマシンスペックによって変動します。これ以降に出てくる実行時間についても同じ

*3: a × b = b × a になるってこと

*4:a = b の場合 a と b の値を入れ替えても元の組と変わらないためそれを省くために = を除いている