2022年5月8日
[toc]
挨拶
こんぺこ 俺は大学を卒業して,就職したい。 就職・院進,どっち!なん!だい!!!
realforceのテンキー有買ったんだけど,レストがない。研究室で使ってるの1個あるけど,それ持って帰るのがめんどいし,サイズも小さいやつだから,もう1本の木パームレストほしい。
辞世の句
クソワロタ
学歴と共に
カス増える
競プロ
やったよ
ABC248 F- Keep Connect
[連結DP, 連結状態,がんばれ]
画像をアップロードするのめんどいから,PDFで解説読んでね。
- 校正してないから,遷移のとことか数字間違ってるだろ!みたいなのあるかも。わかんなかったらスクショTwitterに貼って,ここ理解できねえって感じで人に聞くといいよ
DPで解きます。連結DP初めてなので,厳密?とかそういうえらい人の解説を見たい場合は今すぐ帰れ。
- 今回のお題の 連結DPについて,僕なりに解釈を考えてみた
- 連結かどうかを状態として持ったDP
- i列目までが連結かどうかを状態として持ったDP
- 「i列目までが連結か」,と,「i列目までが現時点では連結ではないが,i+1列目以降で連結にできる可能性がある」状態を持ったDP
さて,解くぞ
DP[i][j][con] := i列目までの点を見て(つまり,2 * i個の点) j個の辺の辺を削除しているときに i列目の2点が何らかの経路でcon(1:連結)であるか,not con(2:繋がっていない)である ときの,j本の辺の消し方が何通りあるか。 **i列目の2点がconであるか,というのは,i列目の2つの点が何らかの経路で(ただし,i+1列目以降の点を経由しないで)繋がってあるかということです**(ツイートの1枚目の画像の左下の図を参照)
このように,DPの状態を定義します。
- (何本消すか,って言っていることからもわかるように,前提とする状態は,は3n+2本の辺がある状態です)
i列目を決めるときは,i-1列目とi列目をつなぐ2つの横の辺と,i列目の2点を繋ぐ縦の辺が1本の計3本ありますが,この3本のうちどれを削除するか,もしくはどれも削除しないか,みたいな感じで遷移を進めていきます。
雑補足をすると,上の定義のconは,「i列目の2点が何らかの経路でつながっているか」といいましたが,
僕の説明で遷移を作っていった場合には「i列目の2点が何らかの経路でつながっている」とき,「i列目までの2 * i 個の点がすべて何らかの経路でつながっている」。
(こうすることで,例えば: 5列目をDPで求めるとき,「あーでも,1列目の下の点が繋がってないから,つなげるようにしないとな」みたいなことを考えずに遷移を作れます。)
— 草 (@niboshi_wakai) May 7, 2022
遷移する際の注意点,つまり,i-1列目とi列目の間の辺を考えるときの注意点は,「連結にならない状態にしてしまわないように注意する」ってことです。多分
とりあえず,初期状態と,初期状態からの遷移を丁寧に見ていきます。
初期状態
まず,1列目だけは,プログラムで遷移を作るんじゃなくて,愚直に定義してしまおう。
1列目だけで考えると,1列目の2点の間に,辺があるか,無いかの二通りだけです。
- conである,は繋がっているってことね。
初期状態 1. dp[1][1][0] = 1 (1列目まで決めた。 ここまで1辺削除している 1列目の2点はnot conである) 2. dp[1][1][1] = 1 (1列目まで決めた ここまで,0辺削除している 1列目の2点はconである)
初期状態は,①と②の二通り。ここまでいいっすかね?
- 違いは,辺が1本あるかないかってだけだからまだ分かりやすいね
初期状態から,2列目を決めるときの遷移
ここから,ちょっとややこしくなってきます。というのも,2列目を決めるにあたって,3つの辺を考えないといけないんだよね
上の図は,状態①($dp[1][1][0]$ )の図だけど,状態②($dp[1][0][1]$ )の場合も一緒で,2列目(dp[2])を決めるっていうのは,a,b,cの3本の辺を決めるってことを意味しています。
状態①($dp[1][1][0]$ ),状態②($dp[1][0][1]$ )で分けて,遷移を考えていこう。
状態①($dp[1][1][0]$)からの遷移
a,b,cのうち,辺を何本消すかで分けて考えます(つまり,何本の辺を選ぶか)
0本の辺を消す場合(a,b,cの3本とも使う場合)
- 0本消す場合は こうっすね。見てわかるように,2列目の2点はconです。
- $dp[2][1][1] += dp[1][1][0]$
- $dp[i+1][j][1] += dp[i][j][0]$ (青い方は,i列目からi+1列目を考えるときなので,コード描く際に使うだけ。今は気にしなくていいよ)
1本の辺を消す場合(a,b,cのうち2本使う場合)
- 1本だけ消す場合は,3通りあります。こうっすね。
- 右の赤い二つのパターンですが。ダメです
- 真ん中は,左上の点が,右は,左下の点が孤立していることが分かりますね。
- 3列目,4列目…と辺を決めていったとしてもこの孤立点を連結に含めることは出来ないので,NGです。(遷移先として,赤い状態への遷移は発生しません)
- 左の青いパターンですが,OKです。
- 例えば,3列目で,a,b,cの位置の辺を全部取ってやれば連結にできます
- $dp[2][2][0] += dp[1][1][0]$
- $dp[i+1][j+1][0]+=dp[i][j][0]$
- (not con からnot conへの遷移。消す本数が1本だから,jが1増えるね)
- ①の状態から1本消す場合の遷移は,これだけです。
- 「1列目まで見たとき,1本の辺を消して,1列目の2点がnot conである状態」から,cの位置の辺をとらない選択をすると,「2列目まで見たとき,2本の辺を消し,2列目の2点はnot con」。である状態が作りだせます。
- (真上にある画像が3列目まであるのでちょっとわかりづらいね)
2本消す場合
- 遷移 無いです。
どの3つのパターンも,孤立が生まれるね
ここまでで,状態①からの遷移が終わりです。
状態②($dp[1][0][1]$)からの遷移
これだね,このa,b,cのうちどれを消すか(どれを取るか)を考える
- っていうかブルスクで落ちて5分ぐらいで書いたやつ消えたふざけんな。
①の時みたいな感じで,何本消すかで考えていく
0本消す場合。(3本とも使う場合)
- 直前で使った図と同じになるね。
- 今度は,1列目合わせて1本も辺を消していないから,j=0への遷移だね。
- もちろん2列目の2点は繋がってるから,con=1だよ
- $dp[2][0][1] +=dp[1][0][1] $
- $dp[i+1][j][1]+=dp[i][j][1]$
- (青い方は,コードを書くときに,i列目からi+1列目の遷移の式。今は気にしなくていいよ)
1本消す場合
こうっすね。
- どの1本の消し方もokだよ。
- 左の二つは2列目の2点がconであることが分かりやすいけど,一番右もconだから,注意してね
- 2列目上から,左,下,右っていけばたどり着ける
- 上の三枚とも,状態としては同じで,$dp[2][1][1]$っていうのが大事。(2列目まで決めて,辺を1本削除していて,2列目の上下が繋がっているっていう状態)
- あとおまけで補足。実は,状態①からの遷移で,この上の3枚の画像と同一視できる遷移(つまり$dp[2][1][1]$に行く遷移)があるから,確認するといいかも。
- 状態②から,3通りの辺の消し方で遷移できるってことで,遷移式は次のようになるよ
- $dp[2][1][1] += dp[1][0][1] \times 3$
- $dp[i+1][j+1][1]+=dp[i][j][1]\times 3$
- 1本だけ消す場合終わり~~
2本消す場合
こうっすねWWW
- 赤い場合だけダメです。
- 1列目と2列目が繋がっていないからです。
- これから3列目4列目…とどのように辺をつけていったとしても1列目と2列目は繋がりません。(っていうか,1列目と3,4列目も繋がりません)
- 青い場合はどっちもOKです
- これ,パッと見て,真ん中は右下が孤立,右は右上が孤立しそうだけど大丈夫なんすよね。
- こんな風にすればいい(線ずれたけど気にすんな)
- ただ,注意点として,2列目まで決めた段階では,右の二つのパターン,どっちもnot conだから注意してね。
- ってことで,状態はnot conに注意して遷移式は…
- $dp[2][2][0]+=dp[1][0][1] \times 2$
- $dp[i+1][j+2][0] += dp[i][j][1] \times 2$
3本消す場合
- 無理に決まってんだろバカ
ってことで,①と②の二つの初期状態からの遷移を見ていきました
3列目以降を決めるときですが,2列目を決めるときと同じようにすることが出来ます。
- というのも,2列目まで決めたとき,一番右の列だけ見ると,(1列目から2列目を決めたときの)1列目の状態と全く一緒だと考えることが出来るんです(全く一緒かは知らんけど,感覚)
後はコードを頑張って書いていけば,DPの遷移式君が勝手に求めてくれます
//初期状態二つ dp[1][0][1] = 1; dp[1][1][0] = 1; for(int i = 1; i < n; i++){ // i+1列目を決める。i列目とi+1列目の間の2辺と,i+1列目の2点の間の縦の辺をどうするか考える // 配るDPで考える(i列目の状態からi+1列目へ遷移する) for(int j = 0; j <= n-1; j++){ //ここのjの回す数は,まあノリ。 // j辺削除している状態からの遷移 for(int con = 0; con <= 1; con++){ if(con == 0){ //i列目の上下が繋がっていないときの遷移を書く } else { // i列目の上下が繋がっているときの遷移を書く } } } } // DP配列が完成した ans = 0; // この変数いらねえわ,草 for(int i = 1; i < n; i++){ cout << dp[n][i][1] << endl; //n列目まで見て,i辺削除したとき,n列目の2点が連結であるときの辺の削除の仕方が何通りあるかを出力する。(冒頭ちらっと書いたけど,遷移の仕方的に,n列目の2点が連結ってことは,1~n-1列目までも連結) }