ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Beginner Contest 051 B - Sum of Three Integers

AtCoder プログラミング 競技プログラミング

お題箱より。

B - Sum of Three Integers

計算量の考え方に入門するのにとてもいい問題です。 O(K) 解法について知りたい…というリクエストだったので、色々な計算量で解く方法を解説してみました。

O(K^{3}) 解法

全ての基本、全探索です。 0 \le X, Y, Z \le K を満たす (X, Y, Z) を全て試します。和が S になれば、条件を満たす組み合わせが1つ見つかったとして答えに1を足します。

この解法の計算量は O(K^{3}) です。今回の問題では K \le 2500 まで大きくなりうるので、単純に3乗すると 1.5625 \times 10^{10} です。流石に間に合いませんね。

TLEコード

Submission #6666763 - AtCoder Beginner Contest 051

O(K^{2}) 解法

計算量を落とします。計算量を落とす王道の考え方の1つは、「変数のうちいくつかを固定すると、残りが自動的に決まる」という性質がないか探してみることです。

今回の問題では、 X, Y を固定すると残りの Z は S - (X+Y) として唯一に決まります。そのため (X, Y) のペアについては全探索し、 Z = S - (X+Y) が 0 \le Z \le K の範囲に入っていれば答えに1を足す、という解法で答えを求めることができます。

計算量は O(K^{2}) になります。今回の制約であればこれで十分間に合います。

ACコード

Submission #6666779 - AtCoder Beginner Contest 051

O(K) 解法

固定する変数を3つ、2つ…と来たら次は1つです。 X を固定したとしましょう。

このとき残りの Y, Z については、 Y+Z = S - X が成り立つことは分かるものの1通りには決まりません。では、この (Y, Z) のペアの個数を求めることはできないでしょうか。

具体的な例として、入力が K = 6, S = 11 だとして、 X = 3 に固定したとします。このとき 0 \le Y, Z \le K かつ Y+Z = S - X を満たす (Y, Z) のペアは (2, 6), (3, 5), (4, 4), (5, 3), (6, 2) の5通りです。このように Y, Z それぞれのとり得る値はある連続した整数になっていて、そのとり得る整数の個数がそのままペア (Y, Z) の個数になります。この範囲の両端を求めれば個数が分かりそうです。

満たすべき条件は 0 \le Y, Z \le K と Y + Z = S - X なので、変数 Z を消去すると以下の不等式が得られます。

  • 0 \le Y \le K
  • 0 \le Z = S - Y - X \le K
    • 変形して、 Y \le S - X かつ S - X - K \le Y

つまり Y の下限は Y_{\min} = \max(0, S - X - K) 、上限は Y_{\max} = \min(K, S - X) となります。もし Y_{\min} \le Y_{\max} であれば範囲内の値は Y_{\max} - Y_{\min} + 1 通りあり、そうでない場合は存在しません。より正確に書くと \max(0, Y_{\max} - Y_{\min} + 1) 通りです。

X を固定すればこの値は計算できるので、全探索した X それぞれに対してこの値を求めて合計すれば解くことができます。これで O(K) です。

ACコード

Submission #6666798 - AtCoder Beginner Contest 051

O(1) 解法

O(K) で終わりかと思いきや、実は O(1) でも解けます。これは数学の力を使います。

先ほどと同様に入力が K = 6, S = 11 のときにおいて、 X を全探索して 0, 1, 2, ... と1ずつ増やしていくときに、 Y_{\min} = \max(0, S - X - K) 、 Y_{\max} = \min(K, S - X) がどのように変化するかをプロットすると次のようになります。これは折れ線グラフであり、つまり傾きが同じそれぞれの部分は等差数列と見なすことができます。

f:id:betrue12:20190803205124p:plain

つまり、条件を満たすペアの数 \max(0, Y_{\max} - Y_{\min} + 1) も折れ線グラフになります。

f:id:betrue12:20190803211218p:plain

この左右それぞれの領域は等差数列になっているので、等差数列の和の公式を使えば合計を求めることができます。つまり求めたい答えである、全ての X に対する \max(0, Y_{\max} - Y_{\min} + 1) の合計値を O(1) で計算することができます。

ただしこの図は入力が 0 \le S-K \le K を満たすときの形であり、そうでない場合は形が変わります。それぞれ場合分けして計算しましょう。

これが O(1) 解法です。ただ計算がゴチャゴチャするので、特にコンテスト本番で O(K) や O(K^{2}) が間に合うのにわざわざこの解法を採用するのはオススメしません。

ACコード

Submission #6666944 - AtCoder Beginner Contest 051

まとめ

元がとてもシンプルな問題なので、 O(N) 解法では条件を満たす値がある連続した範囲に収まってくれたり、 O(1) 解法ではさらにその個数の変化が等差数列になっていたり、良い性質を利用して計算量を落とすことができました。

一方で、最後の O(1) 解法は場合分けが大変で計算ミスのリスクもありますね。制限時間内に計算が終われば速くても遅くてももらえる点数は同じなので、制約を確認して大丈夫そうであれば、無理に計算量を落とそうとせずに楽な解法で通すという意識も大事です。

HUPC2019 Day1 D: 貪欲が最適？

プログラミング 競技プログラミング AOJ

お題箱より。

Aizu Online Judge Arena

解法

答えとなる金額の払い方の必要条件を考える

ある金額 x について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額 x は条件を満たす」と書くことにします。そして条件を満たす最小の金額（答え）が存在すると仮定して、それを X 円と表記します。

答えとなる X 円の払い方について必要条件を考えてみると、実は意外と絞れることに気づきます。まず、

  • X 円の貪欲な払い方は、 B 円硬貨を必ず含む

ということが言えます。つまり必ず X \ge B であるということです。もしそうでない場合使える硬貨は A 円と 1 円だけになり、これでは貪欲が必ず最適になるからです。

このことからさらに、

  • X 円の最適な払い方は、 B 円硬貨を必ず含まない

ということも言えます。もし条件を満たす X に対する貪欲な払い方と最適な払い方にともに B 円硬貨が含まれている場合、その硬貨を取り除くことで X-B も条件を満たすことが分かるからです。これでは X が条件を満たす最小値だという仮定に反します。

そうすると最適な払い方について

  • X 円の最適な払い方は、 A 円硬貨を必ず含む

ことも言えます。もし含まない場合最適な払い方で使える硬貨が1円だけになってしまい、これで貪欲に勝つことはできません。そうすると先ほどと同様の理由で

  • X 円の貪欲な払い方は、 A 円硬貨を必ず含まない

ことも言えます。

さらにもうひとつ、

  • X 円の最適な払い方は、1円硬貨を必ず含まない

ことも言えます。もし最適な払い方に1円硬貨がある場合には、それを1枚減らして金額 X-1 にしたときに貪欲な払い方がどう変化するか考えます。1円硬貨が含まれている場合は単にそれが1枚減り、そうでない場合はより大きい硬貨を崩した上で1円硬貨が1枚減るので合計枚数が増えます。どちらにせよ金額 X-1 は必ず条件を満たすことになるので、 X が最小値であることに反します。

これまでの内容を整理します。条件を満たす金額 X の最適な払い方と貪欲な払い方それぞれが含むコインについて、以下の必要条件が成り立ちます。

最適な払い方 貪欲な払い方
1円硬貨 含まない -
A 円硬貨 含む 含まない
B 円硬貨 含まない 含む

けっこう絞れました。

答えの候補となる金額を絞る

前表から、金額 X の必要条件も分かってきます。最適な払い方では A 円硬貨だけを使うことから X は A の倍数であり、貪欲な払い方に A 円硬貨が含まれないことから X を B で割った余りは A 未満であることが分かります。そして B 以上である必要があります。

この条件を満たす数が実際どのようになるのか、具体例で考えます。例えば A = 3, B = 10 としましょう。上記の条件を満たす数は、以下の図のようになります。

f:id:betrue12:20190803181058p:plain

これはつまり、正である B の倍数それぞれに対して、右側にある最も近い A の倍数です。これは正である B の倍数を A で割った「切り上げ」に A を掛け直したもの、つまり k=1, 2, 3, ... に対する x_{k} = \lceil\frac{kB}{A}\rceil A として列挙することができます。

これでも候補はまだ無限個ありますが、実は

  • もし x_{1} が条件を満たさないのであれば、全ての x_{k} は条件を満たさない

ということが言えます。公式解説ではこの証明は略されていたので、書いておきましょう。

証明

数学的帰納法のように「 x_{1} と x_{k} が条件を満たさないことを仮定すると、 x_{k+1} も条件を満たさない」ことを示すことで証明します。

金額 x_{k} = \lceil\frac{kB}{A}\rceil A について r_{k} = x_{k} \% B と置きます。先ほど書いたように x_{k} は B で割った余りが A 未満になるように決めているので r_{k} \lt A が成り立ちます。

このとき x_{k} に対して、「 A 円硬貨だけで払う」払い方Pと「大きい方から貪欲に払う」払い方Qを考えます。払い方Pは A 円硬貨 \lceil\frac{kB}{A}\rceil 枚になり、払い方Qは B 円硬貨 k 枚と1円硬貨 r_{k} 枚になります。いま金額 x_{k} が条件を満たさないという仮定を置いているので、 \lceil\frac{kB}{A}\rceil \ge k + r_{k} が成り立っていると仮定します。

ここから金額を x_{k+1} に変更したときの変化を考えます。このとき x_{k} と比べて増える金額は、 x_{1} もしくはそれより A 円だけ少ない数になります。先ほどの A = 3, B = 10 の例で言うと x_{1} の値は12で、 x_{k+1} - x_{k} の値は9, 9, 12, 9, 9, 12, ... という値になります。 A 少なくなる時というのは、具体的には r_{k} + r_{1} \ge A である時です。

この2パターンについて、2通りの払い方がどのように変わるか考えます。

  • もし x_{k+1} - x_{k} = x_{1} であれば、 x_{k+1} の払い方は x_{k} と x_{1} の払い方をP, Qそれぞれそのまま合わせたものになります。
  • もし x_{k+1} - x_{k} = x_{1} - A であれば、 x_{k+1} の払い方は x_{k} と x_{1} の払い方をP, Qそれぞれ合わせたものに対して、払い方Pについて A 円を1枚、払い方Qについて1円硬貨を A 枚取り除いたものになります。

これはどちらも、 x_{k} と x_{1} の払い方を足したもの、あるいはその上で貪欲な払い方Qの枚数をより多く減らしたものになっています。よって x_{k} と x_{1} が条件を満たさないという仮定のもとでは、 x_{k+1} も条件を満たしません。

これで x_{1} が条件を満たさない場合は解がないことが示されたので、この値1つだけを試すことで答えを求めることができます。

ACコード

Aizu Online Judge Arena

AtCoder Beginner Contest 135 E - Golf

AtCoder プログラミング 競技プログラミング

E - Golf

解法

コの字の作り方を考えてみる

まずは考えやすい＆実装しやすいように座標変換をします。 X, Y に負の値がある場合、符号反転させて両方とも非負としておきます。

始点 (0, 0) から終点 (X, Y) までボールが移動する軌道は、長さの総和が K の倍数になっている必要があります。 X+Y が K で割り切れる場合は素直に最短距離を進めばよいです。そうでない場合はどこかで無駄な移動を挟まないといけません。ここで無駄に進んだぶんだけ必ず戻らなければいけないので、無駄な移動距離は必ず偶数である必要があります。

無駄な移動の取り方はどのようなものが良いでしょうか？色々なものが考えられますが、例えば以下のような軌道はほとんどの場合アウトです。

f:id:betrue12:20190728194707p:plain

1ステップでの移動が折り返すところをまたいでしまうと、そのステップの始点と終点のマンハッタン距離が K になりません。こうならないようなもの、イメージとしては「ヘアピンカーブが急でないもの」を考えたいです。

以下はどうでしょうか。コの字を作ります。

f:id:betrue12:20190728195610p:plain

さっきより良さそうです。しかしこちらの場合も、1ステップの移動がコの字の3辺にまたがってしまうとアウトです。3辺にまたがりにくくするためには、2本目に通る横向きの辺は長いほうが嬉しそうです。

そこでまた座標変換をします。もし X \lt Y であれば入れ替えて、常に X \ge Y ということにします。そして図の向きにコの字を作ると、2本目に通る辺を長い方にできます。

より具体的にステップ数や長さを決めていき、これで大丈夫なのか計算していきます。

コの字：具体的に計算

まずはステップ数を決めましょう。ステップ数を n とします。また D = X+Y と置きます。こうすると無駄な移動距離は nK - D と表せます。

もし単純な切り上げ、つまり n = \lceil\frac{D}{K}\rceil ステップで移動することができれば理想です。ただし n が以下の2つに当てはまる場合には実現できないので、その場合は n を増やします。

まずは \lceil\frac{D}{K}\rceil = 1 になるとき、1ステップでの移動は D = K である場合を除いて実現不可能です。この場合は n をひとまず2に増やします。

次に、無駄な移動距離は偶数である必要があります。もし nK - D が奇数になっている場合、もし K が奇数であればステップ数を1増やすことで偶奇が変わります。もし K が偶数であれば偶奇を変えることはできないので、 n がいくつであっても実現不可能です。

これらの条件に従って n を修正します。その結果、 \lceil\frac{D}{K}\rceil = 1 である場合は n=2, 3 のどちらかになり、そうでない場合は n = \lceil\frac{D}{K}\rceil, \lceil\frac{D}{K}\rceil + 1 のどちらかになります。

こうして決めた n に対して、先ほどのコの字が構築できないか考えましょう。

f:id:betrue12:20190728202016p:plain

図中の長さ a は無駄な移動距離の半分なので a = \frac{nK - D}{2} です。このとき、3辺にまたがるようなステップがないか確かめましょう。結論から書くと、これは \lceil\frac{D}{K}\rceil = 1 かつ n = 3 の時を除いて大丈夫です。それを証明します。

\lceil\frac{D}{K}\rceil = 1 かつ n = 3 の時以外は n \le \lceil\frac{D}{K}\rceil + 1 \lt \frac{D}{K} + 2 なので、 a \lt K が成り立ちます。そのため終点側から辿ると、必ず1ステップで右の辺は通り越して上の辺に掛かります。

ここで右の辺と上の辺の長さ合計が K 以上であれば、左の辺に掛からないので大丈夫だと示せます。実際に計算すると a + X = \frac{nK + (X-Y)}{2} となり、座標変換で X \ge Y を保証したことと n \ge 2 であることから a+X \ge K が示されます。

これで \lceil\frac{D}{K}\rceil = 1 かつ n = 3 の時を除いて構築可能であることが示されました。あとはこれを何とかします。

最後の詰め

\lceil\frac{D}{K}\rceil = 1 ということは D \lt K なので、終点までの距離よりも1ステップの移動距離が大きいということです。このような時に合計3ステップで移動しようとすると、確かに以下のような動きになってヘアピンカーブをまたぐ可能性があります。

f:id:betrue12:20190728204914p:plain

これを何とかします。直感的には縦方向に伸びすぎているので、横方向にも回り道をしてみます。

f:id:betrue12:20190728205415p:plain

縦横それぞれに無駄な動きの長さがあるので、 a + b = \frac{3K - D}{2} となります。これを、3辺をまたぐステップがないように a, b に割り振ります。

先ほどと同じく、辺の長さに関する不等式を示していきましょう。始点終点それぞれから見て、図のように1ステップ目が2本目の辺の途中（両端含む）で終わることを確かめます。すなわち始点側について b \le K \le b+Y+a 、終点側について a \le K \le a+X+b が成り立っていればよいです。

b \le K かつ a \le K については、 \frac{3K - D}{2} をほぼ等分に a, b に分けることによって成り立ちます。そして K \le b+Y+a かつ K \le a+X+b については、 D \lt K であることから a + b = \frac{3K - D}{2} \gt K が言えるので成り立ちます。

以上でこの構築が可能であることが示せました。

これで構築が不可能であるケースに対してはその証明を、可能であるケース全てに対しては具体的な構築方法とステップ数 n の最適性の証明を与えることができました。あとは場合分けや座標計算を間違えずに書けば解くことができます。

ACコード

Submission #6597616 - AtCoder Beginner Contest 135

AtCoder Beginner Contest 134 F - Permutation Oddness

AtCoder プログラミング 競技プログラミング

F - Permutation Oddness

※問題文で与えられている n, k は小文字ですが、 k を添え字として使いたいので本記事では N, K と表記します。

解法

順列のDP

順列の場合の数を求める問題です。何か条件を満たす数列の個数を求める問題として「左からDP」というのはメジャーな解法ですが、順列の場合は各数字をちょうど1回しか使えないという性質のためDPがやりにくいです。例えば

  • dp\lbrack i \rbrack\lbrack S \rbrack\lbrack k \rbrack = 左から i 番目の場所まで決めて、既に使った整数の集合が S で、それまでの奇妙さの合計が k である場合の数

みたいなのを考えてDPすることは一応できるのですが、これは結局bit DPなので N が大きいと状態数が爆発してしまいます。

なので順列の数え上げについては、

  • そもそもDPしない、数学などでがんばる
  • 使った整数の集合を具体的に覚えておかなくていいDPを組む

などの工夫が必要になります。後者として例えば挿入DPがあり、これはDPで持つ情報を「数の集合」ではなく「ある条件を満たす場所の個数」として持つようなDPです。このように何かの「個数」で状態を持つことができれば状態数を抑えることができます。

今回の問題も、そのような方針でDPを組むことができます。

箱根駅伝DP

この問題に由来して、俗に「箱根駅伝DP」と呼ばれているテクニックです。

整数 1, ..., N までの各整数について、以下のように「箱」と「ボール」を考えます。最初にそれぞれの箱に、仮で同じ番号のボールを入れておきます。

f:id:betrue12:20190721134037p:plain

この箱とボールの組を左から見ていきながら、箱にボールを入れたり入れなかったりします。まず最初の箱1＋ボール1については、

  • 箱1にボール1を入れる。
  • 箱1にボール1を入れない。ボール1が「保留ボール」として残り、箱1も「保留箱」として残る。

の2パターンがあります。

次の箱2＋ボール2について。もし箱1にボール1を入れていた場合は全く同じ2パターンを考えれば良いですが、保留があった場合には事情が異なります。つまり上の2パターンに加えて、

  • 箱2に保留ボール1を入れて、ボール2を保留にする。
  • 箱2に保留ボール1を入れて、保留箱1にボール2を入れる。
  • 箱2を保留にして、ボール2を保留箱1に入れる。

の3つ、合計5パターンがあります。

この遷移をDPで扱っていきます。このとき保留にしているボールや箱を集合で持つとやっぱり状態数が爆発しますが、これを「個数」だけで上手く扱います。保留しているボールと箱の個数は等しいので、

  • dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack = 左から i 番目の場所（箱＋ボール）まで見終わって、保留しているボールと箱の個数がともに j 個で、それまでの（？）奇妙さの合計が k である場合の数

というDPを考えることができます。順列が完成しているときにはもちろん保留がゼロなので、答えは dp\lbrack N \rbrack\lbrack 0 \rbrack\lbrack K \rbrack として求められるでしょう。

先ほどの5パターンについて、遷移にかかる係数と j の増減はそのまま求めることができます。保留箱や保留ボールを選ぶたびに場合の数には j 倍の係数が掛かり、パターンによって遷移後の j が j-1, j, j+1 のいずれかになります。以下の図で列挙します。

f:id:betrue12:20190724013018p:plain

ただ1つ困ったことがあり、それは図中でも?と記載している k の更新です。箱にボールを入れた時に奇妙さを直接足そうとすると、箱とボールの具体的な数字が分からないと求められません。その扱いを詰められればゴールです。

奇妙さ k の更新

k の更新ですが、イメージは i を1個進めるたびに奇妙さを「積み立てておく」感じです。具体的に説明します。

保留ボールとしてボール x 、保留箱として箱 y があったとします。そしてDPにおいて、 i 番目の場所を見ているものとします。ここで x \lt i かつ y \lt i です。

ここでもし箱 i に保留ボール x を入れれば奇妙さは i-x 増えます。また、保留箱 y にボール i を入れれば奇妙さは i-y 増えます。これらは「今入れたときに増えるはずの奇妙さ」です。

しかしここでどちらも入れなかったとしましょう。そして見ている場所を i+1 番目にずらすと、さきほどの「今入れたときに増えるはずの奇妙さ」はそれぞれ1ずつ増えることになります。

このように、箱やボールが保留されている状態で見ている場所をずらすたびに奇妙さを1ずつ足していくのが「積み立て」の考え方です。つまり保留箱と保留ボールがともに j 個の状態で見ている場所 i を1つずらすときに、奇妙さ k に 2j を加算してしまうことで、奇妙さの合計を正しく管理することが出来るのです。

場所 i を見ているときにボール i や箱 i を保留にしても、その時点では「今入れたときに増えるはずの奇妙さ」は0なので特に足す必要はありません。つまり先ほどの図で?と記していた遷移先の奇妙さの値は、全て k+2j とすることができます。先ほどの図に合わせて言えば、見る場所を i-1\to i とずらしたときに増える分ということになります。

これで全ての遷移が完成しました。状態数 O(N^{2}K) であり、遷移は高々5パターンなので全体計算量も同様のオーダーになります。

ACコード

Submission #6465496 - AtCoder Beginner Contest 134

AtCoder Regular Contest 052 D - 9

AtCoder プログラミング 競技プログラミング

D - 9

公式Editorialと違う解法で解いたので記録。

計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした…

解法

まず桁DPを考えました。以下のように状態を考えることができます。

dp\lbrack i \rbrack\lbrack k \rbrack\lbrack d \rbrack\lbrack l \rbrack = 上から i 桁目までの数字まで決めて、そこまで決めた値を K で割った余りが k で、そこまでの桁和を K で割った余りが d で、上限値 M より小さいことが確定している（ l=1）/いない（ l=0）ような場合の数

これで桁DPできます。状態数は

  • i ： M が最大11桁なので初期状態含めて12通り
  • k： K で割った余りなので K 通り
  • d：これも K で割った余りなので K 通り…と思いきや、 10^{10} 以下の非負整数の桁和は最大90なので \min(K, 91) 通り
  • l：2通り

です。1状態あたりの遷移は桁1つの数字の取り方で高々10通りなので、高速な言語に限れば K \le 10^{4} くらいまでなら通る見込みがあります。 (12\times 10^{4}\times 91\times 2 \times 10 = 2.184\times 10^{8})

ただし制約は 1 \le K \le M \le 10^{10} であり、 K が大きいときには破綻します。そこで、 K が大きいときには M \div K の商が小さいことを利用します。

M \div K の商を q 、余りを r とします。さきほど見たように桁和は90以下なので、 r としてもこの範囲しか調べる必要はありません。 K \gt 10^{4} であれば商 q としてとり得る値は高々 10^{6} 通りなので、 (q, r) を全探索します。こちらも速い言語でないと厳しいですが何とか通ります。

ACコード

Submission #6437619 - AtCoder Regular Contest 052

CPSCO2019 Session2 E - Mogu Mogu Gummi

AtCoder プログラミング 競技プログラミング

お題箱より。

E - Mogu Mogu Gummi

解法

木DPを考えてみる

「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。

シンプルなグラフを例にして考えてみましょう。頂点0が根です。

f:id:betrue12:20190719005533p:plain

このグラフにおいて、 H_{2} や H_{3} の辺を切ろうとして頂点2や3を操作するときには必ず H_{1} の辺がダメージを受けます。その途中で H_{1} の辺のほうが切れてしまった場合、もうそれ以上頂点2や3は操作できません。

上側の辺が切れてしまうともう下側を操作できない…と考えると、例えば頂点1に注目したときには「なるべく上の辺 H_{1} に与えるダメージを少なくしつつ、下側の辺 H_{2}, H_{3} を多く切りたい」という気持ちになります。これを元に以下のようなDPを考えます。

  • dp\lbrack i \rbrack\lbrack j \rbrack = 頂点 i 以下の部分木で辺を j 本切るために必要な、頂点 i から根までの辺に与える最小のダメージ

ここでは最小のダメージしか覚えておく必要はありません。ダメージが小さいぶんには、頂点 i 自身を操作することでダメージを追加で与えることができるからです。

例えば上の図において頂点1についてこのDPを考えると、

  • dp\lbrack 1 \rbrack\lbrack 0 \rbrack = 0
  • dp\lbrack 1 \rbrack\lbrack 1 \rbrack = \min(H_{2}, H_{3})
  • dp\lbrack 1 \rbrack\lbrack 2 \rbrack = H_{2} + H_{3}

こんな感じです。

遷移を詰める

より一般的にDPの遷移を詰めていきます。

頂点 i についてのDPの値を求めるときには、まず頂点 i を頂点数1の木とみなし dp\lbrack i \rbrack\lbrack 0 \rbrack = 0 とします。その他の j については dp\lbrack i \rbrack\lbrack j \rbrack = \infty としておきます。 \infty はその部分木で辺を j 本切るのが不可能であることを示します。ここに1つずつ子の情報をマージしていきます。

親頂点を i 、子頂点を c とします。親側で既に切っている辺の本数 j_{i} と子側で既に切っている辺の本数 j_{c} の組み合わせそれぞれについて遷移を試します。

f:id:betrue12:20190719021136p:plain

このとき遷移のパターンとしては、

  • dp\lbrack c \rbrack\lbrack j_{c} \rbrack \gt H_{c} のとき：これは c 以下で操作をしている途中で H_{c} の辺が切れてしまうことを意味する。そのため、そもそもこの遷移は不可能。
  • dp\lbrack c \rbrack\lbrack j_{c} \rbrack \le H_{c} のとき、以下の2つがあり得る：
    • H_{c} の辺を切らない：切った辺の本数が j_{i} + j_{c} になり、 H_{i} には合計で dp\lbrack i \rbrack\lbrack j_{i} \rbrack + dp\lbrack c \rbrack\lbrack j_{c} \rbrack のダメージが入る。
    • H_{c} の辺を切る：切った辺の本数が j_{i} + j_{c} + 1 になり、 H_{i} には合計で dp\lbrack i \rbrack\lbrack j_{i} \rbrack + H_{c} のダメージが入る。

このようにすればマージ後のDPテーブルを計算できます。同じ (i, j) に対して複数の遷移が来た場合にはダメージが少ない方を採用すれば良いです。

このDPを根0まで計算します。そうすると最終結果である dp\lbrack 0 \rbrack\lbrack j \rbrack は、「 dp\lbrack 0 \rbrack\lbrack j \rbrack \ne \infty のときは、木全体で辺を j 本切ることが可能である」と捉えることができます。これで答えを求めることができます。

「二乗の木DP」の話

今回組んだDPは、実装を適切にしてあげると全体計算量 O(N^{2}) で動作します。通称「二乗の木DP」と呼ばれているものです。

こちらの記事で計算量解析がされていますが、まずは知識として覚えてしまって良いと思います。適用できる問題の特徴として、以下の点が挙げられます。

  • 木DPのテーブルに、どの頂点まで見たかだけでなく「頂点や辺の個数」に関するようなインデックスがある。
  • 遷移において子を1つずつマージする際に、さきほどの「頂点や辺の個数」を親子それぞれについて回す2重ループがある。
  • 実装においてこの2重ループを毎回 N や N-1 まで回すのではなく、その部分木のサイズまでしかループしないようにすることができる。

つまりDPの状態を「頂点 i 以下の部分木で、○○な頂点が j 個であるときの△△」や「頂点 i 以下の部分木で、○○な辺が j 本であるときの△△」のように取れる時に適用しやすいです。このようなDPが組めて、かつ制約上 O(N^{2}) が許容されそうであれば、二乗の木DPを疑ってみましょう。

ACコード

Submission #6435777 - CPSCO2019 Session2

変数名はある程度は上記の解説に合わせています。再帰関数の中でコメントを付けているところが二乗の木DPのキモで、どの問題でも割と似たような実装になるので慣れておくと良いと思います。

細かい実装上の注意として、子をマージするときに dp\lbrack i \rbrack から dp\lbrack i \rbrack を更新するような格好になるので、遷移元と遷移先が混ざらないようにしないといけません。例えばナップサックDPを一次元配列でやろうとする時と似たような注意が必要です。

単純なのは上記コードのように別途一時配列を用意して遷移先をそっちに書き、後でコピーする方法。または今回の遷移であれば j_{i}, j_{c} についてループの方向を逆順にすることで一時配列なしで上手くできたりしますが、慣れないうちは混乱しにくい前者がオススメです。

天下一プログラマーコンテスト2016予選A　B - PackDrop

AtCoder プログラミング 競技プログラミング

お題箱より。

B - PackDrop

解法

まずは問題をシンプルに

0.99^{n} みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。

ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付き木になります。子機器を持たない M 台の機器は葉であり、機器0から各葉 B_{i} への到達率が 0.99^{C_{i}} と指定されています。

間に複数辺がある場合の到達率を考えましょう。仮に機器0と葉 B_{i} の間に直列に辺が2本あり、それぞれPackDropが a 個、 b 個含まれているとします。このときそれぞれの辺における到達率は 0.99^{a} と 0.99^{b} であり、機器0と葉 B_{i} の間の到達率は問題文より掛け算になるので 0.99^{a} \times 0.99^{b} = 0.99^{a+b} となります。これは指数法則によるものであり、辺の本数が3本以上になっても同様のことが成り立ちます。

f:id:betrue12:20190713162811p:plain

つまり機器0から各葉 B_{i} への到達率を 0.99^{C_{i}} にしたいのであれば、経路上の辺に含まれているPackDropの個数を全て足し算したものを C_{i} にすることが必要十分となります。これで 0.99^{n} のようなものを考えずに問題を言い換えることができます。

  • 頂点0を根とする頂点数 N の根付き木が与えられる。
  • それぞれの葉 B_{i} について、頂点0からの「距離」 C_{i} が指定されている。
  • 上記距離を満たすように、各辺に非負整数値の「長さ」を割り当てる。（元々、PackDropの個数だったもの）
  • 全ての辺の長さ合計を最小にしたい。その最小値はいくつか？

これで整数で考えられるグラフの問題になりました。

最小値の求め方を考える

実際にどのような割り当て方をすれば長さ合計を最小にできるのか考えてみます。

シンプルな例として、以下のグラフを考えてみましょう。

f:id:betrue12:20190713165429p:plain

これを実現する長さの割り当て方として以下のようなものが考えられます。

f:id:betrue12:20190713165439p:plain

これらは全て条件を満たしていますが、辺の長さ合計が違います。この例を見ると、できるだけ根に近いところに長さを大きく割り当てたほうが長さ合計を節約できそうです。

これはより複雑なグラフでも一般的に成り立ち、根に近いところに長さをできるだけ大きく割り当てるのが常に最適です。図の左側のように根以外の頂点から下に伸びる辺が全て正の重みを持っている場合は、図の右側のように上の辺に移すことで条件を満たしたまま長さ合計を減らせる（少なくとも増えはしない）からです。これはグラフが根付き木であることから成り立ちます。

そのため根に近いところから順番に辺の長さを決めていって、それぞれの長さは許される最大値まで割り当てることにしましょう。その辺の下にいる葉について、葉と根の距離が与えられた値 C_{i} を超えてはいけないので、それを超えないギリギリまで取ります。つまり辺の長さは、

(その辺の下にいる葉についての C_{i} の最小値) - (根からその辺までの距離)

として決めることができます。

あとはこれを実際に計算していきます。各辺について、その辺の下にいる葉についての C_{i} の最小値を求めておかないといけないので、これは下から順番に木DPのように求めておきましょう。それを予め求めた後で、辺の長さは上から順番に決めていきます。実装上は2回DFSをすることになります。

ACコード

Submission #4570032 - 天下一プログラマーコンテスト2016予選A