AtCoder Beginner Contest 098 ~計算量についてのお話~

先週土曜日に行われたABC098に参加しました。

リンクはこちら。

今回の結果がAB問題○CD問題TLE（Time limited exceeded. 時間制限に引っかかったという意味）でした。

テストケースは通っていたし愚直なプログラムなので、無限時間貰えれば通っていたと思います（多分）。

いままでコードがあっていれば通っていたのですが、ここから先に進むには計算にどれだけ時間がかかるのか把握しなくては行けなそうです。ということで、避け続けていた計算量の話を考えます。

ここでいう計算量というのはざっくりと「入力nが十分大きくなったとき、どの項に依存するか」ということを指します。例えば

[tex:2x^2 + x + 1]の計算量はx^2に依存します。これを

$O(x^2)$

と書きます。(係数は考えません）

さて、競技プログラミングではどれくらいの計算量であれば通るのでしょうか？

結論から言ってしまうと10の5乗くらいまでは通って、10の6乗だと通らないと思っておくと良いそうです。

これを踏まえて自分のC問題のコードを見てみます。リンクはこちら。

提出言語はRubyです。（「n.times→n回繰り返す」だけ知っていれば大丈夫です）

問題で与えられるnの最大値は3*10^5です。よって計算量としてはO(N)まで許されて、O(N^2）は許されないと考えます。自分のコードでは

6行目の.timesメソッドでn回

9行目と13行目の.timesメソッドでn-1回

処理を繰り返すコードを書いています。よってこのコードはO(N^2)です。つまり許されないコードですね

このように計算量というものを知っていればこのコードが通らないかどうか事前に知ることが出来ます。ではどうすればO(N)で出来たのかという話はまた次回。

追記

この記事を書くにあたり、Atcorderの社長高橋直大さんの「最強最速アルコリズマー」

を参考にしました。プログラミングの構文、登録の仕方から競技プログラミングで強くなるまでを例題を通して学べる良著です。

yakataの情報奮闘記