yukicoder : No.608 God's Maze

シンプルな設定だけど意外に手こずる問題。
https://yukicoder.me/problems/no/608

問題

1次元のグリッドが与えられる。
各マスは明かりが点いているかいないかのいずれかの状態を持つ。
プレイヤーの駒は指定されたマスを初期位置とし、左右いずれかの隣接マスに繰り返し移動できる。
その際、移動先のマスの明かりの状態が反転する。

全マスの明かりを消すために必要な最小移動回数を求めよ。

解法

初期位置から明かりが点いている範囲で一番左のマスまで移動した後、徐々に明かりを消しながら右に移動するか、その逆の手順いずれかを行い、最小移動回数の方を選択すればよい。
「徐々に明かりを消しながら右に移動」の例をもう少し具体的に書くと以下の通り。

• 今足元の明かりが点いていないなら右に移動
• 今足元の明かりが点いているなら右・左・右の順で移動 (右端のマスだけは左右左と移動しないといけないが、移動回数は同じだし気にしなくてよい）

int N,L;
string S;

void flip(int& cnt,char &tar) {
	cnt-=tar;
	tar^=1;
	cnt+=tar;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	L=S.size();
	N--;
	FORR(c,S) c=(c=='#');
	ll mi=1LL<<60;
	
	FOR(i,2) {
		string T=S;
		int LL=L+1;
		int cnt=0;
		FOR(j,L) if(S[j]) {
			cnt++;
			LL=min(LL,j);
		}
		
		
		ll tot=0;
		int cur=N;
		
		if(LL<cur) {
			for(j=LL;j<cur;j++) flip(cnt,T[j]);
			tot=cur-LL;
			cur=LL;
		}
		while(cnt) {
			if(T[cur]==0) {
				tot++;
				cur++;
				flip(cnt,T[cur]);
			}
			else {
				tot+=2;
				T[cur]=0;
				cnt--;
				flip(cnt,T[cur+1]);
			}
		}
		
		mi=min(mi,tot);
		reverse(ALL(S));
		N=L-1-N;
	}
	cout<<mi<<endl;
	
}

まとめ

出てそうで意外に出ていなかった？問題。