競技プログラミングのすヽめ

これはGUTアドベントカレンダー2018の12/20分の記事です。他の記事はこちらから

----おことわり----

この記事ではあえて専門的な用語は使わずに、高校卒業レベルの数学・情報・プログラミングの知識さえあれば読める記事に仕上げることを目標としています。既に競技プログラミングやコンピュータサイエンスに精通している方が読むともどかしく感じる箇所も多いかと思いますが、ご容赦願います。

こんにちは。今年参加したGUTの活動は #GUTウニ紅白戦2018 のみなので、僕のことをご存じない方も大勢いらっしゃるかと思います。こるとんと申します。

今年のアドベントカレンダーでも、最近ハマっている趣味について書こうと思います。

皆さんは「競技プログラミング(通称:競プロ)」をご存知でしょうか？

AtCoderの説明に困ったらこれ使ってください pic.twitter.com/50s3czCxFy
— chokudai(高橋直大) (@chokudai) July 9, 2018

競プロの大まかな内容は、上ツイートに記載されている通りです(上記ツイートは、競技プログラミングのコンテストを開催する会社「AtCoder」の取締役社長のchokudaiさんによるもの)

...とは言え、これだけだと詳細が分からないと思うので、順に解説していきます。

競技プログラミングでは、定期的に「コンテスト」が開かれます。コンテストでは数問の数学的な問題が出題され、参加者達はそれを制限時間内にプログラムを使って解き、出来るだけ多くの得点を獲得することを目指します(得点の計算方法はコンテストによって異なるのでここでは割愛)。その結果に応じて参加者の中で順位が付けられます。

ここで注意するべきなのが、大抵の場合コンテストの参加者が考えるべきことは、「答えの求め方」ではなく、現実的な時間内に答えを上手く求めることが可能となるような、解の効率的な探索方法を考えることであるということです。

どういうことでしょうか。例えば、以下のような問題を考えてみましょう。

問題1

プログラムの実行時間制限:2秒

長さ $N$ の整数列 $a_1, a_2, \cdots, a_N$ が与えられます。次に, $Q$ 個の整数の組 $l_i, r_i\left(i = 1, 2, \cdots, Q\right)$ が与えられます。各 $l_i, r_i$ について, $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めてください。

制約

$1\leq N \leq 10^3$

$1\leq Q \leq 10^3$

$1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)$

$1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)$

例

$N=5$

$a_1=1, a_2=3, a_3=6, a_4=2, a_5=5$

$Q=3$

$l_1=1, r_1=3$

$l_2=5, r_2=5$

$l_3=1, r_3=5$

に対する答えは

貴方に求められているのは、制約を満たすような如何なる入力 $N, a_1, \cdots, a_N, Q, l_1, r_1, \cdots, l_Q, r_Q$ が与えられても、正しい答えを実行時間制限以内に出力するプログラムを書くことです。

「プログラムの実行時間制限」なるものは一先ず無視していただくとして。如何でしょうか。

恐らくプログラミングの経験がある方にとっては造作も無いでしょう。与えられた $l_i, r_i$ について $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を愚直に計算するプログラムを書けば、この問題は解決出来ます。

では、以下の問題は如何でしょうか。

問題2

プログラムの実行時間制限:2秒

制約

$1\leq N \leq 10^5$

$1\leq Q \leq 10^5$

$1\leq a_i \leq 10^3 \left(i = 1, 2, \cdots , N\right)$

$1 \leq l_i \leq r_i \leq N \left(i = 1, 2, \cdots, Q\right)$

一見何も変わっていないように見える？いえいえ、制約のところが僅かに変化しています。

とはいえ、問題の内容は全く変わっていません。ということで、こちらの問題も、与えられた $l_i, r_i$ について $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を愚直に計算するプログラムを書けばok...

とはなりません。何故か。

皆さんご存知の通り、コンピュータは単純な処理を高速に実行するのが得意です。数千個の数の総和計算もあっという間にこなしてくれます。

では、どれ程多くの処理を要求しても、コンピュータはそれらを必ず一瞬で解決してくれるのでしょうか。答えは当然"No"です。コンピュータの処理速度にも限界があります。

それはどの程度なのか、一言で言い表すのは大変難しいです。ここでは、「『基本的な処理』を $10^8$ 回以下しか行わないならば、大体2秒以内に処理が終わる」ということにしましょう。

「『基本的な処理』って何だよ」と仰る方、ごもっともです。ここでは、以下のようなものを指すことにしましょう。

・2つの数の加減乗除の計算

・2つの数の比較

この辺について語り始めるとキリが無いので、今回はこういうことで...

このことを踏まえた上で、先程の問題1と問題2を振り返ってみましょう。

問題1と問題2において、前述の方法により問題の解決を試みる場合、それぞれ最高でどの程度の回数基本的な処理が必要になるのでしょうか？

各問題で、 $N, Q$ について、最小値と最大値が決まっています。恐らく $N, Q$ いずれも大きい方が大変でしょう。ここでは, $N, Q$ がそれぞれ最大値を取る場合を考えます。

$l_i, r_i$ はどうでしょうか。 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めるのが最も大変なのは、 $\left(l_i, r_i\right) = \left(1, N\right)$ のときです。このとき, $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ は $N$ 個の数の総和ですから, これを計算するには基本的な処理を $N-1$ 回実行する必要があります。このようにして、整数の組 $l_i, r_i$ が $Q$ 組与えられます。最も大変になるのは, $Q$ 回の処理各々で $N-1$ 回の基本的な処理を要求される場合で、このとき答えを出力するまでに基本的な処理を $Q\left(N-1\right)$ 回ほど要求されます。

では、ここで問題1と問題2の制約を振り返ってみましょう。

問題1では、 $1\leq N \leq 10^3$ , $1\leq Q \leq 10^3$ という制約条件が与えられていました。これより、プログラムを実行する上で基本的な処理を $Q\left(N-1\right)$ 回実行することを求められたとしても、必要な基本的な処理の回数は $10^6$ 回程度しか要しません。つまり、2秒もあれば十分余裕を持ってプログラムを実行することが可能です。

一方、問題2では、 $1\leq N \leq 10^5$ , $1\leq Q \leq 10^5$ という制約条件が与えられていました。ここで、プログラムを実行する上で基本的な処理を $Q\left(N-1\right)$ 回実行することを求められた場合、必要な基本的な処理の回数は $10^{10}$ 回程度となります。これでは、プログラムは2秒以内に全ての処理を終えることが出来ません。

お分かりいただけたでしょうか。問題2において、答えを出力するプログラムを作成すること自体は、ある程度のプログラミング経験がある人ならば難しくはないはずです。しかし、短時間の間に答えを求めてくれるプログラムを書く為には、答えを効率的に求める方法を考えねばなりません。これは難しい問題です。

これは他のパズルやクイズにおいては類を見ない問題です。そして、これこそが多くの人を魅了する競技プログラミングの醍醐味なのです。

では、問題2を解決するには、どうすれば良いのか。例えば、以下のような方法があります。

$a_1, a_2, \cdots, a_N$ が与えられたときに、新たな数列 $S_n$ を,

$S_0=0$

$S_n=S_{n-1}+a_n$

と定義します。要は, $a_1からa_n$ までの総和ですね。 $S_1$ から $S_N$ を計算するときにそれぞれ2つの数の足し算を実行しますから, $S_1, S_2, \cdots, S_N$ の計算には計 $N$ 回の基本的な処理を要します。

では、その後 $l_i, r_i$ に対し、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ をどのように計算すればよいのか。実は $S_n$ さえ求めていれば簡単で、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}=S_{r_i} - S_{l_i-1}$ が成立しています。則ち、2つの数の引き算を行うだけで、 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めることが出来るのです。これより、 $Q$ 組の整数の組 $l_i, r_i$ に対して $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i-1} + a_{r_i}$ を求めるには、計 $Q$ 回の基本的な処理を実行すればよいのです。

以上より、この手法を取れば、答えを出力する為に必要な基本的な処理の実行回数は $N+Q$ 回です。これより、 $1\leq N \leq 10^5$ , $1\leq Q \leq 10^5$ という制約条件のもとでも2秒で十分答えを出力することが可能であることが分かります。

如何でしたでしょうか。「答えそのもの」ではなく、「答えを効率的に探す/求める方法」を考えるという、少し変わった面白さが伝わっていれば幸いです。

競技プログラミングは以下のような方々におすすめできます

パズルが好きな人

これまでに見てきたように、競技プログラミングとは、一言で言い表せば「人より速くパズルを解くゲーム」です。パズルが好きな人はハマりやすいと思います。「一般的なパズルに飽きたので一風変わったパズルを解きたい」という方には尚のことおすすめできます。

人と競うのが好きな人

「競技」プログラミングですからね。コンテストは他の参加者との勝負です。

レート(実力の指標)を上げるのが好きな人

言及していませんでしたが、冒頭に紹介したchokudaiさんのツイートの画像にも載っていたように、競プロでは各ユーザーの実力の指標として「レート」という数字が示されており、コンテストの結果に応じてこれが変動します。そのレートに応じて、ユーザー名表記の色が変わる、というのが競プロの通例です。まるでGUTで流行った某音楽ゲームのようですね。レート中毒者にもおすすめ出来る趣味です。

この記事を読んで競プロに興味を持つ方が1人でもいらっしゃれば幸いです。それでは、この記事を終える前にもう1問。

問題3

プログラムの実行時間制限:2秒

長さ $N$ の整数列 $a_1, a_2, \cdots, a_N$ が与えられます。次に, $Q$ 個の整数の三つ組 $t_i, p_i, q_i\left(i = 1, 2, \cdots, Q\right)$ が与えられます。各 $t_i, p_i, q_i$ に対し、以下のいずれかが成立します。