ICFPC 2010 回路生成部分
追記の追記
やっぱりO(N)でできます。ただし、N+1じゃなくてN+7になります。なぜ6個増えたかというと、常に0を出力する1入力の回路が6ゲートかかるからです。実装上の都合により、常に2を出力する回路を7ゲートで作成する方が、N個必要という部分が分かりやすいのと、綺麗に書けるのと、ということがあります。
方針としては、次の回路に欲しい値を要求する連鎖を作る部分は共通です。また、1や2が欲しい回路はすべて右出力をつないでいくことで、最初のclkに2を供給させます。最後に余った2が出てくる信号線は0を常に作る回路に捨てます。(外部入力も余っているので、どっちでもいいです。)
整理すると、あるクロックで欲しい出力は、今までに作った回路で変形されて、そのクロックが0clk目の回路(任意に値を作れる)に要求としてやってきます。このとき、0ならば独立した回路(要は今まで通りの大きさ1の回路)として作られます。1か2が欲しい場合は最初のclkだけ2を出力する右出力の連鎖を受け取ります。右出力は2になるので、この連鎖の後ろにつながります。そして最後は捨てられるわけです。
この右出力の連鎖ですが、常に2を出力する回路からの出力で始まっているので、あるクロックに欲しい値は、今までの回路の出力を操作する過程で決定できます。以上のようにすると、右出力の連鎖を使えば1か2ができ、0出力は独立に作れるので、どの出力も1ゲートで作れます。よって、7ゲートの常に2を出力する回路と組み合わせて、N+7ゲートで生成できるのです。
追記
追記...。さらに激しく間違ってるみたいです。要再検討...。
どうもN+1個ではできなさそうです...。右出力から常に出てくる2は、次の回路に配送することはできますが、2つ以上先の回路に送るともう一本の信号線の遅延数が足りないので変なことになる模様。以下は修正してないですが、多分間違ってます、すみません...。
昨日の続き。入力Nに対して1.66Nのゲートを使っていたけれど、実はN+1個でできることが判明したので、昨日の内容を理解できた人には分かる程度に...。
まず、ゲートの右出力が使い物にならない、という説は嘘だった。0#ゲートの片方の入力を後ろ向きにしておくと、初期値0が0clkの時点では供給されるので、2を常に出力する。この2を前向きに渡すことで、1ないし2を1個の0#ゲートで生成できる。平たく言うと、1-2-2のゲートテンプレートをうまくパイプライン的につなぐことで、1-1-1にでき、ただし最初に要求される値が1なのでそれに2を供給するすべがないためにN+1個になるという次第。
基本的に入力のK桁目をK番目の回路の0clk目の挙動で作り、0#ゲートの片方の入力に次の回路からの信号を受け、前の回路へ受け渡すのは左出力、という点については前日の通り。
まず、回路1を考える。これは先ほど述べたように、1を生成することが要求されているので、昨日書いた通り、2個の0#ゲートを使う。1個目の右出力が2なので、これを2個目に食わせて1を得る。(左出力の0はいらないので、自分に戻す。すべての0#ゲートが後ろ向き信号を得るようにする必要があるため。)各0#ゲートは後ろ向きの辺を一つ入力に取るので、どちらも0clk目には右出力が2となる。この2を自分で消費するか、次の回路に投げるかを決定しなくてはいけないが、次の回路に投げたときに、信号線の都合により次の回路で余った出力が戻ってこなくてはならない。(正確には2を必要とされない回路が出現すると余るので、そこから戻ってくる。)このときに戻す信号を右出力にすることにより、0clk目に常に2とできる。つまり自分で作った2を自分に食わせるか、先送りして別の回路から返してもらうかという違いはあるが、結果は同じ。
次に回路1を考える。回路0が1clk目に出力しないといけない値は決まっている。(作りたい値に沿うように回路を作っているわけなので。)また、上記のように、最初の0#ゲートで生成した0の値と、自分で作ったか先の回路から戻ってきたかは不明だが2という値の入力、内部の前向きの信号と、2個目の0#ゲートに来るべき外部入力、という3つの決定可能な値が入力になる。以上から、一つだけ分からない値である外部入力の値が決定できる。つまりこの値を0clk目に生成することを、回路1に要求すれば良い。
回路1に要求され得る値は0,1,2のいずれか。0であれば昨日の大きさ1の回路を使う。1,2の場合は先日は2つの0#ゲートを必要としていたが、一つ目の0#ゲートは2を出力として得るためのものであり、前の回路0が2を余らせているので(使うなら同じ値を返せ、とは言われているが)この部分が省略できる。
後は昨日同様、横一直線に回路を並べれば良い。細かい結合については割愛。また、回路間で信号の受け渡しが発生するため、次のclkで次の回路に要求すべき値の計算がやや煩雑になることを付け加えておく。
