hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

分割数 DP について

昨日の 第4回ドワンゴからの挑戦状 予選 C 問題 で、分割数 DP を必要とする問題が出されました。

蟻本をよく読んでいる人ならご存知のとおり、この DP は dp[i][j] := j を i 分割する時の場合の数 とするとき、 dp[i][j] = dp[i][j-i] + dp[i-1][j] となります。しかし、蟻本の解説だけだとどうもわかりにくいです (少なくとも自分は理解するまでに N 時間かかりました)。

というわけで、ドワコンのあいだに実際に私が考察した、蟻本とは違うアプローチ (本質的には同じ) でこの式を導出してみます。

若干遅い解法

まず、なにを解きたいのかをちゃんと式で書きましょう。ちゃんと書くと、以下のようになります。

  •  N M 分割  ( dp\left[ M \right] \left[ N \right] ) a_{1} \leq a_{2} \leq \dots \leq a_{M}, \sum_{k=1}^{M} a_{k} = N を満たす数列  \left\{ a \right\} の総数

まず、 1 番目の要素  a_{1} の値を  x にすることを考えましょう。  a_{1} は他のどの値よりも小さいか等しいため、  a_{2}, a_{3}, \dots, a_{M} は必ず  x 以上の値を取ります。

 1 番目の値を確定させると、残った  (M-1) 個の要素に対して同様に分割数 DP を適用すれば良いことが分かります。このとき、各要素は必ず  x 以上の値をとるのですから、全ての要素から  x 引いて考えても問題ありません。

以上のことから、以下のような DP が立てられます。

 dp\left[ i \right] \left[ j \right] = \sum_{x=0}^{\lfloor \frac{j}{i} \rfloor} dp\left[ i-1 \right] \left[ j-i*x \right]

見た目でわかるとおり、これを実装すると 3 重ループになります。 \sum_{k=1}^{M} \frac{1}{k} \approx \log M という近似より、計算量はたぶん  O(NM \log M) です (間違っていたら教えてください)。実際に ドワコンの問題でこの漸化式を使っても通る のですが、次に説明する工夫をすることで log を取ることができます。

速い解法へ

基本的には、先ほどの式を応用させるイメージでやります。式を再掲します。

 dp\left[ i \right] \left[ j \right] = \sum_{x=0}^{\lfloor \frac{j}{i} \rfloor} dp\left[ i-1 \right] \left[ j-i*x \right]

 j-i*x という部分に着目します。 i, j を定数としてみたとき、 j から  i の倍数を引いていることが分かります。ここで、おもむろに  x = 0 の部分だけシグマから抜き出します。

 dp\left[ i \right] \left[ j \right] = \sum_{x=1}^{\lfloor \frac{(j-i) + i}{i} \rfloor} dp\left[ i-1 \right] \left[ (j-i) - i*(x-1) \right]  + dp\left[ i-1 \right] \left[ j \right]

ここで、 j' = j-i, x' = x-1 とおくと、

\begin{align} dp\left[ i \right] \left[ j \right] &= \sum_{x'=0}^{\lfloor \frac{j'}{i} \rfloor} dp\left[ i-1 \right] \left[ j'- i*x' \right] + dp\left[ i-1 \right] \left[ j \right] \\ &= dp\left[ i \right] \left[ j' \right] + dp\left[ i-1 \right] \left[ j \right] \\ &= dp\left[ i \right] \left[ j-i \right] + dp\left[ i-1 \right] \left[ j \right] \end{align}

このように変形できて、無事  O(NM) になりました。終わり! (雑)

ということで、蟻本とは少し違う導出をやりました。

蟻本練習問題解説 Part2 (2-2)

蟻本練習問題の解説をします。今回のトピックは貪欲法です!

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

猪突猛進! "貪欲法"

区間

POJ 2376: Cleaning Shifts

問題リンク

区間 N 個あり、 i 番目の区間 \left[ l_{i}, r_{i} \right] の閉区間である。これらの区間の中からいくつかを選び、 \left[ 1, T \right] を全て被覆したい。そのようなことが可能であれば選ぶ区間の数の最小値を、不可能であれば  -1 と答えよ。

▶表示する

POJ 1328: Radar Installation

問題リンク

2 次元平面上に点が  N 個ある。いくつかの円を用意して、全ての点を囲みたい (点が円周上にあっても、それは囲まれていると見なす)。円は半径が  d で固定であり、中心は必ず  x 軸上になければならない。このようなことが可能ならば用意する円の個数の最小値を、不可能であれば  -1 を出力せよ。

▶表示する

POJ 3190: Stall Reservations

問題リンク

区間 N 個あり、 i 番目の区間 \left[ a_{i}, b_{i} \right] と表される。何回かの操作をしてこの区間を全て取りたい。  1 回の操作では、overlap しない範囲でいくつでも区間を取ることができる (終点と始点の overlap も許されない。つまり取る区間それぞれについて  b_{p} \lt a_{q} (p \neq q, a_{p} \lt a_{q}) を満たす)。このとき、操作の最小回数と、それぞれの区間について何回目の操作で取ったかを求めよ。

▶表示する

その他

POJ 2393: Yogurt factory

問題リンク

ヨーグルト工場では、ヨーグルトの製造・配送・貯蔵を行っている。 i 週目にヨーグルトを  1 つ製造するには  C_{i} 円がかかり、またその週には  Y_{i} 個を配送しなければならないことがわかっている。ヨーグルトを  1 週間貯蔵するには  1 つあたり  S 円がかかる。貯蔵に期限や個数の上限はない。 N 週間の予定が与えられるので、配送の予定を全てクリアするときのコストの最小値を求めよ。

▶表示する

POJ 1017: Packets

問題リンク

 1 \times 1, 2 \times 2, \dots, 6 \times 6 6 種類の正方形がいくつかある。これらを全て、  6 \times 6 のいくつかの領域の中に重なりのないように敷き詰めたい。このとき、必要な  6 \times 6 領域の最小個数を求めよ。

▶表示する

POJ 3040: Allowance

問題リンク

あなたはコインを  N 種類持っている。具体的には、 V_{i} 円のコインを  B_{i} 円持っている。コインの価格は小さい順に並べると倍数列 (すなわち、あるコインの価格はその次に価格が低いコインの倍数) である。手持ちから  C 円以上の金額を何回か払うことを考えるとき、払える回数の最大値を求めよ。

▶表示する

POJ 1862: Stripies

問題リンク

 N 匹の生き物がおり、 i 番目の生き物の体重は  w_{i} である。体重が  w_{i}, w_{j} である  2 匹の生き物同士がぶつかると、元いた生き物は消え、新たに体重  2 \times \sqrt{w_{i} w_{j}} の生き物が  1 匹現れる。生き物がぶつかって最終的に  1 匹だけになるとき、最後に残った生き物の体重の最小値を求めよ。

▶表示する

POJ 3262: Protecting the Flowers

問題リンク

牛が  N 頭おり、 i 番目の牛は座標  T_{i} (\gt 0) におり、単位時間あたり  D_{i} だけ花を食べている。牛を  1 頭ずつ納屋に帰すことを考える。納屋は座標  0 にあるため、帰すには (納屋から牛のところまで行く) + (牛のところから納屋に帰る) で  2T かかり、帰す対象の牛は待っている間も、帰っている間も花を食べない。このとき、全ての牛が納屋に帰るまでに食べられる花の量の合計を最小化せよ。

▶表示する

次回は動的計画法を解説します!

蟻本練習問題解説 Part1 (2-1)

みなさんは、蟻本の「練習問題」を解いたことはありますか?本の中で掲載されている例題は見たことがあっても、練習問題までは手を出していない、という人はそれなりにいるのではないでしょうか (要出典)

というわけで、今日から不定期で蟻本の練習問題を解説していきます。学習の一助になってくれれば幸いです。わからないところがあれば Twitter などで気軽にきいてください。

英語の問題は簡単に和訳しています。分量が多いので何回かに分けてやっていきますが、なんとか完走したいです・・・!

シリーズ目次はこちらからどうぞ。

tsutaj.hatenablog.com

すべての基本 "全探索"

深さ優先探索

POJ 1979: Red and Black

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

POJ 3009: Curling 2.0

問題リンク

問題概要については、AOJ に全く同じ問題が日本語で掲載されているので、そちらを参照してください。

▶表示する

AOJ 0118: Property Distribution

問題リンク

概要は日本語なので省略します。

▶表示する

AOJ 0033: Ball

問題リンク

概要は日本語なので省略します。

▶表示する

幅優先探索

AOJ 0558: Cheese

問題リンク

概要は日本語なので省略します。

▶表示する

POJ 3669: Meteor Shower

問題リンク

隕石が  M 個落ちてくる。 i 番目の隕石は、座標  (X_{i}, Y_{i}) に時刻  T_{i} に落ち、落ちた直後からその座標とそれに隣接する 4 つの座標には立ち入ることができなくなる。あなたは最初に座標  (0, 0) におり、そこから単位時間あたり 1 マス分進んで安全な場所 (隕石による影響がない場所) まで移動したい。このようなことが可能であれば最短の時間を、不可能であれば -1 を出力せよ。

▶表示する

AOJ 0121: Seven Puzzle

問題リンク

概要は日本語なので省略します。

▶表示する

全列挙

POJ 2718: Smallest Difference

問題リンク

相異なる 10 進数の 1 桁の数字の集合が与えられる。この集合を 2 つの部分集合に分ける (空集合は許されない)。同じ集合に属する数字どうしを全て組み合わせて、数字を 1 つ作る。例えば集合が  \left\{ 0, 2, 5\right\} である場合、 250 502 などが作れる。ただし、leading zero は許されないため、  25 は作れない。このとき、それぞれの集合で作った 2 つの数字の差の絶対値の最小値を求めよ。

▶表示する

POJ 3187: Backward Digit Sums

問題リンク

長さ  N の順列が与えられる。1 行目にはその順列そのものを書き下す。2 行目以降は、前の行において隣接している要素同士を足しあわせたものを書き下すという操作を行う。この操作によって、最後の行は 1 つの数字からなる。順列の長さ  N と、最後の行に書かれた数字  K が与えられるので、順列を復元せよ。なお、答えが複数ある場合は、辞書順最小のものを出力せよ。

▶表示する

POJ 3050: Hopscotch

問題リンク

1 マスにつき数字 1 桁が書かれている  5 \times 5 のが盤面がある。適当な位置からスタートし、上下左右に移動して 6 桁の数字を作るとき、何種類の数字が作れるか?

▶表示する

AOJ 0525: Osenbei

問題リンク

概要は日本語なので省略します。

▶表示する

全探索できるかどうかは、あり得るパターン数がどれくらいあるのかをざっくりと計算すれば良いです。大まかな計算量の見積りができるようにしましょう。

次回は、貪欲法のトピックを扱っていきます。