こんにちは 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 の提出ページにコピペして提出することでこの問題に正解することができます。
AtCoder の提出確認画面
画面下部の「AC」という文字が正解している証拠となります。
単純に答えの出力を間違えた場合「WA」にコードを実行した際にエラーが出た場合は「RE」や「CE」と出てきます
そして競技プログラミング では正しい出力を出す以外にも満たすべき要件があり、最も重要なことの一つに実行時間制限というものがあります。これは提出したプログラムが実行に使って良い時間の制限であり大体 2秒 だったり 3秒 だったりします。これを超過すると「TLE」と出てきてしまい、これもまた不正解として扱われてしまいます。
では次にこの実行時間制限について詳しく書いていけたらなと思います。
実行時間について説明するためにまた別の問題を挙げたいと思います。（これはさっきの問題よりも難しいと思います)
atcoder.jp
問題概要を説明しますと正整数
このNに対して
例えば
具体的な14種類の答え
方針A
さて、いきなりこんな問題を出されたとて何から始めれば良いのやらといった感じの方も多いことでしょう。
右辺の1 変数の情報から 左辺の4 変数の情報を得ようとしてるので難しいのは当たり前です。
逆に 左辺の情報から右辺について考えるのは簡単でただ単に四則演算の計算を行えば良いだけです。
そこで
この方法で正しい答えを得るには
少し考えると
これを先ほども紹介した 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,600,000,000,000,000,000,000(*1 となります。
電子計算機というものは人間と比べて計算がはるかに得意で、言語にもよりますが 1秒間に
これは約50万年*2 であり北京原人 が現代人にまで進化できるほどの途方もない時間です。
そんな時間がかかってしまうプログラムは実用的なプログラムであるとは言えないですね
AtCoder 内で「AC」を勝ち取るためにはこの問題の場合 2秒 以内にプログラムが終了しなければいけないので逆算すると 大体
ここで競技者たちの工夫が必要になってくるわけです。
例えば今は
方針B
実は
この
8,000,000,000,000,000(
#これは 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 つ増やし、
とします。正整数同士を掛け合わせたものなので
考える変数を増やしてどうするんだと思われるかもしれませんが容赦なく増やします。考えるべき式も 3 つに増えました。
1 つずつ順番に見ていきたいと思います。
まずは
新たに増やした変数が 2 つも入っており非常にわかりにくそうですが一旦
の
もちろんこの問題の正解として
例えば
このように ある
例えば
の式で求められることがわかります。当然計算した答えは 14 です。
この部分は
X= #ここに x を固定したときの(a, b)の組の数を記録する配列を作る
Y= #ここに y を固定したときの(c, d)の組の数を記録する配列を作る
count = 0
for i in range(1, N):
count += X[i] * Y[N-i]
print(count)
次に
まず
これには前述の
ですので各
であり、最大で 19,999,900,000(
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最後に全ての工程で必要な操作の回数を足し合わせてみると
20,000,299,998(
#これは 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
ここで注目するのは
具体的に
このとき
ここで注目して欲しいのは
これは掛け算が可換*3 であることから正しいとわかります。
このことから *4 となる組の数だけ 2 倍すると正しい答えとなります。
例えば
となって
よって 各
これに
59,528,927(
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これに
59,928,924(
となります
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 を勝ち取りました。やったね
このように計算の仕方を工夫してただ何も考えずにプログラムを作ったときよりも格段に速く動作するプログラムを作る過程こそが競技プログラミング の醍醐味です。少しでも競技プログラミング の楽しさが伝わっていたらいいなと思っています。
少しでも興味がある方はぜひ競技プログラミング を始めてみてください！
