大学の講義で出てきたパストランジスタ(パスゲート、トランスミッションゲート)がよく分からなかったので、ネットで資料を漁りながら自分でも動作をシミュレーションして理解を試みた。

MOSFETのゲートをHにすれば両端繋がるしLにすれば切れるよねー、じゃあこれリレーっぽく使えるよねー、という基本的な気持ちは分かるのだが、こんなのでそんなちゃんと動作するか？？？みたいなのがあった。具体的には、どっちからどっちへ信号が行くかがどう決まるのかとか。

まず信号の伝達方向だが、これは簡単で、そもそも真っ当な論理回路は入力側と出力側というものがある。入力側はハイインピーダンスで電流を出しにくく、出力側は電流を強く出せるようになっている。なのでパスゲートのどっち側をどこに繋ぐかが決まれば伝達方向は確定するのだ。

次に、こんな仕組みでちゃんと信号は伝達されるのかという点について。これは実際問題重要で、nMOSならば、Lの信号を伝えてH→Lにするのは得意だが、Hの信号を伝えてL→Hにするのは厳しい(できなくはない)。pMOSはその逆だ。なのでCMOSっぽくpMOSnMOSを貼り合わせたようなパスゲートが使われたりしているらしい。しかし実際のところ、単体のpMOSやnMOSのパスゲートも普通に使われている。これは要するに、回路的にそれだけで十分ならそうしているということらしい。トランジスタの数を節約するのが本旨なのだからそれはそう。いろいろ上手くやっているようだ。

---

ABC279に出た。

A: count(all(s), 'v')+count(all(s), 'w')*2

B: 全通り試して余裕で間に合う。

C: 列の集合が同じかどうか判断したいわけだが、集合が等しいか判断するにはソートをするのが手っ取り早い。「長さWの文字列H個」を反転して「長さHの文字列W個」に変換してソート。文字列の比較には$O(長さ)$必要でソートには$O(N\log N)$かかるので、$O(HW\log W)$でソート出来る。

初歩的ではあるがこんな計算量判断がCで出るか？感はある。

D: 三分探索も考えたが自信が無いので数学で解いた。数式を変形すれば解析的には$(A/2B)^{2/3}-1$が答えになるので、その付近の整数を探索してしまえば解ける。かけ算オーバーフローに気付けず1WA。

E: 「操作1,2,…nがあり、iだけやらない場合の結果」みたいなやつをi=1,2,…nについて求める、みたいな問題は、だいたい前後両方からそれぞれ「1,2,…kをやった結果」と「k,k+1,…nをやった結果」を求めて組み合わせる感じのことをする。ただし今回の問題は単純にそういう訳には行かない。最終的な1の位置を求めたいわけだが、最終的な状態が分からないのに後ろからやった結果を考えようがないからだ。

しかし、最終的な各地点が、ある時点でのどこに対応するかは求められる。

まずk=1,2,…Nについて、「操作1,2,…kを行ったときの1の位置」を単純にシミュレーションで求めておく。前の結果が使いまわせるので$O(N)$で求まる。次に順列を用意し、操作をNから順番に逆順にやっていく。逆順にやっていきながら1の位置を見る。こうすれば1がどこに来ていようと、最終的な位置との対応が見られる。

F: かなり手間取ってしまった。もうちょっと手早く解けたはずという気もするが、ちょっと不慣れな傾向の問題だったかもしれない。

まず、ボールの番号は最大N+Q程度であることが分かる。当初「操作2ではボールに振ってある数の和を見る」ものと誤読しており、サンプルケースを手でやってみてようやく理解した。

各操作を検討してみると、操作1がボトルネックになりそうなことが分かる。大量のボールを移動させるのはだるそうだ。各ボールの位置を記録することは出来るが、1回の更新に最悪$O(N+Q)$かかる。

しかしよく考えてみると、行う操作は「ボールを追加する」操作と「ボールをまとめる」操作しかない。まとめるといったらUnionFindを使えば良い。各頂点をボールに対応させ、根となるボールの位置だけ記録・更新していけば良い。答える時は根を求めてそれの位置を答えればよい。これでボトルネックは解消された。

あとは細かい部分の話として、上記の操作をやるには「各箱にどのボールが入っているか」に答えられる必要がある。UnionFind上で繋げる糸口を確保したいだけなので箱の中身の全てが分かる必要はなく、箱にボールが入っている場合に最低1個のボールの番号が分かればよい。これも適宜更新してやれば問題なく求められる。これでこの問題が解けた。

最初、UnionFindを持ち出したはいいものの、頂点を「箱」に対応させるのか「ボール」に対応させるのか曖昧なまま実装を進めてしまい、大いにバグらせた。冷静に考えればボール一択なのだが。自分で決めた変数の定義が曖昧なまま実装を進めるのは良くない。ちゃんとどれが何を表しているのか自覚的でなければ。