5個以下の2入力NANDで3入力ORは作れるか?

作れません。(タイトル回収終了)

🐟

2入力NANDゲート回路だけで任意の論理演算が表現可能であるという事実はよく知られています。また、最小個数のNANDを用いてNOT・AND・OR・XORなどのゲートを実現する方法も有名です。(下画像)

f:id:sh-mug:20200507222911p:plain

ところで、3入力ゲート回路(AND・NAND・OR・NOR・XOR・XNOR)を実現するために必要なNANDの最小個数はあまり知られていない(はず)です。3入力ゲート回路の定義ですが、AND・OR・XORについては結合法則が成り立つので自然に定義できます。NAND・NOR・XNORは前の3つの論理否定とします。

やったこと

NAND同士を配線するときに回路内にループができると順序回路ができてしまうため、そうならないような配線方法のみを考えます。使用するNANDの個数を1個から順番に調べていき、求める出力を得られる回路が見つかればそのときの個数が最小だと分かります。

配線方法の探索にはSMTソルバの一つであるz3を使用しました。書いたコードは ここ です。リンク先のコードでは最小個数の3入力NANDから3入力XNORを構成するような配線方法を求めています。

結果など

2入力NANDを用いる場合、3入力NANDを用いる場合の最小個数を調べました。

使用するNAND AND NAND  OR  NOR XOR XNOR
2入力 4 3 6 7 8 9
3入力 2 1 4 5 7 7

3入力NANDを7個用いて3入力XOR・XNORを構成できるというのは比較的非自明で面白い結論かもしれません。回路図は下に示します。なお、NAND(A, A, B) = NAND(A, B)より、このような入力パターンの3入力NANDは2入力NANDを用いて略記しています。

f:id:sh-mug:20200507223004p:plain
XOR

f:id:sh-mug:20200507223023p:plain
XNOR

一方で、その他のゲート回路とNANDの入力の組み合わせについて、最小個数のNANDで構成するのは🐟にある回路の組み合わせだけで可能であり、必要なNAND数をそこから減らせないことも明らかになりました。(タイトル回収2回目)

🍣

z3を使う前にC++で配線方法を全探索するコードを書いていたのですが、z3を使ったほうが実行速度が圧倒的に速かったです。z3最高ですね

家にNANDしか無くて困っている人は参考にしてみてください。

AtCoderでLanguage Ownerになりたい!

この記事は ISer Advent Calendar 2019 7日目の記事です。昨日の記事はhutoshikawaさんによる 今年みたアニメなど[後編] でした。

AtCoder競技プログラミングのコンテストを行っているサービスですが、コンテストに参加する以外の楽しみ方もいろいろあります! この記事ではLanguage Owner(以下LOとします)を狙うという楽しみ方の紹介と、僕が二か月前にSchemeでLOになったとき1の記録を書いていこうと思います。まじめな記事ではないので、気楽に読んでくだされば幸いです。

必要な前提知識

  • AtCoderの存在を知っている

LOとは?

AtCoderでは、解答を提出するのに様々な言語を使用することができます。使用可能な言語は、C++Pythonといった有名な言語から、Brainf*ckやUnlambda2といった難解プログラミング言語まで多種多様です。

そして、それぞれの言語の中で最もACした問題数が多いユーザーに与えられる称号がLanguage Ownerです!かっこいいですね。 各言語のAC数ランキングはAtCoder Problemsから見ることができます。

LOになるまで

ここからはSchemeでLOを取ったときの記録を書いていこうと思います。

言語を書けるようになる

LOを取るためには、まず言語を書けるようになる必要があります。当たり前ですね。

AtCoderで問題を解く前の段階では、Schemeの文法は講義である程度知っていた状態でしたが、入出力を行う方法を知らない状態でした。そこで、AtCoder Beginners Selectionで他の人の提出を見て、簡単な問題をACできるようになりました。3 他の人のコードを見ても分からない部分は、処理系のリファレンスマニュアルを読んで勉強しました。

いっぱい問題を解く

問題を解き始めた2019年の10月21日当時、SchemeのLOだったユーザーのAC数は177でした。つまり、LOになるためには最低でも178問解く必要があります。なんとかACできるような言語で178ACを目指すのは辛いので、まずはAC数ランキング3位に入れる136ACを目指すことにしました。解き始めたのは10月21日の昼頃だったと思います。

ABC (AtCoder Beginners Contest)

ABCは競技プログラミング初心者向けに開催されているコンテストで、4問/6問ある問題セットの中ではA問題が一番簡単です。10月21日時点でABCは143回開催されていたので、A問題をすべて解くと3位には食い込めることがわかります。とりあえず、簡単に解けるA問題と、ぱっと見で簡単そうなB問題を潰しました。これでおよそAC数が140、順位は3位になりました。(ここまで、10月22日朝)

10月22日は「即位礼正殿の儀の行われる日」で休日なので、ありがたく休日を問題埋めに使うことにしました。

その他の問題

LOを狙うとわかるのですが、ABCのA問題とB問題は難易度が雲泥の差です。なのでABCのB問題を埋めるのは後々やることにして、簡単に解けそうな問題を探すことにしました。目指すAC数が400-600なら、B問題を(場合によってはC問題も)埋める必要が出てきますが、この当時は必要なかったためやりませんでした。

まず、AtCoder Problemsを見るとRatedなコンテストで出された問題のdifficultyがほぼ全て載っているので(本当に便利です、これが…!)difficultyが低そうな問題を片っ端から見ていって、簡単に解けそうな問題なら解きました。Schemeの文字列処理をする関数を使いこなせなかったため、文字列処理系の問題はだいたい飛ばしました。ここまででおよそ165ACです。

次に、Unratedなコンテストを見ていきます。A問題や、その他のACできそうな問題()を解きました。
「その他」と大雑把に説明しましたが、実はUnratedなコンテストでは意外なところに簡単にACできる問題があります。それはラソンマッチの問題です。マラソンマッチとは、厳密な最適解を求めるのが難しいような問題でどれだけよいスコアを出せるかを競う大会なのです。逆に言えば、与えられる入力に対して出力のフォーマットが正しければ、どれだけスコアが悪くてもACを得ることができます。これを利用すると、たとえば出力に「○○の行数を1行目に出力して、2行目以降は~」のような制約があれば「0」と出力するだけでACがもらえる可能性があります。そこまでしてLOの称号を得ても虚しくないか、など考えるのはやめにして、Unratedなコンテストの問題を適当に埋めると、AC数が170を超えました。(ここまで、22日夕方)

最後に、ほかにも解けそうな問題を探すために、AC数ランキング上位の人がほかに解いている問題を見ることにしました。AtCoder Scores を使って検索で絞り込むと、「他の人がSchemeでACしているが、自分はしていない問題」のみを表示することができ、これも非常に便利なのでこれを使います。そうすると10問くらい解ける問題が見つかったので、これを解いてAC数が180を超えました。

こうして、22日の夜に、無事SchemeのLOになることができました。だいたい20時間くらいかかったと思います。

LOになりたい方へ向けて

SchemeのLOを取る過程で得た、少ない知見を書いていこうと思います。

現在のLOのAC数が少ない言語(~300ACくらい)を狙う方へ

LOのAC数が少ないのは、大きく分けて4タイプの原因があります。「なんでもいいからLOになりたい」という方は、この原因を見極めるとよいでしょう。

1つ目は、単にほかの言語でコードを書いたほうが楽とかいう理由でAtCoderではあまり使われない言語であること。COBOLや、今回LOを取ったSchemeはこれに当たると思います。言語の仕様さえわかれば、比較的容易にLOを狙えると思います。

2つ目は、難解プログラミング言語であること。これにはUnlambdaなどが含まれます。Unlambdaは入出力すら苦痛(筆者の主観ですが)なので、解ける(解こうと思える)問題が相当限られてきます。それなのにLOは109ACしていて4訳が分かりません。Brainf*ckは564ACです。LOを目指す方は頑張ってください。

3つ目は、ACできない問題がある言語であること。これにはText(cat)があたります。どんな入力に対しても同じ出力でACを得られる問題か、入力がない問題しか解けないため、LOを目指すためには解ける問題探しが重要になります。

4つ目は、コード提出に使える問題が少ない言語であること。これにはIOI-Style C++などが含まれます。IOI-Style C++は IOIer Japan Programming Contestでしか提出に用いることができません。

メジャーな言語でLOを目指す方へ

たとえばC++でLOになるためには、2638ACが必要です5。がんばってください。

おわり

ここまで読んでくださってありがとうございました。AtCoderは近々言語のアップデートがあるかもしれないので、LOを目指すための選択肢が増えるかもしれないですね。明日はMisterさんの記事です。


  1. 実は、今はSchemeのLOではありません。なのにこんな記事を書いていて申し訳なさがあります

  2. Unlambdaは意図的に難解になるように設計された言語ではないですが、公式ホームページ(2019年12月7日確認)に言語の性質として"Obfuscated programming languages"といった記述があることから難解プログラミング言語のくくりに入れています。

  3. 他の人の提出は「提出結果」→「すべての提出」で、言語を見たい言語に、結果をACに絞り込むことで見られます。

  4. AtCoder Scoresで、2019年12月7日確認。

  5. AtCoder Scoresで、2019年12月7日確認。