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

2022年8月17日

保身

ABC264 F- Monochromatic Path

• 問題文のようなもの

  • H行W列のグリッドがある
  • ０行０列(0,0) から、　H-1行W-1列(H-1,W-1)に移動することを考える。
  • 各マスは0,1で構成されている。
  • 移動は同じ数字の間でしか移動できない

  でもって

  • 各行、各列に対してお金を払って0と1を反転することが出来る
  • 最小のお金で(0,0)->(H-1,W-1)への移動をしろ

• 提出コードC++(https://atcoder.jp/contests/abc264/submissions/34029832)
• 制約
  • マス目は2000×2000が最大

• 各行、各列は操作を行うか行わないかの2通り
• じゃあBIT全探索でもしてみるか❓
  • 無理
  • 行が２０００個、列が２０００個の計４０００個なので、$2^{4000}$通りになってしまって、さすがに全探索は無理
• ちょっと考えてみると、ある程度移動したとき、今いるマスより左上に対しての変更を行う操作はしなくていい
  • どういうことかっていうと、なんやかんやあって下のような盤面にできたとする

  • 0	0	0
    0	0(☆)	0
    1	1	1
    1	1	1

  • この状態の盤面にして、今☆の地点(1,1)まで移動したとすると、0行目と0列目に対しては、もう操作を行わなくていい。ということが分かる。
    • 左や上への移動を行えないから、操作を行うだけお金の無駄、ということもあるが、
    • そもそも、左上への操作を行ってしまうと、「お前どうやって☆の位置まで移動してきたねん」みたいな感じになっちゃう
• って感じで、以上のようなことを考えてみると、DP的解法が使えるんじゃないかな～っていうのが感覚で湧いてくる
• DPで解くとして、$DP[i][j]:= (i,j)まで移動するときの最小コスト$ みたいな感じでやるのかなって思うけど、同じ行や列に対して2回操作を行うことはできない（しない）ので、行や列に対して操作を行ったかどうかっていうのもDPの状態として持たせないといけない
• んじゃまあ、行と列の状態が欲しいから、2次元ぐらい増やせばいいのかな
• $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)}だけだよ

• 縦の移動
  • つまり、マス(2,3)からマス(2,4)への移動
  • この時、仮にマス(2,3)とマス(2,4)の数字（０，１）が一致しているなら、移動すればいいです。
  • だけど、一致していないなら、マス(2,4)に対して操作を施さなければいけません。
    • その操作の方法ですが、制限があります。
      • 今、上から下に移動してきたので、列に対して操作を施すことはできません。
        • なぜか？
        • 仮に上が0,下が1だとして、0,1が一致してないからと言って、列に操作を施すと、上が1,下が0になってしまって、結局数字が異なるため、移動することができません
      • つまり、上から下へ移動するとき、上と下の数字が一致していないなら、行に対する操作をすることで移動しないといけません。
  • 以上をまとめて遷移を考えると$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][0][0]$はおｋ(移動先に操作しないで移動できる)
      • $dp[i][j][0][1]->dp[i+1][j][0][1]$はおｋ（移動前で列に対して操作していて、移動後に列に対して操作するわけじゃないので別に問題ない)
      • $dp[i][j][0][1]->dp[i+1][j][1][1]$はおｋ（これ分かりづらいかもしれないけどOKだよ)
    • ちょっと面倒になってきた。
      • こんな感じ
      • 可能な遷移先を書くとこんな感じ
        
      • 水色矢印について説明すると、縦の移動をすることで、移動前に行に対する操作を行っていたとしても、行が変わったので、移動後の行に対して操作が出来るようになった的なことを意味しています
  • 横の移動に対しても、同様に遷移を考えます。多分だけど、上下に伸びてる矢印が横向きになるだけ。
• で、多分これくらい出来たら、なんとなく理解できているようなもんで、後は気合でDPをプログラムに起こしていけばいい。
• プログラム全体のイメージだけど、
  • スタート位置が0の時、ゴール位置も0にしてゴールに向かうのがまず1個。この時のゴールまでの最小値をans1とする
  • スタート位置が1の時、ゴール位置も1にしてゴールに向かうのがもう１個。この時のゴールまでの最小値をans2とする
  • ans1,ans2のうち小さいほうを答えとして出力
• まず$dp[0][0][0][0]=0$が初期値
  • これが意味するのは、スタートマスに何も操作しないで行くときに、払うコストは０円
• もう1個 $dp[0][0][1][1]=R[0] + C[0]$も初期値
  • これが意味するのは、「（日本語で説明できないので略）」
• 初期値こんな感じで、配るDPで書いてみる
• とりあえず、経路をすべて$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パターンと言ったが、「要は横の移動先が移動前と数字が異なるとき」
    					//この２パターンは、列に対する操作でしかnowに一致させることが出来ないので、列に対する操作をする。（移動前に列に対する操作をしているかどうかは関係ないので、chmin(a,b)のbのyは０でも１でもおｋ
    						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)){
    					//(縦の移動前後で数字が異なるとき)、移動先の行に対する操作で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]$じゃないふうに経路を作った場合の最小値も求める
• 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;
  
  

  • 中身のコードはさっきと全く一緒なのでうえのコードは読まなくていい（多分）
• 終わり

日記