POJ3423 - Automaton optimization

穴ゴルからの逃避でPOJを解いてみた。

一次元のセルオートマトンで、隣接するセル二つのうち一つのみが真のときにそのセルを真とするというルール(いわゆるルール90)で、初期状態として、真なセルのインデックスがn個与えられて、sステップ後のf〜f+lのセルの状態を表示せよ、という問題。
問題をざっと読んで、適当に書いて、サンプル通ったからいけるんじゃね? とか思ってsubmitしてみるとacceptされたパターン。こういうことやってるから適当なまんまなんじゃないかとは思わないでもない。というわけで以下適当な解説。というか思考過程。
とりあえず、ちょっと考えてみたらシェルピンスキーのガスケットっぽいもの(というかそのもの)が出てくるなぁと分かって、ここでルール90じゃんと気づき。
そっからid:Ozy:20070428(この記事にリンクするの2回目だ)を思い出して、あれ、そっか二項定理でmod2ってことは、 $v_{t+1,n}=(v_{t,n-1}+v_{t,n+1}) mod 2$ みたいな感じなんだろうから、初期条件のセルが及ぼす影響は別々に計算してもいけるんじゃね? (lights out見たいな感じ(この例えもどうなんだろう、xorみたいな感じ))と思って、適当に書いてみたら通った。
誰かがちゃんとした解説書いてくれたら嬉しいです>_<

入力が重たかったのでcppで。

#import<algo.h>
int n,s,f,l,i,j,t,r,a[9];
main(){
  for(cin>>n;i<n;)
    cin>>a[i++];
  for(cin>>s>>f>>l;j<l;j++,cout<<r<<" ")
    for(r=0,i=n;i--;r^=~t&1&!(s-1&t/2^t/2))
      t=s-1-abs(f+j-a[i]);
}

このぐらい適当な内容でも記事にしていこうかな、とちょっと思い始めた冬。でも書かないかもしれません、と先に言い訳しておく。

3427 -- Ecology taxが、結構インチキなコードを書いたのにトップじゃないのが悔しい。

あれ、穴ゴルからの逃避だったのに結局ショートコーディングに頭使ってるな、、、という一日でした。

[追記]
3427 -- Ecology taxですが、よく見てみたら掲示板に書いてあるやん。問題文の解釈によってはこういうコードも通るよ、って感じですかね。そのまま縮めて85B。
wgetで改行をLFにして送るのをずっと手作業でやってたんですが、やっとスクリプトを書いたw