裏紙

ほぼ競プロ、たまに日記

AOJ 1595 - Traffic Tree

問題

Traffic Tree | Aizu Online Judge

問題概要

頂点数nの木が与えられる(i(1 \le i \le n-1)番目の辺は頂点u_iv_iを結ぶ)。 隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。

  •  2 \le n \le 10^5

イデア

今回は、とある問題の想定解が全方位木dpだったので、その理解を多少はスムーズにできるように全方位木dp練習としてこの問題を解いた。

まずは、適当な根を決めて、根付き木とみなしてdfsをしながらその頂点に対する部分木の性質を得る。つまり、まずは0を根とした時のこの問題の解を求める。全ての頂点に訪れるという状況を考えると、根をスタート地点とするといくつかの部分木に分岐している。k個の分岐がある時、k-1個は分岐先に行って、全頂点を巡りまた根に戻ってくる必要があり、1個は分岐先に行って、帰ってくる必要はない(その部分木内の全頂点を訪れた時点でstopできる)。

よって、1回目のdfsではこの2つの値を各頂点に対する部分木に対して求める。それが pair<int,int> dp1[N]となっている。帰ってくる必要がある場合の最小コスト、ない場合の最小コストをペアで保存する。ある場合は一意に決まる(各部分木の"ある場合のコスト"+2(行き帰りの分)の和になる)。ない場合は、"ない場合"に該当させる部分木を1つ選び、それ以外は"ある場合に"該当させるので、"ない場合"に該当させる部分木を全探索してその最小値を取れば良い。

そうすると、この問題に対して0を寝とした場合の解は求めることができたことになる(dp1[0].second)。

次に、この問題を全頂点に対して解く。任意の頂点xに対して、上と同じようなことを考えたいとすると、先程の0を根とした木の上でxの部分木になっている部分についてはそのまま結果を利用してよいことになるが、新しく部分木として見なす必要があるのがxの親方面に1つ出来ていると見ることが出来る。この親方面にできる部分木の情報を、子に渡しながら1回目のdfsと似たようなことを2回目のdfsで行う。

親方面にできる部分木の情報をどう渡していくかということになるが、部分木の情報なので、同様にpairで渡していく("ある場合"、"ない場合"の それぞれのコスト)。今vにいて、次に進む子の方向が決まった時(nx)、0を根とした根付き木上でvの子になっているnx以外の部分木も、親方面にできる部分木の一員となるので、この情報を盛り込むことになる。

その調整をするために、「ある部分木を"ある場合"から"ない場合"に切り替えたらどれくらい得か」を計算しておくと、次に進む方向が一番得な方か否かで場合分けをして処理することが出来る。細かい内容はコメントで。

実装(C++)

続きを読む

CS Academy #57 - Binary Flips

問題

CS Academy

問題概要

N * Mのバイナリ行列Aがある。はじめ、行列の全要素は0である。この行列に対して、以下の操作をK回行う:

  • 行列のセル((i,j))を1つ指定し、i行目の全要素をバイナリ反転し、j列目の全要素を全要素をバイナリ反転する(よって、セル(i,j)は2回反転されるので変化しないことになる)。

操作をK回行った後に、値が1になっているセルの個数がS個になるような操作の方法は何通りあるか、10^9+7で割った余りを答えよ。

  • テストケース数 T \le 40
  •  1 \le N,M,K \le 3000
  •  0 \le S \le N * M

イデア

行に注目して、i行目に対して操作を行った回数の偶奇の値をR(i)、列に注目して、j列目に対して操作を行った回数の偶奇の値をC(j)と表すことにすると、A(i,j)=1となるには R(i) xor C(j) = 1 \Leftrightarrow R(i) \neq C(j)となることが条件になると言える。

まず、RCを独立にして考えてみる。

数列R (サイズ = N)に関して、dp[i][j] = i回操作を行った時に、1の個数がj個になるような操作の個数というものを考える。まず、初期値はdp[0][0] = 1で与えられる。

次に操作を起こる行に注目すると、0なら、1が1つ増えるので、0の個数を考慮するとdp[i+1][j+1] += dp[i][j]*(N-j)と配ることが出来る。逆に1の部分に対して操作をするならdp[i+1][j-1] += dp[i][j]*jと配ることが出来る。

RCに対して、このdp配列の前計算はそれぞれO(N^2)O(M^2)で行うことが出来る(それぞれの配列の名前をdr,dcとしておく)。

この前計算が終わってしまえば、あとは1になる行の個数と列の個数を全探索する(O(NM))。それぞれr_1行、c_1列あるとすると1になるセルの個数は、(どちらかが0でもう片方が1であれば良いので)r_1 * (M- c_1 ) + c_1 * (N - r_1 )個となる。これがSに一致する時のdr[k][r1] * dc[k][c1]を足し上げていけば良いことになる。

実装(C++)

続きを読む

CS Academy #53 - Parallel Rectangles

問題

CS Academy

問題概要

xy平面に点がn個与えられる。4点を選んで、それによって長方形を構成したいが、長方形のそれぞれの辺がx軸とy軸にそれぞれ平行になるようにしなければならない。 そのような4点の選び方は何通りあるか。

  •  1 \le n \le 10^5
  •  1 \le x_i , y_i \le 10^5

イデア

1つ目の方針として、 x_1を固定して、それ以外のx_2に対して、それぞれのx座標でy座標が共通で存在するの点((x_1 , Y)(x_2 , Y)という意味)がcnt(y)個あるなら、 _{cnt(y)} C _2通りの長方形を作れるということになる。これは、x座標の候補が多いと間に合わないのは明らか。

2つ目の方針としては、x座標を1つ固定する(Xとする)。そのx座標がXのものに対して、y座標のペアをmapによって数え上げる(++map[(y1,y2)]みたいに)。すると、その各ペアに対して、 _{map [(y_1 , y_2 ) ]} C _2 通りの長方形を作れるということになる。しかし、これは同じx座標上に点があるとペアの数が大量になってmapが抱えるkeyの数が大きくなってしまう。

この2つの方針を組み合わせることを考える。同じx座標にある点の個数で各x座標を2つのタイプに分ける:

  1. そのx座標に点がS個より多く存在
  2. そのx座標に点がS個以下存在

すると、長方形としてx座標を2つ選んだ時、そのx座標のペアは

  1. 両方がtype1
  2. type1とtype2
  3. 両方がtype2

のパターンに分類できる。パターン1と2は前者、3は後者で処理する。

前者に関しては、固定するx_1はtype1のx座標のみを考える。すると、type1の性質により、この固定するx_1はたかだか\frac{n}{S}個になる。そして、この固定した1つのx_1に対して、方針1はO(n)の時間がかかる。

後者に関しては、最悪の場合を考えると(S個もつx座標が大量にある状況)、mapが抱えることになるのは\frac{n}{S} * _S C _2個のkeyになる。

後者にはmapのlogが乗ることも考えると、S\sqrt{n}よりも小さくするのがバランスを取るためにはよい。今回はS=70を採用した。色々いじってみたけどギリギリすぎる(自分のコードがダメなのかもしれない...)

実装(C++)

続きを読む