Golden Week Contest 2015 解説

Golden Week Contest 2015 - Golden Week Contest 2015 | AtCoder
というコンテストをAtCoderさんで開かせていただいていました。

まずは、チーム/個人それぞれののtop10から。

チーム

順位	チーム名	点数	問題数	時間	全体順位
1	カラフルジャンボチキン	621	7.5	234:17	3
2	代々木に行くよ（回文）	563	7	221:34	8
3	チーム爽健美茶	563	7	246:07	10
4	†地獄†零春 ‡チーム‡	563	7	246:07	12
5	chikOkU	487	6	274:59	16
6	yosky	435	6	139:42	18
7	camypaper,nuip	435	6	211:44	21
8	お姉ちゃんと猫	435	6	225:42	22
9	btk(チーム（一人))	136	2	92:09	43
10	sonna*baka*na	25	1	126:10	110

個人

※すぬけ さんはりんごさんです。

順位	ユーザ名	点数	問題数	時間	全体順位
1	すぬけ	1000	10	198:16	1
2	semiexp	837	9	201:25	2
3	uwi	621	7.5	266:46	4
4	chokudai@AtCoder社長	621	7.5	273:04	5
5	すぎむ	621	7.5	306:56	6
6	cgy4ever	598	7	312:52	7
7	satos	563	7	230:22	9
8	kmjp	563	7	245:27	11
9	stqn	563	7	272:15	13
10	Lepton_s	563	7	297:44	14

各問題の解説

A 得点

DPすればいいです。G問題を初期化のときに処理しておくと楽です。

2^9 * 3 個全部を列挙して重複を取り除いても良いです。

B アリ巣

10080ターン目あたりから長さ104の周期に入ります。

ラングトンの蟻です。

ラングトンの蟻はこれで知りました。

C Snukeと対戦！

HとWのどちらかが偶数の時

後手を選択し、相手の手と点対称な位置に相手と反対の色の碁石を置く。

HもWも奇数の時

先手を選択し、真ん中に碁石を置く。

その後は、相手の手と点対称な位置に相手と同じ色の碁石を置く。

D 最短絡問題

dist(1,1,i,j) を質問し、h[i][j] としておく。

dist(si,sj,ti,tj) を質問されたら、ti>siのときは、siとti・sjとtjを交換しておいて、

• si ≦ ti かつ sj ≦ tj のとき：h[ti][tj] - h[si][sj]
• そうでないとき：(h[ti][tj] - h[si][tj]) + (h[si][sj] - h[si][tj])

を答える。

左上（マス(1,1)の方）から右下へ行く経路は（左や上に行かなければ）どんな経路でもコストは同じで、左下から右上へ行く経路は最初に上にずっと行ってそこからずっと右に行くような経路が最短であることが証明できます。

タイトルが少し変なのは、間違い探し的な意味しかないです。（問題自体に短絡要素はあんまりない気がする）

E シフト塗り分け

L = N のとき

蟻本のポリアのところに書いてあります。

L が偶数の時

• 12345 → 41235 → 45123

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。L+1 が奇数なので、L+1 のシフトも構成できます。

L のシフトと L+1 のシフトを組み合わせると、

• 12345 → 41235 → 12354
• 12345 → 45123 → 24513 → 13245

のように任意の場所をswapできます。ということは、全ての順列を作ることができます。

この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」になります。

L が奇数の時

• 123456 → 512346 → 561234

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。

L のシフトと L+1 の偶数回シフトを組み合わせると、

• 123456 → 451236 → 123645
• 123456 → 145623 → 231456
• 123456 → 561234 → 235614 → 142356

のように任意の場所で 3 のシフトができます。

3 のシフトができると、偶置換が作れます。（前からN-2個を順番に埋めていけばいい）

偶置換を同じとみなす時の塗り分け方は、

• 全部異なる色で塗る場合：各色の選び方について 2 通り
• 同じ色がある場合：各色の選び方について 1 通り

となるので、この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」+「K個の色からN個の色を重複ナシで選ぶ場合の数」が答えになります。

F ピラミッド - 誕生日編

N が奇数の場合

石の総数の偶奇で決まる。

N が偶数の場合

石の個数が最小の山にある石の個数に注目します。これを X とします。

• X = 0 のとき：石の総数の偶奇で決まる。
• X = 1 のとき：その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 0 にでき、石の総数の偶奇を自由に選べるので勝ち
• X = 2 のとき：X を 1 にすると負けるので、全部の山から取る操作をすると負ける。つまり、石の総数の偶奇で決まる。
• X = 3 のとき：その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 2 にでき、石の総数の偶奇を自由に選べるので勝ち

というふうに、X が奇数のときは先手必勝、X が偶数のときは石の総数の偶奇で勝敗が決まる。

G ピラミッド - 球編

ある穴が壊れた時に石を置けなくなる場所は、直方体状になっています。

部分点は包除原理で計算すれば良いです。

満点は、JOI2011-2012 Day1 Fish 解説

H ピラミッド - デコ編

ある石の色が勝敗に関係するかどうかを計算します。

数式はいろいろありますが、x = B-1, y = A-B, z = L-A とすると

• (x|y|z) == x+y+z なら勝敗に関係する

となります。あとは、勝敗に関係する黒の位置の個数 (mod 2) を求めればいいです。

段数によって結果が反転するので気をつけてください。

I ピラミッド - 立方体編

簡単だったらしい。

DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+1, H[i][j])

を４方向に計算すればいい。

想定解ではもう少し複雑なDPをしてしまっていました・・・

J ピラミッド - 2D編

ヤング図形 - Wikipedia

これを求めるときの分母を効率的に求めたい。

• f(a, x, y) = a~a+x+y-2がずら〜と並んだx*yの長方形の積

という関数を求められれば良い。

例えば、f(4,4,3) は

4 5 6 7
5 6 7 8
6 7 8 9

の積を求めればよくて、4*5*6*7*5*6*7*8*6*7*8*9 になる。

これを求めるためには、10^6 くらいまでの

• ∏ i^i
• i! （階乗）

の値が前計算してあれば良い。

次に、以下の図のイメージで計算（赤を掛けて青を割る）すれば三角形の部分（∏ (i+a)^i）が求まる。

あとは、以下の図のイメージで計算すれば f も求まる。

sublimeのプラグイン作った

sublimeの競プロプラグインを作りました。github.com

適当にプラグインの作り方をググって、雰囲気を把握して、あとはAPI referenceを眺めながら作ったらできた。どう実装するのかわからないところが出てきたらサンプルをあさるのも吉っぽい。

pythonで書けるのが嬉しい。

作ったやつの機能としては、ライブラリを貼ったり、scanf文とかの省略形を展開したり出来ます。詳細はgithubに置いたreadmeを読んでください。

もともとはシェルスクリプトとかでやってコマンドラインからやってたんですが、エディタのプラグインにしてみたらめっちゃ快適でびっくりした。

ちなみに、「[rand]っていつ使うねん汎用性低すぎへん？」って思うかと思いますが、
これはテストケース作るときの乱数シード書くときに欲しかったから作りました。

追記：github.com

こんなのも作った。使いたいシチュエーションが割とあって、使ってみるとすごい便利だった。

プラグイン作るの手軽すぎて、単純なやつなら探すより作った方が早いっていうのすごく気軽な感じで良い。

sublimeをカスタマイズした

Sublime Textが気に入ってずっと使ってるんですが、今更ながらsublimeのカスタマイズをした。なんかMicrosoftが新しいエディタを出したのに触発されてやった。

とりあえずまず、Sublime Textの気に入ってる点と不満点を挙げます。（今朝の時点での）

気に入ってる点

• シンプル
• 欲しい機能（インデントとか）が大体揃っている
• マルチプラットフォームだし、Windowsを突然渡されてもエディタに困らなさそう
• マルチカーソル、"⌘d"がめちゃ便利
• プラグインが作りやすいらしい
• その他カスタマイズもしやすい

不満点

• C++で「for (i=0;i<N;++i) sum+=i;」みたいに１行でfor文を書くとインデントがバグる
• 保存するとたまに変なダイアログが出てくるバグがある
• tabで補完が出来るんですが、日本語入力で予測変換でtabを使うと補完が発動してバグる
• 検索パネルの閉じ方が分からない

で、不満点のうち３つ目以外を今日解消しました。

インデントのバグ

C++で「for (i=0;i<N;++i) sum+=i;」みたいに１行でfor文を書くとインデントがバグる、という件

メニューから「Preference」→「Sublime Text 2」→「Preferences」→「Browse Packages...」から"Package"フォルダを開いて、"C++"フォルダ内の"Indentation Rules.tmPreferences"ファイルを探して開く。

どうやら27行目が悪さをしてるようなので、コメントアウトしてみた。

//24~28行目
<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
<!--| ^ \s* \b(for)\b .* $-->
</string>

当然ですが、２行に分けてforを書きたいときとかでもインデントされないようになりましたΩ＼ζ°)ﾁｰﾝ

まぁそれでいいやと一瞬思ったけどやっぱり困る気がしたのでちょっと考えた結果こうなった。

<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
| ^ \s* \b(for)\b[^;]*;[^;]*; [^;]* $
</string>

いい感じに動いてくれました。

追記(2015/05/01 02:24)：これでもまだ「for(;;)for(;;)\n」（二重forを一行に書いて次の行に処理を書く）というコーナーケースがありますね。これは諦めてforを２行に分けたりしてください。完璧な正規表現はかなり難しそうです。

追記(2015/05/10 16:09)：range-based forに対応できていなかったので修正しました。

<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
| ^ \s* \b(for)\b([^;]*;[^;]*;|[^:;]*:[^:;]*) [^;]* $
</string>

ちなみにsublimeを再起動しないと更新されません。

Sublime Text 3での解決法は知りません。

変なダイアログ

保存するとたまに変なダイアログが出てくるバグがある、という件

お金で解決しました。70$でした。

補完と予測変換

tabで補完が出来るんですが、日本語入力で予測変換でtabを使うと補完が発動してバグる、という件

これはよくわからなかった。解決できるようにできる条件は多分、

• 補完を別のキーにする
• MacのデフォルトのIMEを使うのをやめる

のいずれかっぽいんですが、どっちも嫌なので諦めました。

検索パネルとかの閉じ方

検索パネルの閉じ方が分からない、という件

Sublime Text 3の検索パネルにはxボタンがあるのに他にはないせいで余計ハマっていましたが、解決法はシンプルでした。

Escキーで閉じれるそうです。

ちょうどK個選ぶ部分和問題

JAG春コンのB問題の解法が面白かったので僕なりにまとめておこうと思います。

この解説を参考にしました。

問題（要点を抜き出したバージョン）

N 個の数が与えられる。その中からちょうど K 個選んで作れる和を列挙せよ。

制約

与えられる N 個の数の和を M とすると、

• K ≦ N ≦ 600
• M ≦ 180000

普通のDPをすると O(NKM) になって TLE です。（bitsetでもなんとか間に合うらしいです）

こんなにシンプルだし、有名問題なのに、なんと O(NM) のDPがあるらしいです。

解法

まず数を K 個と N-K 個に分けます。これをそれぞれ Aグループ、Bグループと呼ぶことにします。

考えうる全ての選び方は、以下のような操作で実現できます。

1. 最初に Aグループを全て選ぶ（K個選択中）
2. 次に、Bグループの数を１つ追加する（K+1個選択中）
3. Aグループから１つ数を取り除き、2.に戻る（K個選択中）

コードにすると、

bool selected[N];
for (i = 0; i < K; i++) selected[i] = true;

for (i = 0, j = K; j < N; j++) {
  if  (j番目の数を選ぶ) {
    selected[j] = true;
    while(true) {
      if (i番目の数を取り除く) {
        selected[i] = false;
        break;
      }
      i++;
    }
  }
}

みたいなイメージ。

こんな方針をDPに落とし込むとこうなります。

• dp0[i][j][s] = Aグループを i 個、Bグループを j 個見終わった時点で数を K 個選んでいて和が s になるように出来るか
• dp1[i][j][s] = Aグループを i 個、Bグループを j 個見終わった時点で数を K+1 個選んでいて和が s になるように出来るか

「上のコードでのi,jの値が i,jとなっているときに選んでいる数の和をsに出来るか」みたいなtrue/falseのDPです。（厳密には少し違って、このDPでは、数を追加したり削除したりしないならいつでも自由にi++かj++をできます）

遷移は、「if (b) a = true」を「update(a,b)」と書くことにして、

• update(dp0[i][j+1][s], dp0[i][j][s])
• update(dp0[i+1][j][s], dp0[i][j][s])
• update(dp1[i][j+1][s+x[j]], dp0[i][j][s])
• update(dp1[i+1][j][s], dp1[i][j][s])
• update(dp1[i][j+1][s], dp1[i][j][s])
• update(dp0[i+1][j][s-x[i]], dp1[i][j][s])

最終的に dp[K][N][s] がtrueなら s が作れます。

ただ、このままでは O(N^2 M) なので計算量を落としたいです。

• update(dp0[i][j+1][s], dp0[i][j][s])
• update(dp0[i+1][j][s], dp0[i][j][s])
• update(dp1[i+1][j][s], dp1[i][j][s])
• update(dp1[i][j+1][s], dp1[i][j][s])

という遷移があり、「trueの領域は i,j に対して単調」となっています。例えば、trueの領域は以下の図のような領域になっていたりするでしょう。

そこで、

• dp0[j][s] = さっきのDPテーブルで、dp0[i][j][s]==true となるような最小の i
• dp1[j][s] = さっきのDPテーブルで、dp1[i][j][s]==true となるような最小の i

というDPを考えます。つまり、下図のオレンジの部分を記録するという感じ。

遷移は、「a = min(a,b)」を「update(a,b)」と書くことにして、

• update(dp0[j+1][s], dp0[j][s])
• update(dp1[j+1][s+x[j]], dp0[j][s])
• update(dp1[j+1][s], dp1[j][s])

の３つは分かりやすい（さっきのDPの遷移の1,3,5番目とほぼ同じ）。あとは、

• for (i = dp1[j][s]; i < K; i++) update(dp0[j][s-x[i]], i)

があればよい。しかし、これだとまだO(NKM)なのでもう一工夫したい。

• for (i = dp1[j][s]; i < dp1[j-1][s]; i++) update(dp0[j][s-x[i]], i)

試す i の範囲が [dp1[j][s], K) から [dp1[j][s], dp1[j-1][s]) になりました。こうすると、計算量は O(NM) となります。

なぜ、試す i の範囲をこういう風に狭めても良いのでしょうか？

i が dp1[j-1][s] 以上の場合は、

• dp1[j][s] → dp0[j][s-x[i]]

という遷移をしなくても、

• dp1[j-1][s] → dp0[j-1][s-x[i]] → dp0[j][s-x[i]]

という遷移によって更新できるはずだから、わざわざ dp1[j-1][s] 以上の i について遷移をしなくてもちゃんと更新されてくれるからです。

ちなみに、試す i というのは下の図のオレンジの部分に相当します。

ここを試せば、それより上の部分は試さなくても良いという感じでしょうか。

この図を見れば計算量が O(NM) になるのも納得できるのではないかと思います。試す場所の合計は、各 s に対して高々 K 箇所しかないからです。

実装

元の問題は他の要素があって大変そうだったので、ストレートにDPだけの練習問題をNPCA Judgeに置かせていただきました。（今judge止まってるっぽいのでデータも上げておきます）

僕のコードです。

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
 
const int MAX_N = 605;
const int MAX_M = 180305;
const int INF = 1000;
 
int X[MAX_N];
int dp0[MAX_N][MAX_M];
int dp1[MAX_N][MAX_M];
inline void update(int& a, int b) { a = min(a,b);}
 
int main(){
  int N, K;
  // input
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> X[i];
  int m = accumulate(X, X+N, 0);
  // initialize
  for (int j = K; j <= N; ++j) for(int s = 0; s <= m; ++s) {
    dp0[j][s] = dp1[j][s] = INF;
  }
  dp0[K][accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j <= N; ++j) {
    for (int s = 0; s <= m; ++s) {
      if (dp1[j][s] != INF) {
        update(dp1[j+1][s], dp1[j][s]);
        int l = dp1[j][s], r = K;
        if (j > 0) update(r, dp1[j-1][s]);
        for (int i = l; i < r; ++i) {
          update(dp0[j][s-X[i]], i+1);
        }
      }
    }
    for (int s = 0; s <= m; ++s) {
      if (dp0[j][s] != INF) {
        update(dp0[j+1][s], dp0[j][s]);
        update(dp1[j+1][s+X[j]], dp0[j][s]);
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[N][s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

さらに、このコードのようにメモリを再利用をして空間計算量を落とすこともできます。

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
 
const int MAX_N = 605;
const int MAX_M = 180305;
const int INF = 1000;
 
int X[MAX_N];
int dp0[MAX_M];
int dp1[MAX_M];
int dpr[MAX_M];
inline void update(int& a, int b) { a = min(a,b);}
 
int main(){
  int N, K;
  // input
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> X[i];
  int m = accumulate(X, X+N, 0);
  // initialize
  for(int s = 0; s <= m; ++s) dp0[s] = dp1[s] = INF, dpr[s] = K;
  dp0[accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j < N; ++j) {
    for (int s = 0; s <= m; ++s) update(dpr[s], dp1[s]);
    for (int s = 0; s <= m; ++s) update(dp1[s+X[j]], dp0[s]);
    for (int s = 0; s <= m; ++s) {
      if (dp1[s] != INF) {
        for (int i = dp1[s]; i < dpr[s]; ++i) {
          update(dp0[s-X[i]], i+1);
        }
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

感想

すごい（小並感）

boolのDPはやっぱり効率が悪いんだなぁ、とか思った。

SRM 656

出ました。

250

N個のパンケーキがあり、i番目のパンケーキの幅はi+1で美味しさはd[i]です。以下のような操作をしてタワーを作ります。

• 残っているパンケーキをランダムに１つ選びます。（残っていなければ終了）
• そのパンケーキの幅がタワーの一番上のパンケーキの幅より大きければ終了
• そうでないなら積んで、最初に戻る

タワーに積まれたパンケーキの美味しさの和の期待値を求めよ。

解法

期待値の線形性を使う。

つまり「Σ d[i] * (i番目のパンケーキが使われる確率)」で答えを求める。

dp[i][j] = i個のパンケーキを既に使っていて、一番上のパンケーキの幅がjである確率

というDPをして、答えは「Σ dp[i][j]*d[j]」で求めるといい。

初期化は、番兵をおいて、dp[0][N]とすると楽。

ちなみに遷移は、

if (k < j) dp[i+1][k] += dp[i][j]*(N-i)

みたいな感じ？

500

長さNのパーミュテーションであって、pos[i]の箇所だけp[i]<p[i+1]でそれ以外はp[i]>p[i+1]であるようなものを数え上げよ。
※ len(pos) = Mとします。

• N ≦ 10^6
• M ≦ 2500

解法

包除原理

まず、「posのところの条件を満たす必要がない」という問題を考えます。

単調減少でなければならない区間がM+1個出てきますよね。i個目の区間の長さをa[i]とします。

「posのところの条件を満たす必要がない」という問題の答えは「N!/mul(a[i]!)」です。

では、「posのところの条件を少なくともk個満たさない」という問題を考えます。

これは、

dp[i][j] = i番目の区間までを見て今までで少なくともj個の条件を満たさないものの個数/N!（i=0~M,j=0~M）

みたいなDPを考えるとできます。

「/N!」とかいてありますが、これは計算を簡略化するための工夫で、最後に*N!をするという感じです。

遷移は

dp[i][j] = Σ dp[i-k][j+k]*(Σa[i-k]~a[i])!

みたいな感じです（適当に書いたので細かい±1とかがずれてるかもしれませんが）

で、包除原理を使って答えを求めます。

このままだと３乗ですが、包除原理においては満たす条件の個数はどうでもよくて、その偶奇だけに興味があるので、dp[M][2]のDPにすると２乗になります。

ちなみに、さらにまとめてdp[M]（dp[i][0]-dp[i][1]を記録する）にしても良いです。

雑な解説なので、足りないところがあれば考えてみるか、聞いてください。

（本番では階乗の配列を2505で取ってて落ちました。つらい）

文字列の周期性判定

以前の記事「文字列の頭良い感じの線形アルゴリズムたち」で、

この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、
その辺りの説明は他のサイトにお任せします。

と書いたところ、周期性の判定の方に関して「"他のサイト"なんてものはない」と言われてしまったので、書きます。

文字列 S が与えられる。S[0~i] の最小の周期長を全部まとめて O(N) で求めよ。

という問題を考えます。例えば、

abababcaa
122222778

という感じ。（上がSで下が答えの配列）

例えば、"ababa"なら"ab"を繰り返せばいいので 2 という感じ。

解法

KMPでテーブルを作ります。

んで、「i - KMP[i]」が各場所の答え（1-indexed）

簡単な解説

「最小の周期長」＝「k 文字ずらしたものが元の文字列と一致するような最小の k (k>0)」

例えば、"ababa"は

ababa
__ababa

2 文字ずらした時に初めて同じ列にある文字同士が一致するので 2 が答え。

この同値関係は この記事 が参考になるかも

で、「k 文字ずらしたものが元の文字列と一致するようなhogehoge」ってKMPそのものみたいなものですよねという。

練習問題

• PKU 2185: Milking Grid
• ZeptoLab Code Rush 2015 D: Om Nom and Necklace

SAT solverでパズルを解いた話

SAT solverで「数独」「美術館」「ひとりにしてくれ」を解きました。

Githubにあげました。

めっちゃ楽しかったので準急に多謝だー。（JOI春合宿で講義をしてくれた）

準備

SAT solverをインストールしましょう。

僕はminisatにしました。（なんか入れるのに苦労したけど）

SATを知らない人は適当に調べましょう。

流れとしては、

• パズルを連言標準形(CNF)の論理式にして
• SAT solverに投げて
• ビジュアライズする

って感じです。

数独

多分一番簡単です。

「x1,x2,...,x9 のうち、ちょうど１つだけがtrue」

という式が書ければ勝ちです。これは、

• x1 or x2 or ... or x9 （１つ以上であるという制約）
• 全てのi,jのペアについて、!xi or !xj （２つ以上ないという制約）

で実現できます。

あとは、X_i,j,k（i行目j列目がkであるならtrue）という変数を使って

• 行にちょうど１つだけkがある
• 列にちょうど１つだけkがある
• 3x3のグループにちょうど１つだけkがある
• 各マスにはちょうど１つだけ数が割り当てられている

という条件を書いてやればいいです。

美術館

これも基本的

変数は、X_i,j ＝ i行目j列目に明かりを置くならtrue です。

• 照らしあってはいけない
• 照らされていないマスがあってはいけない
• 黒マスに明かりがあってはいけない
• 周りに 0 個ある
• 周りに 1 個ある
• 周りに 3 個ある
• 周りに 4 個ある

は簡単（実際にプログラムとして書くのはちょっと面倒だけど）で、問題は

• 周りに 2 個ある

です。これは、

• どの３個を取り出してorを取ってもtrue
• どの３個を取り出して否定のorを取ってもtrue

の２つの条件にすると楽に書けます。

ちなみに、フィールドの周囲に番兵を置くとかなり実装が楽になります。

ひとりにしてくれ

• 各列に同じ数が２つ以上残ってはならない
• 黒マスが隣り合ってはならない

は簡単。

• 白マスは連結でなければならない

ひぇーっ！？こんなのできるんでしょうか？

かなりのパズルが連結性判定を必要とするので、これができないとなかなか厳しいです。

連結性判定は、いろいろな方法がありそうですが、僕が今回採用したのはBFSっぽい方法です。

イメージとしては、

• 適当に根を決めてBFSをするときの、各ステップでのvisitedの配列を変数にする。

という感じ。式を書く方針はこんな感じ。

• Y_i,j : i行目、j列目を黒く塗るならtrue
• X_i,j,k : i行目、j列目、BFSのkステップ目
• X_i,j,0 たちのうち、１つだけがtrue
• BFSの総ステップ数を T とすると、白マスの X_i,j,T は全部true
• 黒マスの X_i,j,k は全部false
• X_i,j,k+1 がtrueなら、X_ai,aj,kのうちいずれかはtrue（(ai,aj)は(i,j)に隣接するマス）

※「A ならば B」は 「!A or B」と変換できます

変数も節もO(マスの個数^2)個でいい感じです。

ちなみに、17x17のを１つやらせてみたら20秒で答えが出ました。感動！