SRM 544 500pt : FlipGame

TopCoder

問題概要

W*H(W,H<50)のボードがあり、各マスには0,1が入っている。交点(0,0)から(W,H)へ最短路を書く。分断されたうち左側の各マスをすべてフリップする。最終的に全部0にしたい。最小何手かかるか求める問題。

考えたこととか

  • 最後のステップでは単調増加列っぽいのを必ず消すんだからそこを目標にすれば良さそうだな。
  • 全列挙は流石に無理。DPも覚えるべき状態数多すぎ、xorする系のやつだからフロー系もないだろう。
  • というか、これ答存在するのか。まずはそれを手で確かめてみよう。
  • 右上にある1を消すのを考える。この1を残しておくと考え辛いのでこの1を消しにいこう。
  • その右下のなかで右上にあるものを選んで…、とすると右端の何というか凸包っぽいものは左に移る。
  • これで任意の盤面が解ける。ついでにほぼこれが最小であることも言えている気がする。こういうことってよくある。
  • 実装開始…。バグ…。バグ…。合った。サンプル全部通ったので出そう。
  • 順位表を見て絶望する。

acceptされたコード

#include <vector>
#include <string>
using namespace std;

const int MAX_W = 50;

int right[MAX_W + 1];

struct FlipGame {

	int minOperations(vector <string> board) {
		const int H = board.size(), W = board[0].length();
		for(int t=0; ; ++t){

			for(int i=0; i<H; ++i){
				right[i] = 0;
				for(int j=0; j<W; ++j){
					if(board[i][j] == '1'){
						right[i] = j+1;
					}
				}
			}

			bool ok = true;
			for(int i=0; i+1<H; ++i){
				ok &= (right[i] <= right[i+1]);
			}
			for(int i=0; i<H; ++i){
				for(int j=0; j<W; ++j){
					ok &= (j < right[i]) ^ (board[i][j] == '0');
				}
			}
			if(ok){
				return right[H-1] == 0 ? t : t + 1;
			}

			for(int i=0; i<H; ++i){
				right[i] = i==0 ? 0 : right[i-1];
				for(int j=right[i]-1; j<W; ++j)if(j>=0){
					if(board[i][j] == '1'){
						right[i] = j + 1;
					}
				}
			}

			//flip
			for(int i=0; i<H; ++i){
				for(int j=0; j<right[i]; ++j){
					board[i][j] = (board[i][j] == '0' ? '1' : '0');
				}
			}
		}

		return -1;
	}

};