Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

LeetCode - 1359. Count All Valid Pickup and Delivery Options

LeetCode 数え上げ 数学 動的計画法 良問 複数解法

leetcode.com

概要

あなたはN種類の括弧を持っていて、互いに区別可能である。あなたはこれらを一列に並べる。すべての括弧に関しては、閉じる括弧'）'よりも前に開く括弧'（'が先に来る必要がある。
この並び方は何通り存在してるのか？ 10^9+7で割ったあまりで答えよ。

制約： 1 <= N <= 500

ACするまで

1. 長さが1000前後の括弧列の数え上げは、深く考えずにDP！
2. DPをする->AC

考察

解法1　動的計画法

この問題で括弧の区別をなくせば、有名なカタラン数の問題である。
Wikipediaにもあるように、カタラン数は簡単な式もあるが、碁盤目の上を動かして、いわゆる2次元DPをすることでも得られる。
基本的に、かっこ列が絡む問題で、計算量に余裕があるのならば
dp[i][j] := i文字目まで決めて、かっこの深さがjのときの○○
とDPテーブルを定めて2次元DPをするとうまくいく傾向にある。

今回もこの例に漏れない。DP遷移を考えてみる。

  • dp[i][j] -> dp[i + 1][j + 1]　これはかっこを1つ開くということに相当する。どの種類の括弧を開いたのかは今ここではまだ決めない。なので、遷移するときはそのまま足す。
  • dp[i][j] -> dp[i + 1][j - 1]　これはかっこを1つ閉じてることに相当する。理由は後述するが、「その時の開いてる括弧の数(つまりj)」倍かけて遷移する。

なぜj倍をかけるのか？
ひとまず、この問題での数え上げを次のように、「かっこタイプ」という中間体を定義するとわかりやすい。
まず、どの種類の括弧を使うかを具体的に決めずに、「かっこタイプ１」、「かっこタイプ２」みたいに使われる括弧の種類に別名をつける。その「かっこタイプx」などの別名で並び替えの場合の数を計算したのち、本来のどの種類の括弧をどの「かっこタイプ」に割り振るか？でN!をかければよい。
つまり、DPで計算するのは「かっこタイプ」の並びの場合の数である。
ここで、括弧を閉じる際に起きることを考える。括弧を開く際には、ひとまずどの「かっこタイプ」を使うか？は棚上げにした。
これの処理をしなければならない。括弧を閉じる際に、閉じる直前の括弧の深さのぶんだけ、閉じられてない「かっこタイプ」が存在する。そのうち、どの「かっこタイプ」を選んで閉じても問題はない(括弧の深さが1つ減る)ので、閉じる直前の閉じられてない「かっこタイプ」の数だけ、場合の数が増えるのである。毎回のこの操作は独立なので、DP遷移で掛算するのも問題がない。

よって、これをソースコードに起こせばよい。計算量は O(N^2)

 int countOrders(int n) {
        const ll MOD = 1000000007;
        ll dp[1000 + 10][500 + 10] = {};
        dp[0][0] = 1;
	    for (int i = 0; i < 2 * n; i++) {
		    for (int j = 0; j <= n; j++) {
			    if (dp[i][j] == 0)continue;
			    //(を増やす
			    if (j + 1 <= n) {
				    dp[i + 1][j + 1] += dp[i][j];
				    dp[i + 1][j + 1] %= MOD;
			    }
			    //)を増やす
			    if (j >= 1) {
				    dp[i + 1][j - 1] += dp[i][j] * j;
				    dp[i + 1][j - 1] %= MOD;
			    }
		    }
	    }
	    ll frac = 1;
	    for (int i = 1; i <= n; i++)frac *= i, frac %= MOD;
	    return (int)((frac * dp[2 * n][0]) % MOD);
    }
解法2　数学のみで数え上げ

カタラン数は簡単な組み合わせの式で表されることから、実はこれもできるのではないか？と少しは勘づくかもしれない。実際できるし、カタラン数よりも議論的にはわかりやすいと思う。

ひとまず、2N個の何も入ってない配列があり、そこにN種類の括弧を入れていくことを考える。

  • 1つ目の種類の括弧は、2N個の場所のうち2つの場所を選べる。(選ぶ2つさえ決まれば、どれが先で'（'になり、どれが後で'）'になるかは自明に決まる)
  • 2つ目の種類の括弧は、2N - 2個の場所のうち2つの場所を選べる。
  • iつ目の種類の括弧は、2N - 2i個の場所のうち2つの場所を選べる。

このように考えると、普通の「いくつあるものから何個かを選ぶ時の場合の数」となる。答えは、これらをかけ合わせればよい。これの計算量は O(N)。

一言

こういう数え上げはパッとできるようになるためにも訓練をしないとだめだなぁ。