Ccmmutty logo
Commutty IT
0 pv8 min read

ABC264 F-Monochromatic Pathの雑な説明(あたまのうごき)

https://cdn.magicode.io/media/notebox/f8813667-4a45-4284-a0c4-66f93757e441.jpeg

2022年8月17日

本日お日柄以下略
DPやってくヨ

保身

解説っていうか、頭の流れを書いてる感じなので厳密もくそもない。
でも解ければ正義の派閥なので良し。俺は強い。
4次元DP書くのが初めてなので、楽できるところ楽してないし、関数化とかもしていない。
ポエムなつもりで読んでね♡

ABC264 F- Monochromatic Path

[4次元DP]
  • 問題文のようなもの
    • H行W列のグリッドがある
    • 0行0列(0,0) から、 H-1行W-1列(H-1,W-1)に移動することを考える。
    • 各マスは0,1で構成されている。
    • 移動は同じ数字の間でしか移動できない
    でもって
    • 各行、各列に対してお金を払って0と1を反転することが出来る
    • 最小のお金で(0,0)->(H-1,W-1)への移動をしろ
  • 制約
    • マス目は2000×2000が最大
なるほどね同じ行や列に対して2回操作を行うのは無駄でしかないらしい。というのも2回同じ行に対して操作を行っても、その行の各マスは結局操作の前後で変化がなく、ただお金を払うだけだから
ということで、全探索的な解法が浮かんでくる。
  • 各行、各列は操作を行うか行わないかの2通り
  • じゃあBIT全探索でもしてみるか❓
    • 無理
    • 行が2000個、列が2000個の計4000個なので、240002^{4000}通りになってしまって、さすがに全探索は無理
  • ちょっと考えてみると、ある程度移動したとき、今いるマスより左上に対しての変更を行う操作はしなくていい
    • どういうことかっていうと、なんやかんやあって下のような盤面にできたとする
    • 000
      00(☆)0
      111
      111
    • この状態の盤面にして、今☆の地点(1,1)まで移動したとすると、0行目と0列目に対しては、もう操作を行わなくていい。ということが分かる。
      • 左や上への移動を行えないから、操作を行うだけお金の無駄、ということもあるが、
      • そもそも、左上への操作を行ってしまうと、「お前どうやって☆の位置まで移動してきたねん」みたいな感じになっちゃう
  • って感じで、以上のようなことを考えてみると、DP的解法が使えるんじゃないかな~っていうのが感覚で湧いてくる
  • DPで解くとして、DP[i][j]:=(i,j)まで移動するときの最小コストDP[i][j]:= (i,j)まで移動するときの最小コスト みたいな感じでやるのかなって思うけど、同じ行や列に対して2回操作を行うことはできない(しない)ので、行や列に対して操作を行ったかどうかっていうのもDPの状態として持たせないといけない
  • んじゃまあ、行と列の状態が欲しいから、2次元ぐらい増やせばいいのかな
  • DP[i][j][x][y]:=(i,j)まで移動するときの最小コスト。ただし、x=1の時、行iに対して操作を行っている。y=1の時列jに対して操作を行っている。DP[i][j][x][y]:=(i,j)まで移動するときの最小コスト。ただし、x=1の時、行iに対して操作を行っている。y=1の時列jに対して操作を行っている。
  • こんな感じでやればいけそうやな
    • xとyの取りうる値は2通りで、状態としては(x,y) = {(0,0), (0,1), (1,0), (1,1)}だけだよ
で、DPの定義はまあいいとして、これ遷移(移動)をどうやって行うかが難しそうだね
たとえば、(i,j,x,y) = (2,3, 0,0)だとして、これは2行3列にいて、2行目に対しても3列目に対しても操作を行っていないということになる。この状態からの移動を考える。
  • 縦の移動
    • つまり、マス(2,3)からマス(2,4)への移動
    • この時、仮にマス(2,3)とマス(2,4)の数字(0,1)が一致しているなら、移動すればいいです。
    • だけど、一致していないなら、マス(2,4)に対して操作を施さなければいけません。
      • その操作の方法ですが、制限があります。
        • 今、上から下に移動してきたので、列に対して操作を施すことはできません。
          • なぜか?
          • 仮に上が0,下が1だとして、0,1が一致してないからと言って、列に操作を施すと、上が1,下が0になってしまって、結局数字が異なるため、移動することができません
        • つまり、上から下へ移動するとき、上と下の数字が一致していないなら、行に対する操作をすることで移動しないといけません。
    • 以上をまとめて遷移を考えるとdp[i][j][x][y]からdp[i+1][j][x][y]dp[i][j][x][y]からdp[i+1][j][x'][y']への遷移先というのが分かってきそうな気がします。
    • 横に移動するなら行への操作をしてはいけない。縦に移動するなら列への操作をしてはいけない。
      • これを遷移式で書くと
      • まず縦
        • dp[i][j][0][0]>dp[i+1][j][1][0]dp[i][j][0][0]->dp[i+1][j][1][0]はおk(移動先の行に対する操作をすることでの移動)
        • dp[i][j][0][0]>dp[i+1][j][0][0]dp[i][j][0][0]->dp[i+1][j][0][0]はおk(移動先に操作しないで移動できる)
        • dp[i][j][0][1]>dp[i+1][j][0][1]dp[i][j][0][1]->dp[i+1][j][0][1]はおk(移動前で列に対して操作していて、移動後に列に対して操作するわけじゃないので別に問題ない)
        • dp[i][j][0][1]>dp[i+1][j][1][1]dp[i][j][0][1]->dp[i+1][j][1][1]はおk(これ分かりづらいかもしれないけどOKだよ)
      • ちょっと面倒になってきた。
        • こんな感じ
        • 可能な遷移先を書くとこんな感じ
        • 水色矢印について説明すると、縦の移動をすることで、移動前に行に対する操作を行っていたとしても、行が変わったので、移動後の行に対して操作が出来るようになった的なことを意味しています
    • 横の移動に対しても、同様に遷移を考えます。多分だけど、上下に伸びてる矢印が横向きになるだけ。
  • で、多分これくらい出来たら、なんとなく理解できているようなもんで、後は気合でDPをプログラムに起こしていけばいい。
  • プログラム全体のイメージだけど、
    • スタート位置が0の時、ゴール位置も0にしてゴールに向かうのがまず1個。この時のゴールまでの最小値をans1とする
    • スタート位置が1の時、ゴール位置も1にしてゴールに向かうのがもう1個。この時のゴールまでの最小値をans2とする
    • ans1,ans2のうち小さいほうを答えとして出力
  • まずdp[0][0][0][0]=0dp[0][0][0][0]=0が初期値
    • これが意味するのは、スタートマスに何も操作しないで行くときに、払うコストは0円
  • もう1個 dp[0][0][1][1]=R[0]+C[0]dp[0][0][1][1]=R[0] + C[0]も初期値
    • これが意味するのは、「(日本語で説明できないので略)」
  • 初期値こんな感じで、配るDPで書いてみる
  • とりあえず、経路をすべてS[0][0]S[0][0]の数字に合わせてゴールまで行く場合を書いてみる
    • 	int now = S[0][0]; //とりあえず、スタートマスの数字に合わせて移動する
      	rep(i,h){
      		rep(j,w){
      			bool same = (now == S[i][j+1]);//入力で与えられた盤面を見たとき、横の移動先はnowか?
      			bool same2 = (now == S[i+1][j]);//縦の移動先はnowか?
      			//ちなみに、移動前がnowと一致していることはDP的に保障されている。そういう風に実装している
      			rep(x,2){
      				rep(y,2){
      					// dp[i][j][x][y]からの遷移
      					//横の移動
      					if((same && x) || (!same && !x)){
      					// 移動先は目的の数字であるが、行に対する操作を施してしまっている。あるいは、移動先が目的の数字でなくて、行に対する操作もしていないというとき。
      					// 2パターンと言ったが、「要は横の移動先が移動前と数字が異なるとき」
      					//この2パターンは、列に対する操作でしかnowに一致させることが出来ないので、列に対する操作をする。(移動前に列に対する操作をしているかどうかは関係ないので、chmin(a,b)のbのyは0でも1でもおk
      						chmin(dp[i][j+1][x][1], dp[i][j][x][y] + C[j+1]);
      					} else {
      					// 移動の前後で数字が変わらないので、課金額0円で遷移可能
      						chmin(dp[i][j+1][x][0], dp[i][j][x][y]);
      					}
      					//縦の移動
      					if((same2 && y) || (!same2 && !y)){
      					//(縦の移動前後で数字が異なるとき)、移動先の行に対する操作でnowと一致させないといけない
      						chmin(dp[i+1][j][1][y], dp[i][j][x][y] + R[i+1]);
      					}else {
      						chmin(dp[i+1][j][0][y], dp[i][j][x][y] );
      					}
      				}
      			}
      		}
      	}
      	ll ans = INF;
      	rep(x,2)rep(y,2){
      		chmin(ans,dp[h-1][w-1][x][y]);
      	}
      //ansは候補の値的なイメージ
      
  • で、次は、S[0][0]S[0][0]じゃないふうに経路を作った場合の最小値も求める
  • DPテーブルの初期化をもう一回。
  • 	rep(i,2010)rep(j,2010)rep(x,2)rep(y,w)dp[i][j][x][y] = INF;
    	//dp[i][j][x][y]:= (i,j)
    	dp[0][0][0][1] = C[0];//S[0][0]じゃない方にするので、行に対する操作か、列に対する操作を最初のマスにしとかないといけない
    	dp[0][0][1][0] = R[0];
    	now = 1-now;
    
  • 	rep(i,h){
    		rep(j,w){
    			bool same = (now == S[i][j+1]);
    			bool same2 = (now == S[i+1][j]);
    			rep(x,2){
    				rep(y,2){
    					// dp[i][j][x][y]からの繊維
    					if((same && x) || (!same && !x)){
    						chmin(dp[i][j+1][x][1], dp[i][j][x][y] + C[j+1]);
    					} else {
    						chmin(dp[i][j+1][x][0], dp[i][j][x][y]);
    					}
    					if((same2 && y) || (!same2 && !y)){
    						chmin(dp[i+1][j][1][y], dp[i][j][x][y] + R[i+1]);
    					}else {
    						chmin(dp[i+1][j][0][y], dp[i][j][x][y] );
    					}
    				}
    			}
    		}
    	}
    	rep(x,2)rep(y,2){
    		chmin(ans,dp[h-1][w-1][x][y]);
    	}
    	cout << ans << endl;
    
    
    • 中身のコードはさっきと全く一緒なのでうえのコードは読まなくていい(多分)
  • 終わり

日記

今日は、ハンバーグを食いにインスタで見つけた店に行ったら、OPENと書かれているが品切れだった。
勘弁してくれ

Discussion

コメントにはログインが必要です。