AOJ 1595 - Traffic Tree
問題
Traffic Tree | Aizu Online Judge
問題概要
頂点数の木が与えられる(
番目の辺は頂点
と
を結ぶ)。
隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。
アイデア
今回は、とある問題の想定解が全方位木dpだったので、その理解を多少はスムーズにできるように全方位木dp練習としてこの問題を解いた。
まずは、適当な根を決めて、根付き木とみなしてdfsをしながらその頂点に対する部分木の性質を得る。つまり、まずは0を根とした時のこの問題の解を求める。全ての頂点に訪れるという状況を考えると、根をスタート地点とするといくつかの部分木に分岐している。個の分岐がある時、
個は分岐先に行って、全頂点を巡りまた根に戻ってくる必要があり、
個は分岐先に行って、帰ってくる必要はない(その部分木内の全頂点を訪れた時点でstopできる)。
よって、1回目のdfsではこの2つの値を各頂点に対する部分木に対して求める。それが pair<int,int> dp1[N]となっている。帰ってくる必要がある場合の最小コスト、ない場合の最小コストをペアで保存する。ある場合は一意に決まる(各部分木の"ある場合のコスト"+2(行き帰りの分)の和になる)。ない場合は、"ない場合"に該当させる部分木を1つ選び、それ以外は"ある場合に"該当させるので、"ない場合"に該当させる部分木を全探索してその最小値を取れば良い。
そうすると、この問題に対して0を寝とした場合の解は求めることができたことになる(dp1[0].second)。
次に、この問題を全頂点に対して解く。任意の頂点に対して、上と同じようなことを考えたいとすると、先程の0を根とした木の上で
の部分木になっている部分についてはそのまま結果を利用してよいことになるが、新しく部分木として見なす必要があるのが
の親方面に1つ出来ていると見ることが出来る。この
親方面にできる部分木の情報を、子に渡しながら1回目のdfsと似たようなことを2回目のdfsで行う。
親方面にできる部分木の情報をどう渡していくかということになるが、部分木の情報なので、同様にpairで渡していく("ある場合"、"ない場合"の
それぞれのコスト)。今にいて、次に進む子の方向が決まった時(
)、0を根とした根付き木上で
の子になっている
以外の部分木も、親方面にできる部分木の一員となるので、この情報を盛り込むことになる。
その調整をするために、「ある部分木を"ある場合"から"ない場合"に切り替えたらどれくらい得か」を計算しておくと、次に進む方向が一番得な方か否かで場合分けをして処理することが出来る。細かい内容はコメントで。
実装(C++)
続きを読むCS Academy #57 - Binary Flips
問題
問題概要
のバイナリ行列
がある。はじめ、行列の全要素は0である。この行列に対して、以下の操作を
回行う：
- 行列のセル(
)を1つ指定し、
行目の全要素をバイナリ反転し、
列目の全要素を全要素をバイナリ反転する(よって、セル
操作を回行った後に、値が
になっているセルの個数が
個になるような操作の方法は何通りあるか、
で割った余りを答えよ。
- テストケース数
アイデア
行に注目して、行目に対して操作を行った回数の偶奇の値を
、列に注目して、
列目に対して操作を行った回数の偶奇の値を
と表すことにすると、
となるには
となることが条件になると言える。
まず、と
を独立にして考えてみる。
数列 (サイズ =
)に関して、
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と配ることが出来る。
と
に対して、このdp配列の前計算はそれぞれ
と
で行うことが出来る(それぞれの配列の名前を
dr,dcとしておく)。
この前計算が終わってしまえば、あとは1になる行の個数と列の個数を全探索する()。それぞれ
行、
列あるとすると1になるセルの個数は、(どちらかが0でもう片方が1であれば良いので)
個となる。これが
に一致する時の
dr[k][r1] * dc[k][c1]を足し上げていけば良いことになる。
