数え上げ その1「状態をまとめる」

DEGwerさんの数え上げテクニック集を読んで自分のコメントを追加していく。

 

何かを作っていく方法の個数を数える問題や、グリッドに色を塗っていく問題など、単純な全探索アルゴリズムで終端状態まで到達した場合の数がそのまま数えたい値となる場合は、DP を「全探索の高速化」として見ることができます。

 

まずは、紹介されている問題を見てみる。

F - バイナリハック / Unhappy Hacking

これはある文字列を作る方法の数を数える問題。計算量を無視すれば、全探索をして、はじめの状態から終端状態までのパスが何通りあるかを数えればいい。ただ、単純な全探索ではもちろん間に合わないので、上手いこと状態をまとめて全探索を高速化してやるのが基本的な方針となる。

 

状態をまとめられる条件としては、

・遷移先の状態が同じである

・遷移につく係数が同じである

・各状態について、そこにまとめられた状態のすべてが問題文の条件を満たすか、すべてが満たさないかのいずれかである

 

という3つの条件が挙げられている。

先ほどの問題で言えば、例えば「k回操作をして文字列がsになっている状態」を全てまとめることにすると、これは3つの条件を満たすことがわかる(これではまだまとめきれていないが)。

 

条件をもう少し理解するため次の問題も見てみる。

F - Road of the King

作っている途中のグラフは、強連結成分を潰して1つの頂点と見なしたとき、直線グラフにいくつかの孤立点を加えた形のグラフになることがわかる。直線グラフが1点に潰れるのは、最初の強連結成分内の頂点に帰ってきたときだけである。

f:id:Div9851P:20190211223323p:plain

 そうすると、出来る移動は本質的に以下の3パターンにわかれることになる。

1.孤立点に行く(孤立点が減る)

2.最初の強連結成分に含まれる頂点のうちどれかに行く(最初の強連結成分のサイズが大きくなる)

3.それ以外の頂点に行く(何も起きない)

遷移につく係数が孤立点の数と強連結成分のサイズで決まることを考えるとこれらは状態として持たないといけない(まとめられる条件2より)ので、「n回移動して、孤立点がx個あり、最初の強連結成分のサイズがyであるような場合の数」としてDPが出来る。

 

 

・まとめ

もちろん問題固有の考察は必要となるが、状態をまとめられる条件を意識すると、考察が進めやすい。

みんなのプロコン F 「Pass」

問題文

F - Pass

 

まず、2N個のボールを全て区別し、最終的にそのボールが列の前から何番目に並ぶかを割り振っていくことにする(ボールには1から2Nまでの番号がつく)。

そうすると、そのような並べ方が出来るためには、番号の割り振り方に制約があることに気づく。それは1≦i≦Nについて、番号iが割り振られたボールは、前からi人目までのすぬけ君が持っていないといけないということ。何故なら、ボールは1回の操作で高々1つしか前に進まないので、i人目よりうしろの人が持っていると間に合わないからである。

逆に、この制約を満たしているなら、持っているボールのうち番号の小さい方のボールを前の人に渡すことにすれば割り振った通りの順番で並べることが出来る。

f:id:Div9851P:20190210213542p:plain

ここで、赤青赤赤青...のような長さ2Nの列Aがあったとき、最終的にこの列になることがあり得るか、という判定問題を考えてみると、任意のi(1≦i≦2N)について、「Aのi番目までに出てくる赤の個数が前からmin(i,N)人目までのすぬけ君がもっている赤の個数以下」かつ「Aのi番目までに出てくる青の個数が前からmin(i,N)人目までのすぬけ君がもっている青の個数以下」であればいいということが、最初の考察からわかる。

よって「dp[i][j]=前からi番目までのあり得る色の決め方で、赤がj個出てくるようなものの個数」というDPをすることで解ける。

 

みんなのプロコン2019 E 「Odd Subrectangles」

問題文

E - Odd Subrectangles

 

以下、和は全てmod 2で考える。

選んだ行集合をA、列集合をBとしたとき、Aに含まれる行とBに含まれる列が交わっているマスに書かれた数の和をf(A,B)と書く。f(A,B)=1となるA,Bの選び方が何通りあるかを数えたい。

列集合Bを固定する。そうすると、Bに含まれる列と交わっているマスに書かれた数の和が1の行と0の行に分かれる。ここで、和が1の行が1つでもあれば、その行を選ぶとf(A,B)が反転するので、f(A,B)=0となるAの選び方と、f(A,B)=1となるAの選び方は同数存在することになる。一方、和が0の行しかない場合は、常にf(A,B)=0である。

ということは、和が0の行しかないようなBの選び方がx通りあるとすると、(2^(N+M)-x)/2で答えが求まることがわかる(余事象)。

さて、ここでi番目の列を選ぶならx[i]=1、選ばないならx[i]=0としたM次元ベクトルxを考えると、和が0の行しかないというのは、与えられた行列をAとしてAx=0と言いかえることが出来る。よって、Ax=0を満たす解の個数を数える問題に帰着された。

ここで、AをK上のN×M行列としたとき、連立1次方程式Ax=0の解空間 W={x∈K^M|Ax=0} の次元は dim(W)=M-rank(A) と表されることが知られているので、AのランクrがわかればWの次元がわかる。

Wの次元をdとすると、Ax=0の任意の解は、あるd個のベクトルの線形結合で表されることになる。今、係数は0か1なので、解は2^d個ある。

したがって、Aのランクをrとしたとき答えは(2^(N+M)-2^(N+M-r))/2=2^(N+M-1)-2^(N+M-r-1)と表されることがわかった。

AtCoder Regular Contest 094 F 「Normalization」

問題文

F - Normalization

 

a→0,b→1,c→2とすると、x,y(x≠y)をxでもyでもない数に置きかえるという操作はx,yを3-(x+y)で置きかえる操作と言いかえられる。このことから、この操作をしても数列の和を3で割った余りは不変であることが示せる。

したがってSからT(|S|=|T|,T≠S)に出来るための必要条件は「sum(S)%3==sum(T)%3」であることがわかるが、実はいくつかの例外をのぞいて十分条件にもなっている。

まず明らかな例外として、Sに含まれる文字が1種類(操作が1回も出来ない)のときと、Tに同じ文字が連続した箇所がない(操作の結果としてこのような文字列が出来ることはない)のときがある。

これらでほとんどの場合をカバーできているが、実験をすると|S|≦3のときは答えがずれるケースがあることがわかるので、この場合も弾く。

そうすると結局「Sに含まれる文字が1種類のとき答えは1」「|S|≦3のとき全探索して答えを求める」「それ以外のとき、長さが|S|で、和を3で割った余りがSと等しく、同じ数が連続した箇所があるような数列を数えればそれが答え」とわかり、3番目はDPで簡単に計算できるので解けた。

AtCoder Regular Contest 096 F 「Sweet Alchemy」

問題文

F - Sweet Alchemy

 

d[i]=c[i]-c[p[i]](ただしd[1]=c[1])とする。これを用いると、この問題は

・「頂点iを根とする部分木に含まれる各頂点についてドーナツを1個作る操作」をd[i]回行う

・ただし0≦d[1]かつ2≦i≦Nであるようなiについて0≦d[i]≦D

とき、上手くdを決めてドーナツの個数を最大にする問題になる。

これは、「部分木に含まれる頂点数」を価値、「部分木に含まれる頂点についてのmの和」を重さとしたアイテムがN種類あり、重さの合計がX以下となるようアイテムを選ぶときの価値の合計の最大値を求める問題なので、ナップサック問題に帰着された。

すこし一般的に書くと以下のようになる。

・N種類のアイテムがあり、i種類目のアイテムの重さはW[i]、価値はV[i]で、C[i]個まで選べる

・重さの合計がX以下となるようアイテムを選んだとき、価値の合計の最大値はいくつか?

・ただしN≦50,V[i]≦50で、それ以外は大きい

今回は重さの合計も価値の合計も大きくなり得るのでよく知られたDPをそのままやる訳にはいかない。

そこで、最適解がどのような形になるか考える。基本的にはV[i]/W[i]が大きい方から選んだ方が良さそうなので、V[1]/W[1]≧V[2]/W[2]≧...≧V[N]/W[N]を満たすようにソートしておく。

そうすると以下のようなことがわかる。

・p<qであるとき、pが50個以上余っていて、qを50個以上選んでいるなら、qをV[p]個捨ててpをV[q]個増やすことで価値を変えないまま重さを減らすことが出来る

よって最適解においては、このような状況は起きていないとしてよいので、最適解は次の図のような形に限られることがわかる(真ん中にどちらでもない領域が挟まっていてもいい)。したがって、左側についてDPをして価値の合計がYとなるときの重さの合計の最小値Xを求め、各Yについて右側を貪欲に取っていけば答えが求まる。

 

f:id:Div9851P:20190209124957p:plain

難しかったが、大体貪欲で、細かい所をDPというテクは汎用性がありそうなので覚えておきたい。

 

AtCoder Regular Contest 101 F 「Robots and Exits」

問題文

F - Robots and Exits

 

まず次の2つのことがわかる。

・一番左の出口より左にいるロボットと、一番右の出口より右にいるロボットは無視してよい

・どのロボットも左にある一番近い出口か、右にある一番近い出口から出ることになる。

各ロボットを(左の出口までの距離,右の出口までの距離)というペアで表すことにして、これを二次元平面上にプロットする。今あるロボットを表す点を(X,Y)とする。そうすると結局、原点から始めて右か上に1ずつ進んでいったとき「先にx座標がXになる」ということが「ロボットが左の出口から出る」状況に、「先にy座標がYになる」ということが「右の出口から出る」状況に対応することがわかる。

※(左に最大いくつ動かしたか,右に最大いくつ動かしたか)という点を動かしていく

という訳で、以下の図のように線で平面を二分割して、左側から出るロボットと右側から出るロボットにわける方法が何通りか数えれば良くなったのだが、赤線の分割と青線の分割は本質的に同じなので、青線のような形の線だけを数えることにする。

f:id:Div9851P:20190208001343p:plain

さて青線は、進む向きを変える点たちで特徴づけられ、これらはx座標もy座標も単調増加でないといけないことがわかる。よって、平面上の点がN個与えられてx座標もy座標も単調増加になっているような点の選び方が何通りか数える問題になったので解けた。

AtCoder Regular Contest 103 F 「Distance Sums」

問題文

F - Distance Sums

 

木に辺u-vが含まれるとき、D[u]とD[v]にどんな関係があるかを考えると、辺u-vを取りのぞいて出来る2つの木のうち、uを含む方をA、vを含む方をBとするとD[u]=D[v]-|A|+|B|=D[v]+N-2|A|が成り立つことがわかる。・・・☆

D[1]<D[2]<...<D[N]と仮定しても一般性を失わない。頂点1を根とした木の、頂点1からある頂点までのパス1,p1,p2,...,pkを考える。そうすると、D[1]<D[p1]と☆よりp1を根とする部分木のサイズはN/2より小さいことがわかる。当然p2,p3,...,pkを根とする部分木のサイズもN/2より小さいから、結局D[1]<D[p1]<D[p2]<...<D[pk]となる。

したがって、1以外の各頂点は、自分よりDが小さい頂点を親に持つことがわかる。あとは頂点Nから順番に☆を使って親を決定していけばよい。

 

こういうときは最小・最大など極端な値をとるものに注目してみるのが定石っぽい。