読者です 読者をやめる 読者になる 読者になる

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;
}