TopCoder SRM 855 : Div1 Easy Div2 Hard MinesweeperStrings

最初の誤った上限のためにバグったコードを入れてしまい、resubmitでひどいことに。
https://community.topcoder.com/stat?c=problem_statement&pm=18236

問題

整数N,Xが与えられる。
1*Nマスで構成されるマインスイーパを考える。
爆弾のあるマスは"*"、爆弾のないマスは隣接マスのうち爆弾のあるマスの数を"0","1","2"という文字を使い、N文字の文字列によりマインスイーパの盤面を表現するとする。
あり得る盤面の文字列のうち、辞書順でX番目のものを求めよ。

解法

爆弾の有無のパターンを考えると、あり得る盤面は2^N通り。
文字列の先頭から爆弾の有無を考えていく。爆弾のないマスに012いずれとするかは、爆弾の有無が各程度に埋めればよい。

• 文字列の先頭、または爆弾の直後の場合：爆弾を置いた方が、置かない場合より文字列全体で辞書順で小さくなる。
• 爆弾のないマスの直後の場合：爆弾を置かない方が、置く場合より文字列全体で辞書順で小さくなる。(爆弾を置くと、手前のマスの文字が行く裏面とされるため)

上記前提をもとに、爆弾を置く場合と置かない場合どちらがX番目に近づくかを見て行けばよい。

class MinesweeperStrings {
	public:
	string generate(int N, long long X) {
		
		if(X>=1LL<<N) return "";
		X++;
		string S;
		
		int i;
		int pre=0;
		FOR(i,N) {
			
			if(pre==0) {
				if(X<=1LL<<(N-1-i)) {
					S+="*";
				}
				else {
					X-=1LL<<(N-1-i);
					S+=".";
					pre=1;
				}
			}
			else {
				if(X<=1LL<<(N-1-i)) {
					S+=".";
				}
				else {
					X-=1LL<<(N-1-i);
					S+="*";
					pre=0;
				}
			}
		}
		FOR(i,N) if(S[i]=='.') {
			int x='0';
			if(i&&S[i-1]=='*') x++;
			if(i+1<N&&S[i+1]=='*') x++;
			S[i]=x;
		}
		
		
		
		return S;
		
	}
}

まとめ

最初は単純に爆弾の置き方を辞書順に並べるだけでいいと思ってたので、いい意味で裏切られた。