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

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

xxpoxx

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


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

対象読者

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

中級者になるためには?

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

目次

二分探索

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

理論、考え方

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

a[5]=[1,2,4,7,22]a[5] = [1, 2, 4, 7, 22]

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

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

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

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

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

実装

一見難しいように見えますが(真ん中の取り方とかおかしくない?と思うかもしれません)、プログラムにすると、再帰関数を用いて次のようになります。真ん中は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から選んで解いてみましょう!

累積和

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

理論、考え方

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

a[105]=[5,4,7,12,22,,4]a[10^5] = [5, 4, 7, 12, 22, \cdots , 4]

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

sum[105+1]=[0,5,9,16,28,50,]sum[10^5+1] = [0, 5, 9, 16, 28, 50, \cdots]

これをO(N)O(N)で持っておいて、O(1)O(1)でとってくる、ということです。先ほどのa[3]a[3]からa[40000]a[40000]までの和はsum[40001]sum[3]sum[40001]-sum[3]とすればよいですね!

実装

簡単です。こんな感じです。適当にa[i5]a[i-5]からa[i]a[i]の和を全て出力します。

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)

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

DP(DynamicProgramming)

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

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

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

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

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

制約:

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

理論、考え方

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

dp[i+1][w]=max(dp[i][ww[i]]+v[i],dp[i][w])dp[i+1][w] = max(dp[i][w-w[i]] + v[i], dp[i][w])

w<w[i]w < w[i]のとき

dp[i+1][w]=dp[i][w]dp[i+1][w] = dp[i][w]

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

実装

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

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])

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

さいごに

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

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


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

この記事を書いた人
xxpoxx

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

この記事をシェア

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

関連する記事

2019年12月7日
Pythonで競技プログラミングの勧め【AdC2019 38日目】
ebi
2019年12月5日
ラビンカープ法のおはなし+二次元のロリハいいぞ
0214sh7
2019年12月4日
緑コーダーが1日1ACを265日続けた結果
hukuda222
2019年12月26日
アドベントカレンダーエンディング
HF
2019年12月25日
今からでも間に合う!?彼女(嫁/ママ/推し/etc...)とデートしよう!
chuukunn
2019年12月25日
TensorFlow.jsでwasmを使ってみるためにコントリビュートした【AdC2019 56日目】
sappi_red

活動の紹介

カテゴリ

タグ