競技プログラミングのススメ
この記事は、競プロ Advent Calendar 2021の９日目に作成されました。
1. はじめに
1-1. 自己紹介の前に
私の前に投稿している方の記事を拝見させていただきました。みなさん構成がしっかり練られていて参考になる部分が多い印象を受けました。個人的に特に関心したのは、H20さんが書いた【Python版】AtCoderのコンテスト中に「問題が解けない！」となった時に読む記事です！私もPythonを使っていることもあり、コンテスト中に正解できない時にどの状況かあまり考えず悩んでいることが多いです。また、計算量が怪しい時もとりあえず出してTLEにならないことを祈るような手法をとっていたので、今度からはコードテストを上手に利用し確認してから出そうと思いました！
1-2. 自己紹介
はじめまして！
にしん( nishin0141 )です。今まで記事を書いたことがないのに軽い気持ちで競プロ Advent Calendar 2021に参加しました 。
約1年前から競技プログラミング（以下競プロ）をやっていて現在（12/9）、AtCoderのRatingは732です。使用している言語はPythonですが、最近Rustで典型90問にしています。
1-3. どんな人に読んでほしいか
この記事は、「主に競プロをはじめてみたいけど難しそう...」という方にむけて記事を書いています。少しでも競プロの面白さを知ってもらってはじめの一歩を踏み出してほしいです！私が思う競プロの面白さは以下の３つです。
- コンテストの結果、レートが上がった時
やはりやってて面白い一番の理由はこれです！ AtCoderのコンテストによく出ているのですが、特に色が変わった時やレートが100ほど上がった時は最高です。Apex Legends をプレイしていた頃はランクが上がったり戦績がよかったりすると自分の実力が上がっていることを実感できました。それに似たような感情がこのコンテストで味わうことができるのです。しかも、コンテストに出たり勉強を続けているとコードを書くことに慣れていきます。
- コンテストで早く問題が解けた時
これもコンテスト中に面白いと思うもののひとつです。AtCoderでは基本的に毎週コンテストが開催されています。各コンテストには開始時刻と終了時刻が設定されていて、いかに早く正確に解くかが高い順位を取るカギになっています。
そんな時間との勝負になるコンテストですが、今まで解くのに時間がかかっていたような問題を、自己ベストと言えるほどの早さで解けた時は「面白い！」と感じます。Apex Legends でいうところの開幕に１パーティーを１人で壊滅することに似ていると私は感じます。
- 新しいアルゴリズムを理解した時
ただコンテストに出るだけではいつまでも上達していきません。自分の知らないアルゴリズムや考え方を勉強していく必要があります。この際に新しいアルゴリズムを理解した時に「この解法考えた人すげぇ！」、「めちゃくちゃ上手いこといくじゃん！」などと感動することが多々あります。このように成長しても新しい出会いが常に待っていることが競プロの面白い箇所だと思います。
2. 競プロをはじめたきっかけ
約1年間続けている競プロをはじめたきっかけは、大学の友人の紹介になります。学部2年のときに、「競プロおもしろいからやってみようよ」と言われてAtCoderをはじめてみたところ、自分の実力が数値化されるのが面白い！と思いそこからハマりました。
私は誘われた当時、読んでいておわかりの方もいると思いますが、Apex Legendsというゲームのランクマッチに夢中になっていました。（プラチナに行けないくらいのレベルでした...）
私の大学にはプログラミングの授業が必修であったので簡単なコード程度なら書くことはできましたが、関数の使い方すらまともに知らないような状態でした。そんな時に競プロと出会って計算量やコードの内容の質が大切なことを痛感しました。これは、今後プログラミングを活かして働きたいと思う方は学んでいて損することはないと思います。このように自分の中で競プロをやるメリットがたくさん見つかったので積極的に挑戦していこうと決意しました。
3. 競プロをするとどんなことができるようになるか
今まで競プロをしてきたからこそできるようになったことはたくさんあります。迷路を解くようなアルゴリズムを学んだり、大きな計算時間がかかるような問題を高速に計算する方法など学んでいます。今回はその中でも自分で解いていて面白いと感じたアルゴリズムについて紹介していきたいと思います。
3-1. 累積和
累積和はある区間での数の総和を求めるときに使われるアルゴリズムです。ここでは、累積和をPythonを用いて説明していきます。
3-1-1. 例題
AtCoder Beginner Contest 037 C - 総和
atcoder.jp
問題文
長さ $N$ の数列 ${a_i }$ と $1$ 以上 $N$ 以下の整数 $K$ が与えられます。 この数列には長さ $K$ の連続する部分列が $N−K+1$ 個あります。これらのそれぞれ部分列に含まれる値の合計の総和を求めてください。
制約
- $1 \leq K \leq N \leq 10^5$
- $0 \leq a_i \leq 10^8$
- $a_i$ は整数である。
入力
$N$ $ $ $K$
$a_1$ $ $ . . $ $ $a_N$
$a_1$ $ $ . . $ $ $a_N$
出力
部分列に含まれる値の合計 $N−K+1$ 個の総和を出力せよ。
3-1-2. 解法
この問題を解く時に注意しなければいけないのが計算量です。
問題文の通りに長さ $K$ の連続する部分列の個数である $N - K + 1$ 回for文を回し、その中でそれぞれの $K$ 個の和を計算するという解法は思いつくと思います。しかし、この解法では残念ながら満点をとることはできません！
これは、最悪の場合 $O(N^2)$ かかってしまい「実行時間制限: 2 sec」 を超えてしまうからです。
実行時間制限が超えてしまう解法
# 入力 N, K = map(int, input().split()) a = list(map(int, input().split())) # 総和の計算 ans = 0 for i in range(N-K+1): for j in range(i, i+K): ans += a[j] print(ans)
じゃあどうすればいいんだよ！！！！！！！
そう思う方もいるかもしれませんが、ここで累積和の出番になります。それではこの問題を累積和で解くとどういう考え方になるのか説明していきます。
累積和とは、先ほどにも述べたようにある区間での数の総和を求めるときに用いられるアルゴリズムになります。
この問題では、数列 $a_0$ から $a_i \left( i = 0, 1, ・・ , N \right)$ までの和を先に計算して配列で管理することにより高速に解くことができます。
まず、はじめに累積和をしその結果を配列に保存していきます。
cum = [0] for i in range(N): cum.append(cum[i] + a[i])
ここで気をつけてほしいのは「配列のはじめは0にする」ということです。まだなにも足されていない数も保存しておかなければ累積和を使った計算で予期しない動作がすることがよくあるので忘れずに入れておきましょう。
累積和を行ったあとは保存した配列を利用して総和の計算をしていきます。ここで重要になるのはどうfor文を回してどの配列を参照していくかです。
この図を参考に考えていくとfor文を回す回数は $5 - 3 + 1$ 回、すなわち一般化すると $N - K + 1$ 回になります。そして参照する配列は $i$ と $i + K$ になります。
以上をまとめるとこの問題は
$\displaystyle{ans = \sum_{i = 0}^{N - K} cum[i + K] - cum[i]}$
これまでのことをプログラムにまとめると以下のようになります。
- 累積和を用いた解法
# 入力 N, K = map(int, input().split()) a = list(map(int, input().split())) # 累積和 cum = [0] for i in range(N): cum.append(cum[i] + a[i]) # 総和の計算 ans = 0 for i in range(N-K+1): ans += cum[i + K] - cum[i] print(ans)
以上で累積和についての説明は終わりです。次にいもす法について説明していきます。
3-2. いもす法
いもす法は先ほど説明した累積和を用いて更新することができるある区間での問題を解く時に用いられるアルゴリズムです。累積和は更新することがない区間だったのに対し、いもす法は数の出入りなどの更新に対応しています。
それでは、ここでも同様に例題を用いて紹介していきます。
3-2-1. 例題
AtCoder Beginner Contest 024 B - 自動ドア
atcoder.jp
問題文
ABCマーケットは高橋王国で最も人気なスーパーマーケットです。 入り口は自動ドアになっています。
この自動ドアは人が前を通りかかると自動で開き、そこから $T$ 秒後まで開き続け、その後自動的に閉じます。 ドアが開いている状態で新たに人が前を通りかかると、通りかかった時刻のさらに $T$ 秒後まで開き続ける時間が延長されます。
今日はのべ $N$ 人の客が自動ドアの前を通りかかりました。 $i$ 番目の人が通りかかった時刻はABCマーケットが開店してから $A_i$ 秒経った時刻です。
今日、この自動ドアが開いていた合計秒数を求めてください。
制約
- $1 \leq N \leq 10^5$
- $1 \leq T \leq 10^5$
- $1 \leq A_i \leq 10^6$
入力
$N$ $ $ $T$
$A_1$
$A_2$
・
・
$A_N$
$A_1$
$A_2$
・
・
$A_N$
出力
ドアが開いていた秒数を 1 行に出力せよ。 出力の末尾に改行を入れること。
3-2-2. 解法
この問題で重要なことは、$i$ 番目の人が通って自動ドアが開いた時刻と閉じた時刻をあらかじめ記録しておくということです。まずは、各時刻の配列を作り $i$ 番目の人が通った時刻 $A_i$ に $+1$ 、自動ドアが閉じる時刻 $A_i + T$ に $-1$ を入れていきます。
# 開き始めと終わりの時間を記録 num = 2 * 10 ** 6 imos = [0]*(num) for i in A: imos[i] += 1 # 始まりは足す imos[i + T] -= 1 # 終わりは引く
今回の問題の制約上、時刻の最大は $A_i = 10^6, T = 10^5$ のときの $10^6 + 10^5$ になります。そのため上のコードでは少し余裕をもって配列の長さは $2 \times 10^6$ に設定してあります。開き始めと終わりの時間を記録したら、その配列を使って累積和を行っていきます。そうすると、時刻 $cum_i$ の時に自動ドアが開いている処理が何人分あるかが配列に記録されていきます。
# 累積和をとっていく
cum = [0]*(num)
for i in range(len(imos)-1):
cum[i + 1] = cum[i] + imos[i]
最後に、その配列を順番に参照していき値が0以上、すなわち自動ドアが開いている処理が1人分以上あるときは自動ドアが開いている状態と等しいため $ans$ にカウントをしていきます。こうしてこの問題は無事に解くことができました。いもす法については理解が少し難しくなるため、いろんな方が書いているいもす法についての記事を見ることをお勧めします。以下は今回の例題の処理を実際にPythonで書いたプログラムになります。
- いもす法を用いた解法
# 入力 N, T = map(int, input().split()) A = [int(input()) for _ in range(N)] # 開き始めと終わりの時間を記録 num = 2 * 10 ** 6 imos = [0]*(num) for i in A: imos[i] += 1 # 始まりは足す imos[i + T] -= 1 # 終わりは引く # 累積和をとっていく cum = [0]*(num) for i in range(len(imos)-1): cum[i + 1] = cum[i] + imos[i] # 開いている時間をカウントしていく ans = 0 for i in cum: if i > 0: # 人が通ってからT秒以内のとき ans += 1 print(ans)
4. おわりに
今回はブログや記事の書き方を練習するためにもこのようなものを書かせていただきました。累積和といもす法のどちらも丁寧に解説してくださっている方の記事がたくさんあるので、これを機にぜひ拝見してみてください！この記事を読んで「競プロをはじめたいけどハードルが高そう...」と思っている方に背中を押せたらうれしいです！
最後までこの記事を読んでいただきありがとうございます :)
