feature image

2019年12月16日 | ブログ記事

競プロ初心者が中級者にレベルアップするための小技集【AdC2019 47日目】

この記事は東京工業大学デジタル創作同好会traP アドベントカレンダー2019の12/16の記事です。


こんにちは、19のxxpoxxです。いつもは競技プログラミング(AtCoder:緑)やゲームの開発、部内サービスの開発などをしています。
競プロは始める際に壁に当たることは少ないのですが、少しできるようになってきたあたり、つまり中級者になれそうな時に壁に当たることが多いと思います。僕も今めちゃくちゃ壁にぶつかっています...
この記事では、競プロ初心者や僕のような中級者になれない人がレベルアップするために覚えておくべきアルゴリズムをまとめていきます。
そもそも、競技プログラミングとはなんぞや?という人は今年の新歓ブログリレーでeiyaさんが書いた記事を読んでみましょう。

対象読者

この記事は以下の人を対象にしています。

中級者になるためには?

なにをすればいいのでしょう。わかっていたら僕はとっくに水色になっています答えはただひとつ、問題を解くことです。過去のABCの問題を解くことで、解ける問題も増えていきます。しかし、すぐに気づくと思います。全然解けない(´;ω;`)
競プロはただ発想力や数学力を問うものではなく、アルゴリズム力や実装力を問うものでもあるのです。つまり、なにも勉強せずにただ問題を解いたところで全ての問題が解けるようになるわけではありません。そこで、C問題やD問題を解くために必要なアルゴリズムをまとめていこうと思います!計算量などの話も少しだけ出てくるのですが、わからない方はなんか早くなるんだなと思っておいてください。 けんちょんさんの記事を読んでみてください。
なお、ソースコードの例はC++Pythonの順に載せています。また、実行のために必要な諸々(main関数やimport、入力値など)は補ってください...

目次

二分探索

めっちゃ有名なアルゴリズムです。

理論、考え方

以下のようなソートされた配列があったとします。

この配列にが含まれているか調べたいとき、どのようにすれば良いでしょうか。普通の人はが要素に含まれるか、前から見ていくと思います。これをプログラムにすると、以下のようになります。

for(int i = 0; i < 5; i++){
    if(a[i] == 22){
        cout << "存在する" << endl;
    }
}
for i in a:
    if i == 22:
        print("存在する")

しかし、この例の場合、処理の回数は回となります。今回は5個の配列なので、コンピュータで実行すればすぐに結果が返ってきますが、これが個の要素を持つ配列だったらどうでしょうか...?
そのような時に登場するのが二分探索です!
先ほどの例を用いて説明します。二分探索はその名前の通り、二つに分けて目的の要素を探していくものです。先ほどの例でを二分探索で探索するには、以下のようにします。

  1. 配列の真ん中の要素、つまり4を見る。
  2. がそれより大きいか小さいかを判断し、大きい場合は4より上の範囲、小さい場合は4より下の範囲の真ん中の要素を見る。もしなら存在すると判断する。(今回の場合は大きいので[7, 22]を見てその真ん中の要素、つまり22を見る)
  3. がそれより大きいか小さいかを...(ry
  4. 最後までとり、ではなかったら存在しないと判断する。

というように真ん中で区切って大小を比較し、再び真ん中で区切って...と繰り返していき、一度も目的の要素を取らなかったら存在せず、取ったら存在するというように探索していきます。

実装

一見難しいように見えますが(真ん中の取り方とかおかしくない?と思うかもしれません)、プログラムにすると、再帰関数を用いて次のようになります。真ん中はfloor((i+j)/2)でとっていますね。

int binary_search(int i, int j){
    int m = floor((i+j)/2);
    if(i > j){
        cout << "存在しない" << endl;
        return 0;
    }else{
        if(a[m] == ans){
            cout << "存在する" << endl;
            return 0;
        }else if(a[m] > ans){
            binary_search(i, m-1);
        }else{
            binary_search(m+1, j);
        }
    }
}
def binary_search(i, j):
	m = math.floor((i+j)/2)
	if i > j:
		print("存在しない")
		return
	else:
		if a[m] == ans:
			print("存在する")
			return
		elif a[m] > ans:
			binary_search(i, m-1)
		else:
			binary_search(m+1, j)

これを用いるのは、配列にある値が含まれているのか探す場合などです。理解することができたら、二分探索を用いる問題をAtcoder Tagsから選んで解いてみましょう!

累積和

配列のある区間における要素の和をでとってこられるようにする、のアルゴリズムです。

理論、考え方

例えば以下のような配列があったとします。

この配列のからまでの和が、回のループの中で必要になったとします。
愚直に3から40000まで足していくのが愚直に求める方法ですが、これではTLEになってしまうでしょう。困りました...
ここで現れるのが累積和というアルゴリズム(考え方?)です。内容は簡単で、予め最初の要素から各要素の合計を配列に記録しておく、というものです。つまり、上の例なら次のようになります。

これをで持っておいて、でとってくる、ということです。先ほどのからまでの和はとすればよいですね!

実装

簡単です。こんな感じです。適当にからの和を全て出力します。

sum[0] = 0;
for(int i = 0; i < N; i++){
    sum[i+1] = sum[i] + a[i];
}
for(int i = 5; i < N; i++){
    cout << sum[i+1] - sum[i-5] << endl;
}
sum.append(0)
for i in range(N):
    sum.append(sum[i] + a[i])
for i in range(5, N):
    print(sum[i+1] - sum[i-5)

で処理できましたね!
累積和を用いる問題をもっと解きたいという方はAtcoder Tagsから選んで解いてみましょう!!

DP(DynamicProgramming)

漸化式(のようなもの)を立てて様々なものを求めるアルゴリズムです。
次のような問題を考えてみましょう。

価値が 重さが であるような 個の品物と、容量が のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます:

価値の合計の最大値を求めてください。

入力:1行目に2つの整数  が空白区切りで1行に与えられます。 続く 行で i 番目の品物の価値 と重さ が空白区切りで与えられます。

出力:価値の合計の最大値を1行に出力してください。

制約:

この問題は、どのようにして解けばいいのでしょうか。おそらく、DPを知らないとどこから手を出せばいいのかもわからないと思います。

理論、考え方

では、実際にDPを使って解いていきましょう。
DPとは、漸化式を作ると言いましたが、これは実際には主に配列を用いて表現します。とても簡単な例を言うと、のような形です。このように式を作るには、まずなにを式にするのかが大切になります。これは問題を実際にたくさん解いて身につけていきましょう。この問題では、配列dp[][]をまでの重さの総和が以下で最大化した価値であるとします。すると、dpの漸化式は以下のように考えることができます。
のとき

のとき

少し解説します。
まず、上の式は番目まで価値を最大にとってきたときに、番目において、品物をナップザックに入れられる状態を表しています。よりも大きいときには、[]までの重さで価値を最大化させてきたナップザックに[]の重さの品物を入れてまでの重さで価値を最大化させた状態が作れますよね?さらに追加できるときに追加したほうが価値が大きくなるかどうかを判断するために、max関数を用いて価値を最大化させています。
同様に[]よりも小さいときにはナップザックに追加できないので(追加すると番目での重さの総和がを超えてしまう)、そのような場合にはそのままの価値を受け継ぎます。
ここで、漸化式を使うには初期値が必須です。DPを用いる時には忘れないようにしましょう。今回の場合は、初期値はと定めることができます。そして、個を使ってまでの重さで価値の最大化を行えばいいので、求めるのはであることがわかります。

実装

プログラムにすると、次のようになります。なお、実行できるように変数名を少し変えています。

int dp[N+1][W+1];
dp[0][0] = 0;
for(int i = 0; i < N; i++){
    for(int w = 0; w < W+1; w++){
        if(w >= c[i]){
            dp[i+1][w] = max(dp[i][w-c[i]] + p[i], dp[i][w]);
        }else{
                dp[i+1][w] = dp[i][w];
        }
    }
}
cout << dp[N][W] << endl;
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(N):
    for w in range(W+1):
        if w >= c[i]:
            dp[i+1][w] = max(dp[i][w-c[i]] + p[i], dp[i][w])
        else:
            dp[i+1][w] = dp[i][w];
print(dp[N][W])

このように、番目と番目で関係性が見えてきそうな問題には、DPを使ってみましょう!実はこの問題はAOJで実際に解くことができるとても有名なナップザックDPという問題です!理解できたら解いてみましょう。また、他にもDPの問題が解きたいという方は、Atcoder Tagsから解いてみましょう。さらに、DPにはこのような基本的なものからとても難しいものまでたくさんの種類があります。†完全に理解した†方は、他のDPも勉強してみましょう!

さいごに

レベルアップするためのアルゴリズムや考え方を3つ紹介してきましたが、いかがでしたでしょうか?紹介したいアルゴリズムはもっとあるのですが、長くなりそうなので絞って紹介しました。わかりにくい点がありましたらコメントやTwitterなどで質問してください。また、自分も勉強中なので間違っている点があるかもしれません。そのような場合はコメントやTwitterで馬鹿にしてください...もっといろいろなものを知りたい、より詳しく知りたいという方は、ググってみたり、蟻本[1]を買ってみるといいと思います。

明日、12月17日はmazreanくんの記事です。お楽しみに!


  1. 表紙に蟻がいるので、蟻本と呼ばれています。 ↩︎

xxpoxx icon
この記事を書いた人
xxpoxx

雰囲気で競プロをやっている

この記事をシェア

このエントリーをはてなブックマークに追加
共有

関連する記事

2018年12月12日
多重スリーブの世界と,各種進捗報告。
Silviase icon Silviase
2019年12月21日
モデリングを始めてみたい君へ、MagicaVoxelのススメ
isak icon isak
2019年12月13日
ゲーム紹介「League of Legends」【AdC2019 44日目】
Yataka_ML icon Yataka_ML
2019年12月25日
TensorFlow.jsでwasmを使ってみるためにコントリビュートした【AdC2019 56日目】
sappi_red icon sappi_red
2019年12月25日
無料でDTM環境構築 電子音系編
liquid1224 icon liquid1224
2019年12月22日
部内製チャットサービス「traQ」UIのこれから 【AdC2019 53日目】
sigma icon sigma
記事一覧 タグ一覧 Google アナリティクスについて