AOJ 2633 「Cellular Automaton」
りんごさんセットのCellular Au🍅n解きました。
面白いです。ヒントなしでは解けませんでした。
ヒント
ヒント
グラフ
グラフの頂点は2^(2w+1)個、辺は各頂点から2本ずつでる有向辺
閉路の重み
ポテンシャル
牛
解法
ネタバレ防止のため閉じてあります
w=1で考えます
sの長さは3です
000~111に対して0,1を割り振ったとき、それが条件を満たすかどうかを判定する方法を考えます
判定方法
まず、000は0でなくてはならない(わりと自明)
セルの初期状態として考えられるものは、
・00..0001011000..00
のように、000で囲われたものになる
この例だと、
・p[000]+p[001]+p[010]+p[101]+p[011]+p[110]+p[100]+p[000]=3
を満たしている必要がある。
ここで、000~111を頂点とし、「1つシフトして右に0か1をつけたもの」に重み付きの辺を張る
たとえば、011-0->110、011-1->111、010-0->100、010-1->101、のような感じ
このグラフの000を含むサイクルであって、辺の重みの和≠頂点の重み(p[v])の和となるものがあってはならない
グラフを少し拡張して、頂点の重みを辺の重みとして扱えるように変形します
頂点を2倍にして、片方をin、片方をoutにして、他の頂点からの辺u->vはu_out->v_inとつなぎ直します
それから、v_in->v_outに重みが-p[v]の辺を張ります
このグラフに重みが0でない閉路があってはいけません
判定だけならこれでできるようになりました
ただし、解の候補は2^128通りあったりするのでまだ工夫が必要です
p[v]を0,1だけでなく?にできるようにします。(?=0か1のどちらかが未定)
?を許可した時の判定方法
各頂点にポテンシャルh[v]を定めた時、全ての辺u->vでh[u]+重み=h[v]となっていれば良いです
h[u]+重み=h[v]を
・h[v]≦h[u]+重み
・h[u]≦h[v]-重み
に書き直すと牛になります。
重みが?の辺に関しては、
・h[v_out]≦h[v_in]+(-1)
・h[v_in]≦h[v_out]
です。
辞書順でs以上の最小を求める方法は、ソースコードを読むのが早いと思います
イメージとしては、0から1にすべき最下位のビットを求めて、そこからはいつもの辞書順
ちなみに、閉じるやつはindenterで生成しました。
ソースコード
// 前略 int w, n; bool f(string s) { rep(i,n) { int l = (s[i] == '1'); int r = (s[i] != '0'); g.setCost(i, r); g.setCost(n+i, -l); } return !g.hasNegativeCycle(); } int main() { string s; cin >> w >> s; w = w*2+1; n = 1<<w; g = bell(n*2); rep(i,n) g.add(i,n+i,0); rep(i,n) g.add(n+i,i,0); rep(i,n) { int u = (i<<1)&(n-1); g.add(n+i,u,0); g.add(u,n+i,0); g.add(n+i,u|1,-1); g.add(u|1,n+i,1); } // ここから辞書順最小を計算 if (f(s)) { cout<<s<<endl; return 0; } for (int i = n-1; i >= 0; --i) { if (s[i] == '0') { s[i] = '1'; if (f(s)) break; } s[i] = '?'; } if (s == string(n,'?')) { puts("no"); return 0; } rep(i,n) { if (s[i] != '?') continue; s[i] = '0'; if (!f(s)) s[i] = '1'; } cout<<s<<endl; return 0; }