Codeforces Round #298 (Div. 2) F. Simplified Nonogram
本番TLEしたやつ。こういうの慣れてないのでこれから慣れていかないと。
解法:全探索すると間に合わないのは明らかなので,いろいろと工夫する。
まず第一の工夫が,左右に分けて探索すること。これによって探索量が大幅に減る。
次の工夫が,dpによって解をまとめること。この問題で,例えば列ごとに探索していくとすると,ボード全体の様子を保持しておく必要はなく,直前の列の状態と今までに各行がどれくらいセグメントを持っているかだけ分かっていれば良いことに気づく。
よって,dp[col][s][prv]=(今見ている列がcolで今までに各列でセグメントがsで表されるだけ保持されていて直前の列がprvで表されるときの直前の列の状態)と定義してdpを計算することができる。
「sで表される状態」というのは,例えば各行がセグメント数1個,2個,1個だったとすると,
3^0 * 1 + 3^1 * 2 + 3^2 * 1といった感じで状態を持っておくことを意味します。今回の場合は各行を2分割しておくと最高でセグメント数は6なので3^nと書いたところは6^nになります。
以下ソースコード。自分ではとてもまとめられそうになかったので模範解答(Submission #10705343 - Codeforces)を写経しました。一応コメントつけてわかりやすくしたつもりなので参考にしてください。
const int N = 5; const int M = 20; // セグメント数の最高値(半分に割るので最高でも6個) const int B = 6; // それぞれの行で今までセグメント数がいくつか(B^Nが最高) const int S = 7776; // bcはその並べ方をしたらいくつのセグメントができるかを示す // 例:11010はセグメント数2なのでbc[26] = 2 int n, m, a[N], b[M], bc[1<<N]; typedef char dpmat[M/2+2][S][1<<N]; int c[M+1]; // 右側と左側 dpmat lft, rgt; // sが今まで数えたセグメント数だとして, // mul=1:一つ前の列がmask1で今の列がmask2のとき次の列では行ごとのセグメント数がどうなっているか // mul=-1は逆走するので減っていく int make_move(int s, int mask1, int mask2, int mul) { int ns = s; // セグメントが増える行だけビットが1になります // どちらもbitが1だとxorで消される mask2だけ1だと&演算子で残る int dm = mask2 & (mask1 ^ mask2); int pw = 1*mul; for (int c = 0; c < n; c++) { if (dm & (1<<c)) ns += pw; pw *= B; } return ns; } char ans[N][M+1]; // dp[列][今までの行ごとのセグメント数][今の列の状態]=1つ前の列の状態 void calcdp(int m, dpmat dp) { // 初期化 for (int i = 0; i <= m; i++) for (int s = 0; s < S; s++) for (int j = 0; j < (1<<n); j++) dp[i][s][j] = -1; dp[0][0][0] = 0; for (int i = 0; i < m; i++) { for (int s = 0; s < S; s++) { for (int mask1 = 0; mask1 < (1<<n); mask1++) { // mask1の値が条件で言っているようなセグメント数になってなかったらスルー if (bc[mask1] != c[i]) continue; if (dp[i][s][mask1] == -1) continue; for (int mask2 = 0; mask2 < (1<<n); mask2++) { if (bc[mask2] != c[i+1]) continue; int ns = make_move(s, mask1, mask2, +1); dp[i+1][ns][mask2] = mask1; } } } } } // 各列の状態をbitで管理する int res[M]; // 左側と右側のセグメントの数 int al[M], ar[M]; // dpから逆走して答えを記憶していく void restore(int m, int s, int mask, dpmat dp) { for (int i = m; i >= 1; i--) { res[i-1] = mask; int pmask = dp[i][s][mask]; s = make_move(s, pmask, mask, -1); mask = pmask; } } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; // bcの初期化 for (int i = 0; i < (1<<n); i++) { int c = 0; int prv = 0; for (int j = 0; j < n; j++) { int cur = ((i>>j)&1); if (cur && cur != prv) c++; prv = cur; } bc[i] = c; } // 半分に分ける int l = m/2, r = m-l; int il = l-1, ir = l; for (int i = 0; i < l; i++) c[i+1] = b[i]; calcdp(l, lft); for (int i = 0; i < r; i++) c[i+1] = b[m-i-1]; calcdp(r, rgt); // 答えを再現する // sl:左側で稼ぐ行ごとのセグメント数 // ml, mr:左側の右端の列の状態,右側の左端の列の状態 for (int sl = 0; sl < S; sl++) { for (int ml = 0; ml < (1<<n); ml++) { if (bc[ml] != b[il]) continue; if (lft[l][sl][ml] == -1) continue; for (int mr = 0; mr < (1<<n); mr++) { if (bc[mr] != b[ir]) continue; int sr = 0; int pw = 1; int csl = sl; for (int i = 0; i < n; i++) { int cs = a[i]; int cl = csl % B; csl /= B; // 左側のセグメントの数 al[i] = cl; // 右側のセグメントの数 int cr = cs-cl; // 左側の右端と右側の左端でつながってたら右側でもう一個セグメントが必要 if (mr & ml & (1<<i)) cr++; if (cr < 0 || cr >= B) { sr = -1; break; } sr += pw*cr; // 右側の各行のセグメントの数 ar[i] = cr; pw *= B; } if (sr == -1) continue; if (rgt[r][sr][mr] != -1) { restore(l, sl, ml, lft); for (int i = 0; i < l; i++) { for (int j = 0; j < n; j++) { ans[j][i] = ((res[i]>>j) & 1) ? '*' : '.'; } } restore(r, sr, mr, rgt); for (int i = 0; i < r; i++) { for (int j = 0; j < n; j++) { ans[j][m-1-i] = ((res[i]>>j)&1) ? '*' : '.'; } } for (int i = 0; i < n; i++) puts(ans[i]); return 0; } } } } puts("Impossible"); return 0; }
今度ちゃんと自力で解こう。
