kmjp's blog

競技プログラミング参加記です

AtCoder ARC #109 : F - 1D Kingdom Builder

ARC

白黒マスと白黒石の問題が嫌になりそうだ。
https://atcoder.jp/contests/arc109/tasks/arc109_f

問題

無限個のマスが1列並んでおり、それぞれ白黒で塗られている。
うち、Nマス分の白黒が指定される。（その両端の外側は、それぞれ白と黒のマスが無限個ある）

以下の手順で石を置いていく。

  • まず、置く石の白黒を決める。
  • 既存の石のあるマスの両隣に、置く石と同じ色の空きマスがあったら、そのいずれかに石を置く。
  • そのようなマスがなければ、置く石と同じ色の任意の空きマスに石を置く。

最低限石を置かなければならないマスが定められている。
最適な順で石を置くとき、その条件を満たすのに最低何個の石を置く必要があるか。

解法

石が置かれたマスの連結成分を増やすことができるのは、既存の石が置かれたマスの隣に、置きたい石の色のマスがない場合である。
そう考えると、置ける条件は以下のとおりである。

  1. 連結成分を白マスで始める場合、その白マスは両隣も白マスなところである。このパターンは最大1個しか存在し得ない。
  2. 連結成分を黒マスで始める場合、
    1. もともと黒マスの連結成分全体を埋め尽くす。このパターンは任意個可能。
    2. 単に黒マスで始める。このパターンは1個だけ可能。

あとは上記を白黒反転したものである。
上記をDPで求めて行こう。下記を頑張って状態遷移をかんがえていく。

dp(n,a,b,c) := 先頭nマスまで石を置く置かないを決めたとき、下記の状態で最低何個石を置くか

  • a: 1番目のパターンの開始白マスを使用済みである。
  • b: 2.2番目のパターンの開始黒マスを使用済みである。
  • c: nマス目の状態が
    • 石を置いていない
    • 1番目のパターンに属する石である
    • 2.2番目のパターンに属する石である
    • 2.1番目のパターンに属する石であり、
      • まだ黒マスの連結成分の左端マスを経過していない
      • 黒マスの連結成分の左端マスを経過したが、右端マスを経過していない
      • 黒マスの連結成分の右端マスを経過した
const ll mo=998244353;

int N;
string S,T;
int dp[101010][2][2][6]; //a1, a2a2a2, a3, none

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>T;
	N+=6;
	S="www"+S+"bbb";
	T="___"+T+"___";
	int ret=1<<20;
	FOR(k,2) {
		memset(dp,0x3f,sizeof(dp));
		dp[0][0][0][5]=0;
		for(i=1;i<=N;i++) {
			if(S[i-1]=='w') {
				// take a1
				if((i==1||S[i-2]=='w')&&(i<N&&S[i]=='w')) {
					FOR(y,2) {
						dp[i][1][y][0]=min(dp[i][1][y][0],dp[i-1][0][y][0]+1);
						dp[i][1][y][0]=min(dp[i][1][y][0],dp[i-1][0][y][5]+1);
					}
				}
				// new section
				FOR(y,2) dp[i][0][y][0]=min(dp[i][0][y][0],dp[i-1][0][y][5]+1);
				FOR(x,2) FOR(y,2)	dp[i][x][y][1]=min(dp[i][x][y][1],dp[i-1][x][y][5]+1);
				FOR(x,2) dp[i][x][0][4]=min(dp[i][x][0][4],dp[i-1][x][0][5]+1);
				// keep
				FOR(x,2) FOR(y,2) FOR(j,5) dp[i][x][y][j]=min(dp[i][x][y][j],dp[i-1][x][y][j]+1);
				if(T[i-1]=='_') {
					//keep empty
					FOR(x,2) FOR(y,2) dp[i][x][y][5]=min(dp[i][x][y][5],dp[i-1][x][y][5]);
					// a1->empty
					FOR(y,2) dp[i][1][y][5]=min(dp[i][1][y][5],dp[i-1][1][y][0]);
					// a2->empty
					FOR(x,2) FOR(y,2) dp[i][x][y][5]=min(dp[i][x][y][5],dp[i-1][x][y][3]);
					// a3->empty
					FOR(x,2) dp[i][x][1][5]=min(dp[i][x][1][5],dp[i-1][x][1][4]);
				}
			}
			else {
				// take a3
				FOR(x,2) {
					dp[i][x][1][4]=min(dp[i][x][1][4],dp[i-1][x][0][4]+1);
					dp[i][x][1][4]=min(dp[i][x][1][4],dp[i-1][x][0][5]+1);
				}
				// keep
				int isL=(i>1)&&(S[i-2]=='w');
				int isR=(i<N)&&(S[i]=='w');
				FOR(x,2) FOR(y,2) {
					dp[i][x][y][0]=min(dp[i][x][y][0],dp[i-1][x][y][0]+1);
					dp[i][x][y][3]=min(dp[i][x][y][3],dp[i-1][x][y][3]+1);
					dp[i][x][y][4]=min(dp[i][x][y][4],dp[i-1][x][y][4]+1);
					dp[i][x][y][1]=min(dp[i][x][y][1],dp[i-1][x][y][1]+1); //get a2
					if(isL) dp[i][x][y][2]=min(dp[i][x][y][2],dp[i-1][x][y][1]+1); //get a2
					if(isL&&isR) dp[i][x][y][3]=min(dp[i][x][y][3],dp[i-1][x][y][1]+1); //get a2

					dp[i][x][y][1]=min(dp[i][x][y][1],dp[i-1][x][y][5]+1); //get a2
					if(isL) dp[i][x][y][2]=min(dp[i][x][y][2],dp[i-1][x][y][5]+1); //get a2
					if(isL&&isR) dp[i][x][y][3]=min(dp[i][x][y][3],dp[i-1][x][y][5]+1); //get a2

					dp[i][x][y][2]=min(dp[i][x][y][2],dp[i-1][x][y][2]+1);
					if(isR) dp[i][x][y][3]=min(dp[i][x][y][2],dp[i-1][x][y][2]+1); //get a2
					dp[i][x][y][3]=min(dp[i][x][y][3],dp[i-1][x][y][3]+1);
				}
				// new section
				FOR(y,2) dp[i][0][y][0]=min(dp[i][0][y][0],dp[i-1][0][y][5]+1);
				FOR(x,2) dp[i][x][0][4]=min(dp[i][x][0][4],dp[i-1][x][0][5]+1);
				if(T[i-1]=='_') {
					//keep empty
					FOR(x,2) FOR(y,2) dp[i][x][y][5]=min(dp[i][x][y][5],dp[i-1][x][y][5]);
					// a1->empty
					FOR(y,2) dp[i][1][y][5]=min(dp[i][1][y][5],dp[i-1][1][y][0]);
					// a2->empty
					FOR(x,2) FOR(y,2) dp[i][x][y][5]=min(dp[i][x][y][5],dp[i-1][x][y][3]);
					// a3->empty
					FOR(x,2) dp[i][x][1][5]=min(dp[i][x][1][5],dp[i-1][x][1][4]);
				}
			}
		}
		FOR(x,2) FOR(y,2) {
			ret=min(ret,dp[N][1][y][0]);
			ret=min(ret,dp[N][x][y][3]);
			ret=min(ret,dp[N][x][1][4]);
			ret=min(ret,dp[N][x][y][5]);
		}
		
		
		reverse(ALL(S));
		reverse(ALL(T));
		FORR(c,S) c='b'+'w'-c;
	}
	cout<<ret<<endl;
	
	
}

まとめ

こういうの本番中に一発で通せる気がしないなぁ。